Paper 2024/1924 Original: eprint.iacr.org/2024/1924 ↗
The complexity of solving a random polynomial system
Abstract
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
- Preprint.
- History
- 2024-11-27: last updated
- 2024-11-27: published
- Short URL
- https://ia.cr/2024/1924
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2024/1924}
}