Welcome to the resource topic for
**2020/1375**

**Title:**

Semi-regular sequences and other random systems of equations

**Authors:**
M. Bigdeli, E. De Negri, M. M. Dizdarevic, E. Gorla, R. Minko, S. Tsakou

**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 Gröbner bases, since computing the solutions of a polynomial system can be reduced to finding a lexicographic Gröbner 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\leq k,n\leq 100 and online we provide the values of the bounds for 2\leq k,n\leq 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.

**ePrint:**
https://eprint.iacr.org/2020/1375

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .