Paper 2020/1375
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
Metadata
- Available format(s)
-
PDF
- 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
- 2020-11-10: 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 = {Semi-regular sequences and other random systems of equations}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/1375}, year = {2020}, url = {https://eprint.iacr.org/2020/1375} }