[Resource Topic] 2024/1924: The complexity of solving a random polynomial system

Welcome to the resource topic for 2024/1924

Title:
The complexity of solving a random polynomial system

Authors: Giulia Gaggero, Elisa Gorla

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.

ePrint: https://eprint.iacr.org/2024/1924

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .