Semi-regular sequences and other random systems of equations

DOI10.1007/978-3-030-77700-5_3MaRDI QIDQ5048628zbMATH OpenOpenAlexFDO

Authors Mina Bigdeli, Emanuela De Negri, Manuela Muzika Dizdarević, Elisa Gorla, Romy Minko, Sulamithe Tsakou

Publication date 16 November 2022

Published in Association for Women in Mathematics Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.01032

zbMATH Keywords

multivariate cryptographyrandom systemsolving degreeGröbner basissemiregular sequence

Mathematics Subject Classification ID

Cryptography (94A60) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Hilbert-Samuel and Hilbert-Kunz functions; Poincaré series (13D40) Solving polynomial systems; resultants (13P15)

Abstract: The security of multivariate cryptosystems and digital signature schemes relies on the hardness of solving a system of polynomial equations over a finite field. Polynomial system solving is also currently a bottleneck of index-calculus algorithms to solve the elliptic and hyperelliptic curve discrete logarithm problem. The complexity of solving a system of polynomial equations is closely related to the cost of computing Groebner bases, since computing the solutions of a polynomial system can be reduced to finding a lexicographic Groebner basis for the ideal generated by the equations. Several algorithms for computing such bases exist: We consider those based on repeated Gaussian elimination of Macaulay matrices. In this paper, we analyze the case of random systems, where random systems means either semi-regular systems, or quadratic systems in n variables which contain a regular sequence of n polynomials. We provide explicit formulae for bounds on the solving degree of semi-regular systems with m > n equations in n variables, for equations of arbitrary degrees for m = n+1, and for any m for systems of quadratic or cubic polynomials. In the appendix, we provide a table of bounds for the solving degree of semi-regular systems of m = n + k quadratic equations in n variables for 2 <= k; n <= 100 and online we provide the values of the bounds for 2 <= k; n <= 500. For quadratic systems which contain a regular sequence of n polynomials, we argue that the Eisenbud-Green-Harris Conjecture, if true, provides a sharp bound for their solving degree, which we compute explicitly.

Recommendations

• Solving multivariate polynomial systems and an invariant from commutative algebra
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations
• The degree of regularity of HFE systems
• Solving degree and degree of regularity for polynomial systems over a finite field
• scientific article; zbMATH DE number 2085432

Cites work

• scientific article; zbMATH DE number 3857249 (Why is no real title available?)
• scientific article; zbMATH DE number 4057653 (Why is no real title available?)
• scientific article; zbMATH DE number 592836 (Why is no real title available?)
• scientific article; zbMATH DE number 2151220 (Why is no real title available?)
• scientific article; zbMATH DE number 1418284 (Why is no real title available?)
• scientific article; zbMATH DE number 2206382 (Why is no real title available?)
• Algorithmic Cryptanalysis
• An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
• An inequality for Hilbert series of graded algebras.
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations
• Elliptic curve discrete logarithm problem over small degree extension fields
• Generic sequences of polynomials
• Hybrid approach for solving multivariate systems over finite fields
• Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem
• On the existence of homogeneous semi-regular sequences in \(\mathbb{F}_2[X_1,\ldots,X_n]/(X_1^2,\ldots,X_n^2)\)
• On the minimal free resolution of $n+1$ general forms
• Syzygies of semi-regular sequences
• The Magma algebra system. I: The user language
• The initial ideal of generic sequences and Fröberg's conjecture
• Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property

Cited in

(12)

• On the first fall degree of summation polynomials
• Probabilistic analysis on Macaulay matrices over finite fields and complexity of constructing Gröbner bases
• The complexity of solving Weil restriction systems
• Solving degree, last fall degree, and related invariants
• Phase transition of multivariate polynomial systems
• Krawtchouk polynomials and quadratic semi-regular sequences
• Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology
• Solving polynomial systems over finite fields: improved analysis of the hybrid approach
• Development of hybrid approach for solving MQ problem: Intermediate hybrid approach
• Solving multivariate polynomial systems and an invariant from commutative algebra
• On the existence of homogeneous semi-regular sequences in \(\mathbb{F}_2[X_1,\ldots,X_n]/(X_1^2,\ldots,X_n^2)\)
• Solving degree and degree of regularity for polynomial systems over a finite field

Describes a project that uses

Uses Software

• CoCoA
• Macaulay2
• Magma
• Mathematica

This page was built for publication: Semi-regular sequences and other random systems of equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5048628)