Talk
Solving Polynomial Systems and an Invariant from Commutative Algebra
Talk by Dr. Alessio Caminata
Date: 21.03.18 Time: 16.00 - 17.00 Room: Y27H28
The security of several post-quantum cryptoschemes is based on the assumption that solving a system of (quadratic) polynomial equations $p_1\cdots=p_m=0$ in several variables over a finite field is hard. A common efficient strategy to solve such a system is computing a lexicographic Groebner basis of the ideal $(p_1,\cdots,p_m)$. The fastest known algorithms for this scope are algorithms which transform the polynomial solving process into several steps of solving linear systems, such as F4 and Mutant XL. To understand the complexity of these algorithms, it is important to know the highest degree of the polynomials involved in the computations, the so-called solving degree of the system. We prove that the solving degree is controlled by the Castelnuovo-Mumford regularity of the homogeneous ideal $(p^h_1,\cdots,p^h_m)$ obtained by homogenizing the input polynomials. We apply this result to obtain bounds on the solving degree of ideals coming from multivariate cryptography and from instances of the MinRank problem. This is a joint work with Elisa Gorla.