Paper 2026/1969

Efficient Polynomial System Solving via Dixon Resultants: Applications to AO Primitives

Abstract

Solving multivariate polynomial systems is a fundamental problem in cryptanalysis, with increasing relevance in algebraic attacks on arithmetization-oriented (AO) primitives. Current approaches include Gröbner bases and the Sylvester resultant. However, Gröbner basis methods typically rely on FGLM to change the order, which requires a zero-dimensional ideal, whereas the Sylvester resultant eliminates only one variable at a time, limiting its flexibility in multivariate elimination. We revisit the Dixon resultant as an efficient and flexible tool for eliminating several variables simultaneously. We derive refined upper bounds on the Dixon matrix size via lattice-path counting and analyze the complexity under several determinant computation models, yielding explicit complexity estimates. For well-determined systems, the Dixon resultant is a viable alternative to Gröbner basis methods. Moreover, given their respective limitations, Dixon resultants are particularly suitable for parametric elimination in underdetermined systems, while Gröobner basis methods are generally preferable for solving overdetermined systems. We present an efficient open-source C implementation, DRSolve, with multiple determinant methods and a degree-aware submatrix selection strategy to mitigate the impact of extraneous factors. On the randomly generated well-determined systems tested, our implementation is competitive with the state-of-the-art Gröbner basis solvers Magma and msolve, with DRSolve performing better in the low-variable/highdegree regime, while Magma and msolve remain preferable in the high-variable/low-degree regime. Finally, we formulate three elimination strategies for polynomial systems arising from AO primitives: direct elimination, iterative elimination, and reduction-based hybrid elimination. We demonstrate these strategies on Poseidon, Vision, and XHash12, obtaining complexity reductions in many cases.