Paper 2024/1924
The complexity of solving a random polynomial system
, University of Neuchatel, University of NeuchatelAbstract
In this paper, we discuss what it means for a polynomial system to be random and how hard it is to solve a random polynomial system. We propose an algebraic definition of randomness, that we call algebraic randomness. Using a conjecture from commutative algebra, we produce a sharp upper bound for the degree of regularity, hence the complexity of solving an algebraically random polynomial system by Groebner bases methods. As a proof of concept, we apply our result to Rainbow and GeMSS and show that these systems are far from being algebraically random.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. arXiv, poster at MEGA 2022
- DOI
- https://arxiv.org/abs/2309.03855
- Keywords
- multivariate cryptographyrandom systemsolving degreedegree of regularity
- Contact author(s)
-
giulia gaggero @ unine ch
elisa gorla @ unine ch - History
- 2024-11-29: approved
- 2024-11-27: received
- See all versions
- Short URL
- https://ia.cr/2024/1924
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1924,
author = {Giulia Gaggero and Elisa Gorla},
title = {The complexity of solving a random polynomial system},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1924},
year = {2024},
doi = {https://arxiv.org/abs/2309.03855},
url = {https://eprint.iacr.org/2024/1924}
}
