### Semi-regular sequences and other random systems of equations

M. Bigdeli, E. De Negri, M. M. Dizdarevic, E. Gorla, R. Minko, and 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.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Women in Numbers Europe III: Research Directions in Number Theory A. Cojocaru, S. Ionica and E. Lorenzo Garcia Eds., Springer
Keywords
Groebner basismultivariate cryptographysolving degreerandom systemsemiregular sequence
Contact author(s)
elisa gorla @ unine ch
History
Short URL
https://ia.cr/2020/1375

CC BY

BibTeX

@misc{cryptoeprint:2020/1375,
author = {M.  Bigdeli and E.  De Negri and M.  M.  Dizdarevic and E.  Gorla and R.  Minko and S.  Tsakou},
title = {Semi-regular sequences and other random systems of equations},
howpublished = {Cryptology ePrint Archive, Paper 2020/1375},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1375}},
url = {https://eprint.iacr.org/2020/1375}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.