Sharpness of the zero-coefficient bounds in the Thomae–Wolf reduction for underdetermined multivariate quadratic systems

Solving a system of $m$ multivariate quadratic (MQ) equations in $n>m$ unknowns over a finite field is the central hard problem behind multivariate (post-quantum) signature schemes such as UOV (Unbalanced Oil and Vinegar) and its descendants. The 2012 Thomae–Wolf algorithm showed that for $n=\omega m$ over fields of even characteristic a linear change of variables can force many cross-term coefficients to zero, reducing the system to one with only $m-\lfloor\omega\rfloor+1$ equations and variables; degrees-of-freedom counting via equivalent keys bounds the achievable reduction (Corollary 2), and the authors claimed — with experimental support only — that these bounds are sharp. The sharpness claim also underlies the solvability assumption of the Kipnis–Patarin–Goubin polynomial-time algorithm and the genericity/semi-regularity assumptions of every successor algorithm, and it is unproven. The open problem: prove, or disprove, that for generic MQ systems the degrees-of-freedom bounds on attainable zero coefficients are also lower bounds (equivalently, the linear systems defining the transformation have full rank).

Background

The MQ problem asks for a solution of a system $f_1=\dots=f_m=0$ of $m$ quadratic polynomials in $n$ variables over a finite field $\mathbb{F}_q$. It is NP-complete in general, yet the difficulty depends strongly on the ratio $n/m$. In the overdetermined case $m\ge n$, Gröbner-basis algorithms — linear-algebra-based polynomial-system solvers such as F4, F5 and XL — profit from extra equations; their running time is predicted by the degree of regularity, the smallest degree at which Gaussian elimination on the Macaulay matrix (the matrix collecting all monomial multiples of the equations up to a given degree) produces an over-determined linear system, computed for semi-regular systems (the standard randomness model) by a generating-series formula due to Bardet, Faugère, Salvy and Yang. In the underdetermined case $n>m$, which is the regime of signature forgery for schemes built on the Unbalanced Oil and Vinegar (UOV) principle — to sign, the legitimate key holder inverts a quadratic map $\mathbb{F}_q^n\to\mathbb{F}_q^m$ with $n>m$ — the known complexity pattern is: (i) Kipnis, Patarin and Goubin (EUROCRYPT 1999) showed that for even characteristic and $n\ge m(m+1)$ the system is solvable in polynomial time by a linear change of variables $S$ after which the transformed equations, restricted to $m$ suitably fixed variables, contain only square terms $x_i^2$, hence linearize via $y_i:=x_i^2$; (ii) Courtois, Goubin, Meier and Tacier (PKC 2002) extended this to arbitrary characteristic but require an infeasible $n\ge 2^{m/7}(m+1)$; (iii) for the cryptographically relevant intermediate regime $m<n<m(m+1)$ (classic UOV parameter sets use $n=3m$, i.e. $\omega=n/m=3$, as in the example treated by Thomae and Wolf) nothing better than randomly guessing $n-m$ variables and solving a square system was known. Thomae and Wolf (PKC 2012) closed this gap for even characteristic: for $n=\omega m$, $\omega\in\mathbb{Q}_{>1}$, they construct a regular transformation $S\in\mathrm{GL}_n(\mathbb{F}_q)$ forcing cross-term coefficients $\tilde\gamma^{(k)}_{i,j}$ (coefficients of $y_iy_j$ in the $k$-th transformed equation) to zero, reducing the system to $m-\lfloor\omega\rfloor+1$ equations and variables ($m-\lfloor\omega\rfloor$ when $\lfloor\omega\rfloor\mid m$), which is then solved by a Gröbner basis solver under the semi-regularity assumption. How many coefficients can be zeroed is bounded by counting the degrees of freedom of $S$ modulo the equivalence class of transformations preserving the achieved zero pattern (the theory of equivalent keys, i.e. transformations that leave the structure of the public system invariant); their Corollary 2 states the upper bound $b_i=\lfloor(n-1)/(i-1)\rfloor$ zero-coefficient equations solvable per column $i$ of $S$ for $2\le i\le m$ (the paper writes this for $1\le i\le m$; the formula is meaningful for $i\ge 2$) and $b_i=1$ for $m+1\le i\le n$, and Corollary 1 the analogous bounds $b_i\le\lfloor(n-2)/(i-1)\rfloor$ for $2\le i\le m$ and $b_i=0$ for $m+1\le i\le n$ in the Kipnis–Patarin–Goubin regime $n\ge m(m+1)$. The paper then asserts as a claim, supported only by experiments, that these bounds are also lower bounds, i.e. sharp for generic systems. Successor work substantially advanced the algorithmic picture: Miura, Hashimoto and Takagi (2013) relaxed the even-characteristic polynomial-time threshold; Cheng, Hashimoto, Miura and Takagi (2014) gave the first polynomial-time algorithm for underdetermined MQ over odd characteristic, with threshold $n\ge m(m+1)/2$ according to the comparative tables of Hashimoto (2023) and May et al. (2026), plus reduced-complexity ('gradual') algorithms valid for any characteristic; Furue, Nakamura and Takagi (2021) combined the transformation with optimized exhaustive search; Hashimoto (2023) and May, Ostuzzi and Ressler (EUROCRYPT 2026, 'Just Guess') give the current best classical and quantum complexities, all of which rest on unproven genericity assumptions. Today the Thomae–Wolf reduction followed by a hybrid Gröbner/XL solver is the standard direct-attack estimate used to select UOV parameters (Beullens et al., TCHES 2023).

Problem Statement

Let $\mathbb{F}_q$ be a finite field, let $m<n$ with $n=\omega m$ for some $\omega\in\mathbb{Q}_{>1}$, and let $\Pi$ be a generic MQ system of $m$ homogeneous quadratic equations in $n$ variables (generic in the algebraic-geometric sense: outside a proper Zariski-closed subset of the coefficient space, equivalently drawn uniformly at random with overwhelming probability). Sharpness of the zero-coefficient bounds (the explicit open claim of Thomae and Wolf, PKC 2012). For fields of even characteristic, the Thomae–Wolf reduction constructs a regular change of variables $S\in\mathrm{GL}_n(\mathbb{F}_q)$ forcing cross-term coefficients $\tilde\gamma^{(k)}_{i,j}$ of the transformed system to zero; degrees-of-freedom counting via the theory of equivalent keys yields the upper bounds of Corollary 2: at most $b_i=\lfloor(n-1)/(i-1)\rfloor$ zero-coefficient equations can be solved per column $i$ of $S$ ($2\le i\le m$), and $b_i=1$ for $m+1\le i\le n$; Corollary 1 gives the analogous bounds $b_i\le\lfloor(n-2)/(i-1)\rfloor$ for $2\le i\le m$ and $b_i=0$ for $m+1\le i\le n$ in the Kipnis–Patarin–Goubin regime $n\ge m(m+1)$. Prove, or disprove, that for generic $\Pi$ these upper bounds — Corollary 2's in general and Corollary 1's in the Kipnis–Patarin–Goubin regime — are also lower bounds — that is: (a) the linear system solved when fixing the $i$-th column of $S$ has full rank, so a solution exists and $S$ stays regular whenever the bound permits; and (b) the minimal representative of the relevant equivalence class of transformations has exactly the counted number of free variables, with the converse upper-bound direction already given by the degrees-of-freedom count.

References

1. Enrico Thomae, Christopher Wolf: Solving Underdetermined Systems of Multivariate Quadratic Equations Revisited. PKC 2012, LNCS 7293, pp. 156–171. DOI 10.1007/978-3-642-30057-8_10, https://doi.org/10.1007/978-3-642-30057-8_10
2. Aviad Kipnis, Jacques Patarin, Louis Goubin: Unbalanced Oil and Vinegar Signature Schemes. EUROCRYPT 1999, LNCS 1592, pp. 206–222. DOI 10.1007/3-540-48910-x_15, https://doi.org/10.1007/3-540-48910-x_15
3. Nicolas Courtois, Louis Goubin, Willi Meier, Jean-Daniel Tacier: Solving Underdefined Systems of Multivariate Quadratic Equations. PKC 2002, LNCS 2274, pp. 211–227. DOI 10.1007/3-540-45664-3_15, https://doi.org/10.1007/3-540-45664-3_15
4. Hiroyuki Miura, Yasufumi Hashimoto, Tsuyoshi Takagi: Extended Algorithm for Solving Underdefined Multivariate Quadratic Equations. PQCrypto 2013, LNCS 7932, pp. 118–135. DOI 10.1007/978-3-642-38616-9_8, https://doi.org/10.1007/978-3-642-38616-9_8
5. Chen-Mou Cheng, Yasufumi Hashimoto, Hiroyuki Miura, Tsuyoshi Takagi: A Polynomial-Time Algorithm for Solving a Class of Underdetermined Multivariate Quadratic Equations over Fields of Odd Characteristics. PQCrypto 2014, LNCS 8772, pp. 40–58. DOI 10.1007/978-3-319-11659-4_3, https://doi.org/10.1007/978-3-319-11659-4_3
6. Heliang Huang, Wansu Bao: Algorithm for Solving Massively Underdefined Systems of Multivariate Quadratic Equations over Finite Fields. arXiv 1507.03674, https://arxiv.org/abs/1507.03674
7. Hiroki Furue, Shuhei Nakamura, Tsuyoshi Takagi: Improving Thomae-Wolf Algorithm for Solving Underdetermined Multivariate Quadratic Polynomial Problem. PQCrypto 2021, LNCS 12841, pp. 65–78. DOI 10.1007/978-3-030-81293-5_4, https://doi.org/10.1007/978-3-030-81293-5_4
8. Ward Beullens: Breaking Rainbow Takes a Weekend on a Laptop. CRYPTO 2022. Cryptology ePrint Archive, Paper 2022/214, https://eprint.iacr.org/2022/214
9. Ward Beullens, Ming-Shing Chen, Shih-Hao Hung, Matthias J. Kannwischer, Bo-Yuan Peng, Cheng-Jhih Shih, Bo-Yin Yang: Oil and Vinegar: Modern Parameters and Implementations. IACR Communications in Cryptology, TCHES 2023(3), pp. 321–365. DOI 10.46586/tches.v2023.i3.321-365, https://doi.org/10.46586/tches.v2023.i3.321-365
10. Yasufumi Hashimoto: An improvement of algorithms to solve under-defined systems of multivariate quadratic equations. JSIAM Letters 15 (2023), pp. 53–56. DOI 10.14495/jsiaml.15.53, https://doi.org/10.14495/jsiaml.15.53
11. Alexander May, Massimo Ostuzzi, Henrik Ressler: Just Guess: Improved (Quantum) Algorithm for the Underdetermined MQ Problem. EUROCRYPT 2026. Cryptology ePrint Archive, Paper 2025/1788, https://eprint.iacr.org/2025/1788
12. Damien Vidal, Sorina Ionica, Claire Delaplace: An analysis of the Crossbred Algorithm for the MQ Problem. Cryptology ePrint Archive, Paper 2024/992, https://eprint.iacr.org/2024/992
13. Pierre Briaud, Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai: Quantum Advantage via Solving Multivariate Quadratics. arXiv 2411.14697, https://arxiv.org/abs/2411.14697 (withdrawn by the authors, who report having been informed of a classical attack on their polynomial system)