Paper 2020/1375
Semiregular 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 indexcalculus 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 semiregular 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 semiregular 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 semiregular 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 EisenbudGreenHarris conjecture, if true, provides a sharp bound for their solving degree, which we compute explicitly.
Metadata
 Available format(s)
 Category
 Publickey 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
 20201110: received
 Short URL
 https://ia.cr/2020/1375
 License

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 = {Semiregular 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} }