Gröbner-basis solving and first fall degree
Many attacks end with a system of polynomial equations: summation polynomials, multivariate signatures, algebraic attacks on ciphers. Gröbner-basis algorithms solve them, and their cost is set almost entirely by one number, the degree the computation has to reach. For random systems that degree can be predicted. For the structured systems cryptanalysis produces, predicting it is the whole problem.
- Problem
- Find the common zeros of polynomials f1, …, fm in n variables over a finite field
- Algorithms
- Buchberger (1965); XL; F4 (1999) and F5 (2002), which do the work as sparse linear algebra
- Cost driver
- The solving degree D: the matrices have one column per monomial of degree up to D
- Measured here
- In 8 shapes of random quadratic system over F2, XL solved 5 within the predicted degree of regularity and needed one more degree in 3
- Open question
- Whether systems from summation polynomials and HFE variants fall far below the generic degree
From equations to linear algebra
A Gröbner basis of the ideal generated by f1, …, fm is a generating set in which the equations can be solved one variable at a time, much as Gaussian elimination produces a triangular linear system. For a system with finitely many solutions, a basis in lexicographic order ends in a polynomial in a single variable, whose roots can be found directly. Buchberger's 1965 algorithm computes one by repeatedly combining pairs of polynomials to cancel their leading terms.
The modern algorithms turn this into linear algebra. Multiply every equation by every monomial up to some degree D. Treat each monomial as an unknown, write the products as rows of a matrix (the Macaulay matrix), and row-reduce with monomials ordered by degree. A row whose leading term has dropped to low degree is a new, lower-degree consequence of the system. XL, due to Courtois, Klimov, Patarin and Shamir, does exactly this and raises D until linear equations appear. Faugère's F4 chooses which products to add far more selectively. F5 also predicts in advance which rows would reduce to zero, and skips them.
Either way the cost is dominated by the largest matrix, whose width is the number of monomials of degree up to the solving degree D, about C(n + D, D). The complexity is roughly that number raised to the linear-algebra exponent ω, between 2 and 3. Everything depends on D.
Degree of regularity and first fall degree
For a system with no special structure, the degree the computation reaches can be predicted. Bardet, Faugère and Salvy defined semi-regular systems, whose only relations among the equations are the trivial ones every system has, such as fifj − fjfi = 0. For these the Hilbert series is known in closed form. Over F2, with the field equations x2 = x, m quadratics in n variables have series (1 + z)n / (1 + z2)m. The degree of regularity Dreg is the first degree at which its coefficient stops being positive. Random systems are believed to be semi-regular with high probability, and Dreg is the number that complexity estimates for multivariate schemes are built on.
The first fall degree is a measured rather than a predicted quantity. It is the lowest degree at which some combination of the products has its leading terms cancel for a reason other than the trivial relations: a genuine degree fall. For a semi-regular system it coincides with Dreg. For a structured system it can be much lower, and when it is, the computation can finish at that lower degree. That is how structure becomes an attack.
A measurement with XL
The code behind this page generated random quadratic systems over F2, each with a planted solution, and redrew each system until that solution was the only one, checked by trying every point. With several solutions no degree gives n independent linear equations, and the solver has to recover a larger structure instead. It then ran XL at D = 2, 3, … until the reduced matrix contained a linear equation for every variable, read off the solution, and checked it against the system. The table compares that solving degree with the semi-regular Dreg for the same shape, 3 systems per shape.
| n | m | Dreg | Solved at | Columns |
|---|---|---|---|---|
| 8 | 8 | 3 | 4, 4, 4 | 163 |
| 10 | 10 | 4 | 4, 4, 4 | 386 |
| 12 | 12 | 4 | 4, 4, 4 | 794 |
| 14 | 14 | 4 | 5, 5, 5 | 3,473 |
| 8 | 16 | 3 | 3, 3, 3 | 93 |
| 10 | 20 | 3 | 3, 3, 3 | 176 |
| 12 | 24 | 3 | 3, 3, 3 | 299 |
| 14 | 28 | 3 | 4, 4, 4 | 1,471 |
The prediction holds up to one degree. XL finished at Dreg in 5 of the 8 shapes and at Dreg + 1 in the other 3. Dreg describes when the top-degree parts of the equations fill every monomial; pushing all the way down to linear equations can take one degree more. Doubling the number of equations lowers the degree. That is why an attacker with more equations than unknowns, from many plaintexts or from Weil descent, is in a better position.
Structured systems
Cryptanalysis rarely meets random systems. It meets systems with a hidden structure, and the question is always whether that structure makes the degree fall early:
- HFE. Patarin's Hidden Field Equations hide a low-degree univariate polynomial over an extension field behind linear changes of variables. Faugère and Joux solved Patarin's first HFE challenge, in work published in 2003, because the public systems had a degree of regularity far below that of random systems. Dubois and Gama later bounded it in terms of the hidden degree, and that bound is why plain HFE is broken and its variants add modifiers.
- Summation polynomials. The systems from elliptic-curve index calculus come from Weil descent of a Semaev polynomial and are highly structured. Petit and Quisquater conjectured, from first-fall-degree experiments, that the binary-field ECDLP is subexponential. Huang, Kosters and Yeo introduced the last fall degree, an invariant with a firmer link to running time than the first fall degree. Whether the first fall degree predicts the running time of these systems is exactly what is disputed.
- Symmetry and multi-homogeneity. Systems invariant under a group, such as permutations of the decomposition variables, can be rewritten in invariants of lower degree. This is often the difference between a feasible and an infeasible computation.
The boundary
For random systems of quadratic equations, Gröbner-basis algorithms are exponential, with an exponent that Dreg predicts well. That is the assumption behind multivariate signature schemes, and their parameters are set against it together with the dedicated attacks on their structure. For the systems from elliptic-curve index calculus over prime fields there is no factor base to generate them from at all; see summation polynomials. Over binary and extension fields the systems exist, and the dispute over their degree of regularity is the live question.
Primary sources
- J.-C. Faugère, "A new efficient algorithm for computing Gröbner bases (F4)", Journal of Pure and Applied Algebra 139 (1999)
- J.-C. Faugère, "A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)", ISSAC 2002
- N. Courtois, A. Klimov, J. Patarin and A. Shamir, "Efficient algorithms for solving overdefined systems of multivariate polynomial equations", EUROCRYPT 2000
- J.-C. Faugère and A. Joux, "Algebraic cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gröbner bases", CRYPTO 2003
- V. Dubois and N. Gama, "The degree of regularity of HFE systems", ASIACRYPT 2010
- C. Petit and J.-J. Quisquater, "On polynomial systems arising from a Weil descent", ASIACRYPT 2012
- M.-D. Huang, M. Kosters and S. L. Yeo, "Last fall degree, HFE, and Weil descent attacks on ECDLP", CRYPTO 2015