Semi-regular sequences and other random systems of equations
This work addresses the computational complexity of polynomial system solving, a key issue in cryptography and discrete logarithm problems, though it appears incremental as it builds on existing methods and conjectures.
The paper tackles the problem of solving random systems of polynomial equations, which is crucial for cryptographic security and algorithm bottlenecks, by providing explicit formulae and bounds for the solving degree of semi-regular systems and quadratic systems containing regular sequences, with specific bounds computed for up to 500 variables.
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.