The Multivariate Quadratic (MQ) problem — finding a common solution of mm quadratic equations in nn variables over a finite field — is NP-complete in general, yet becomes tractable when the system is massively underdefined (far more variables than equations). Since Kipnis–Patarin–Goubin (1999), a line of linearization-based algorithms has pushed the polynomial-time threshold down from n≥m(m+1)n\ge m(m+1) to the current frontier n≥m(m+1)/2n\ge m(m+1)/2. Huang and Bao (2015) posed, as explicit future work, closing the remaining gap between this polynomial-time regime and the square case n=mn=m. The question is cryptographically load-bearing: forging signatures in the UOV family of post-quantum schemes (UOV, MAYO, QR-UOV, SNOVA) is equivalent to solving underdefined MQ instances whose parameters lie deep inside the gap.

Background

The MQ problem asks for a common root of mm quadratic polynomial equations in nn variables over a finite field Fq\mathbb{F}_q. It is NP-complete in general, and the assumed hardness of generic (random-looking) instances underpins multivariate public-key cryptography, one of the candidate families for post-quantum digital signatures. Two regimes are comparatively easy. In the overdefined case (m≫nm\gg n), Gröbner-basis and XL algorithms — methods that multiply the equations by monomials and linearize, then solve one large linear system — are effective. In the massively underdefined case (n≫mn\gg m), the excess of variables can itself be exploited.

Underdefined (also called underdetermined) instances, with more variables than equations (n>mn>m), are exactly what a forger of UOV-family signatures must solve. UOV ("Unbalanced Oil and Vinegar") is the archetype of multivariate signature schemes: the public key is a quadratic map P:Fqn→FqmP:\mathbb{F}_q^n\to\mathbb{F}_q^m that looks random, and signing means finding a preimage of a hashed message — the secret key merely provides a shortcut. A forger faces the raw underdefined MQ problem, so the concrete security of UOV and its descendants MAYO, QR-UOV and SNOVA is set by the best algorithms for this problem. These schemes deliberately use nn only a small multiple of mm (for example MAYO security level I uses m=78m=78, n=86n=86), far below n≈m2/2n\approx m^2/2.

The key technique for the massively underdefined regime, introduced by Kipnis, Patarin and Goubin (EUROCRYPT 1999), is a linear change of variables that eliminates all mixed quadratic terms xixjx_ix_j from enough equations so that, after fixing the remaining variables, each equation becomes linear in the squares xi2x_i^2; the system is then solved by Gaussian elimination plus square-root extraction. This requires n≥m(m+1)n\ge m(m+1) over fields of even characteristic. Successive refinements tightened the required number of variables: Courtois–Goubin–Meier–Tacier (PKC 2002) extended the approach to odd characteristic at an exponential cost in mm; an attempt by Hashimoto (2011) was shown by Miura–Hashimoto–Takagi not to achieve its claimed efficiency; Miura–Hashimoto–Takagi (PQCrypto 2013) reached n≥m(m+3)/2n\ge m(m+3)/2, polynomial over even characteristic with a 2m2^m overhead in odd; and Cheng–Hashimoto–Miura–Takagi (PQCrypto 2014), independently of the Huang–Bao preprint that is the source of the present question, reached the current frontier n≥m(m+1)/2n\ge m(m+1)/2 with a polynomial-time algorithm over fields of odd characteristic.

For the intermediate regime m<n<m(m+1)/2m<n<m(m+1)/2, a separate line of interpolating algorithms reduces an (m,n)(m,n) instance to a smaller square instance plus exhaustive guessing: Thomae–Wolf (PKC 2012) and its improvements by Furue–Nakamura–Takagi (PQCrypto 2021) and Hashimoto (2021, 2023). The most recent and strongest, "Just Guess" by May–Ostuzzi–Ressler (EUROCRYPT 2026), transforms the system into single-variable quadratic equations at the cost of a larger exhaustive search and runs in O~(qm−2n−m)\tilde{O}(q^{m-\sqrt{2n-m}}) — exponential in mm throughout the gap, polynomial exactly at n=m(m+1)/2n=m(m+1)/2, and essentially exhaustive search near n=mn=m; it also gives speedups from Grover search — the generic quantum technique that finds a marked item among NN candidates in about N\sqrt{N} queries — that reduce the estimated quantum security of MAYO, QR-UOV and SNOVA.

Thus the polynomial-time threshold has been stuck at n≈m2/2n\approx m^2/2 since 2014–2015, while all cryptographically relevant instances live deep inside the gap. Whether the gap can be closed — whether the excess of variables can be exploited all the way down to nn close to mm — was posed as future work in the Huang–Bao preprint.

Problem Statement

Determine the computational complexity of solving generic (random) underdefined MQ instances — mm quadratic equations in nn variables over a finite field Fq\mathbb{F}_q, with m<n<m(m+1)/2m<n<m(m+1)/2 — and thereby close the gap, posed as future work in Huang–Bao (2015), between the square case n=mn=m (worst-case NP-hard, best known time qΘ(m)q^{\Theta(m)}) and the polynomial-time regime n≥m(m+1)/2n\ge m(m+1)/2. The complexity of interest concerns generic systems (not a structured subclass), over a stated range of field characteristics, with complexity and success probability proved (worst case, or with overwhelming probability over random instances) rather than merely heuristic.

References

  1. Heliang Huang, Wansu Bao. Algorithm for Solving Massively Underdefined Systems of Multivariate Quadratic Equations over Finite Fields. arXiv:1507.03674, 2015. https://arxiv.org/abs/1507.03674
  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. Yasufumi Hashimoto. Algorithms to Solve Massively Under-Defined Systems of Multivariate Quadratic Equations. IEICE Transactions on Fundamentals E94-A(6), 2011, pp. 1257–1262. DOI: 10.1587/transfun.e94.a.1257. https://doi.org/10.1587/transfun.e94.a.1257
  5. 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
  6. 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
  7. 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
  8. 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
  9. Yasufumi Hashimoto. An improvement of algorithms to solve under-defined systems of multivariate quadratic equations. IACR ePrint Archive 2021/1045, 2021. https://eprint.iacr.org/2021/1045
  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. Emanuele Bellini, Rusydi H. Makarim, Carlo Sanna, Javier Verbel. An Estimator for the Hardness of the MQ Problem. Africacrypt 2022. DOI: 10.1007/978-3-031-17433-9_14; also IACR ePrint Archive 2022/708. https://eprint.iacr.org/2022/708
  12. Alexander May, Massimo Ostuzzi, Henrik Ressler. Just Guess: Improved (Quantum) Algorithm for the Underdetermined MQ problem. EUROCRYPT 2026; IACR ePrint Archive 2025/1788, 2025. DOI: 10.1007/978-3-032-25327-9_12. https://eprint.iacr.org/2025/1788
  13. Daniel Smith-Tone, Cristina Tone. A correct justification for the CHMT algorithm for solving underdetermined multivariate systems. Finite Fields and Their Applications 103, 2025, article 102547. DOI: 10.1016/j.ffa.2024.102547. https://doi.org/10.1016/j.ffa.2024.102547
  14. Pierre Briaud, Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai. Quantum Advantage via Solving Multivariate Quadratics. arXiv:2411.14697, 2024. https://arxiv.org/abs/2411.14697