Semi-regularity of the RMQ modelings: proving Assumption 1 and Heuristic 1 behind the complexity analysis of the Regular Multivariate Quadratic problem

The Regular Multivariate Quadratic (RMQ) problem asks to solve a system of $m$ random quadratic equations over $\mathbb{F}_2$ in $n=lw$ variables whose solution must be regular: split into $w$ blocks of length $l$ , each block containing exactly one nonzero entry. Joux and Mora (2025) proved NP-completeness of RMQ and derived asymptotic complexity formulas for Gröbner-basis and hybrid algebraic attacks at the uniqueness bound. All of these formulas rest on two unproven statements — Assumption 1, asserting that the random quadratic polynomials behave semi-regularly modulo the structured ideal encoding the regular constraint (in plain, hybrid, and big-field modelings), and Heuristic 1, asserting a maximum formula for the Hilbert function of an alternative modeling of degree $2s$ (where $l=2^s$ ). The problem is to prove these statements, or to refute them with certified computations, thereby placing the complexity analysis of RMQ on rigorous footing.

Background

The Multivariate Quadratic (MQ) problem — finding a common zero, over a finite field, of $m$ randomly drawn quadratic polynomials in $n$ variables — is NP-complete and conjectured hard on average; it is the computational foundation of multivariate cryptography, one of the leading post-quantum alternatives. The regular variant studied here imports a constraint from code-based cryptography: the vector of $n=lw$ variables is split into $w$ consecutive blocks (windows) of length $l$ , and an admissible solution must have exactly one nonzero entry per block. This is the same regularity notion as in Regular Syndrome Decoding (RSD), introduced by Augot, Finiasz and Sendrier (2005) for hash functions and since used in pseudorandom correlation generators and MPC-in-the-head signatures. Joux and Mora (2025) defined RMQ as the MQ analogue — fully random equations, regular solution — proved it NP-complete, and analyzed the asymptotic complexity of the main solver families in the uniqueness-bound regime, i.e. $m=\mu n$ with $\mu$ large enough that the instance has a unique expected regular solution.

The algebraic attack route is Gröbner-basis computation (or the equivalent XL approach — eXtended Linearization, which multiplies the equations by all monomials up to a degree bound and treats the resulting products as independent linear unknowns): one builds Macaulay matrices — matrices whose rows are the polynomial multiples of the system up to some degree — and reduces them by Gaussian elimination. The cost is dominated by linear algebra on a matrix of size roughly $\binom{n}{d}$ , where $d$ is the solving degree, so the whole analysis reduces to predicting the degree of regularity $d_{\mathrm{reg}}$ , the degree at which the system becomes solved. For random systems this prediction comes from the Hilbert series, the generating function of the dimensions of the graded pieces of the quotient ring $R/I$ ( $R$ the polynomial ring, $I$ the ideal generated by the system). A system is called semi-regular if it has no spurious low-degree relations: whenever $g_i f_i = 0$ with $\deg(g_i f_i) < d_{\mathrm{reg}}$ , then $g_i = 0$ . For semi-regular systems the Hilbert series has a closed product form, from which Bardet, Faugère, Salvy and Spaenlehauer (2013) derived explicit complexity formulas for quadratic boolean systems. The statement that randomly drawn systems are semi-regular with high probability is a cousin of Fröberg's conjecture (1985) on Hilbert series of graded algebras and has remained unproven for forty years; every concrete security estimate in multivariate cryptography relies on it heuristically.

Joux and Mora encode the regular constraint algebraically. Modeling A (over $\mathbb{F}_2$ ) augments the $m$ random quadratics with: field equations $x_{i,j}^2 = x_{i,j}$ for all $n$ variables (forcing solutions over $\mathbb{F}_2$ ), quadratic 'at most one nonzero per block' equations $x_{i,j_1} x_{i,j_2}$ for distinct positions in a block, and affine linear 'exactly one nonzero per block' equations $\sum_j x_{i,j} + 1$ . Modeling B (over a big field $\mathbb{F}_q$ ) keeps only the quadratic block equations. The structured equations generate a fixed ideal; the analysis must then predict how the $m$ random quadratics behave in the quotient ring $Q$ defined by that structured ideal. Assumption 1 postulates exactly the semi-regularity property for the random quadratics inside $Q$ — in the plain case, in the hybrid cases (after specializing variables by guessing, which is how Gröbner computations are sped up at the cost of repetitions), and in the big-field case. The assumption mirrors the one introduced by Briaud and Øygarden (2023) for the structured modelings of RSD, whose proof framework Joux and Mora inherit; in both papers it is validated only by experiments at small parameters. From Assumption 1 the authors derive closed-form Hilbert series for each strategy and, by saddle-point analysis (a standard asymptotic method for extracting coefficients of generating functions), the relative degree of regularity $\bar\delta = d_{\mathrm{reg}}/n$ as the smallest root of an explicit quartic polynomial in the plain case, yielding complexities of order $O^*(2^{\omega H(\bar\delta)n})$ — soft- $O$ notation, suppressing factors polynomial in $n$ — with $\omega$ the linear-algebra exponent of matrix multiplication and $H$ the binary entropy function. No finite- $n$ error bounds connect these asymptotic roots to the degrees observed in actual runs.

The paper also studies an alternative modeling: when $l = 2^s$ , a bijection maps each window to $s = \log_2 l$ variables, turning the RMQ instance into a system of degree $2s$ in $sw$ variables. Heuristic 1 asserts that the Hilbert function of the homogenized transformed system is the maximum of the semi-regular prediction and the number of non-admissible monomials (monomials excluded by the transformed field equations); it is supported experimentally (the authors' Table 1 compares solving degrees for small parameters) but not proved.

Thus every complexity formula in the RMQ analysis is conditional on unproven semi-regularity statements: the structured-quotient assumption itself (Assumption 1) and the alternative-modeling behavior (Heuristic 1). Whether these statements are true is open, and is the subject of this problem.

Problem Statement

Establish or refute, with rigor, the semi-regularity predictions that underlie the Gröbner-basis complexity analysis of the Regular Multivariate Quadratic (RMQ) problem given by Joux and Mora. Concretely, resolve the following two linked questions, which jointly determine whether the paper's asymptotic complexity formulas for plain, hybrid, and alternative-modeling algebraic attacks on RMQ at the uniqueness bound are correct.

Assumption 1 (structured-quotient semi-regularity). For Modeling A (boolean, with field equations, block quadratics, and block-sum linears), including its hybrid specializations, and for Modeling B (big field), determine whether the randomly drawn quadratic polynomials satisfy the semi-regularity property in the quotient ring defined by the structured ideal, so that the predicted Hilbert series — and hence the predicted degree of regularity — is correct.
Heuristic 1 (alternative modeling). For the alternative mapping that sends each window of $l=2^s$ variables to $s=\log_2 l$ variables, turning the system into equations of degree $2s$ in $sw$ variables, prove or refute the claim that the Hilbert function of the homogenized transformed system equals the maximum of the semi-regular prediction and the number of non-admissible monomials.

The problem is resolved when these Hilbert-series predictions are either proved or refuted with certified evidence — an argument or an exact computation whose validity can be independently checked. The reach of a finite computation is the same for both questions: an exact computation over an explicitly stated finite parameter range certifies a prediction on that range only. Because both predictions concern the behaviour of randomly drawn systems over the scaling of the analysis rather than a single fixed instance, neither question is settled by a finite-range computation alone. Full resolution of each requires evidence valid for that scaling — a proof, or a refutation showing that the prediction fails, or that its failure probability does not tend to $0$ . Analytical proofs and refutations, and exact computations valid in that scaling, are all admissible.

References

Antoine Joux, Rocco Mora. The regular multivariate quadratic problem. Designs, Codes and Cryptography 93(12) (2025), pp. 5179–5229. DOI: 10.1007/s10623-025-01717-6 (arXiv:2503.07342). https://arxiv.org/abs/2503.07342
Pierre Briaud, Morten Øygarden. A New Algebraic Approach to the Regular Syndrome Decoding Problem and Implications for PCG Constructions. Advances in Cryptology – EUROCRYPT 2023. DOI: 10.1007/978-3-031-30589-4_14. https://doi.org/10.1007/978-3-031-30589-4_14
Magali Bardet, Jean-Charles Faugère, Bruno Salvy, Pierre-Jean Spaenlehauer. On the complexity of solving quadratic Boolean systems. Journal of Complexity 29(1) (2013). DOI: 10.1016/j.jco.2012.07.001. https://doi.org/10.1016/j.jco.2012.07.001
Ralf Fröberg. An inequality for Hilbert series of graded algebras. Mathematica Scandinavica 56(2) (1985). DOI: 10.7146/math.scand.a-12092. https://doi.org/10.7146/math.scand.a-12092
Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. A Family of Fast Syndrome Based Cryptographic Hash Functions. Progress in Cryptology – Mycrypt 2005. DOI: 10.1007/11554868_6. https://doi.org/10.1007/11554868_6
Mina Bigdeli, Emanuela De Negri, Manuela Muzika Dizdarevic, Elisa Gorla, Romy Minko, Sulamithe Tsakou. Semi-Regular Sequences and Other Random Systems of Equations. Women in Numbers Europe III (2021). DOI: 10.1007/978-3-030-77700-5_3 (arXiv:2011.01032). https://arxiv.org/abs/2011.01032
Momonari Kudo, Kazuhiro Yokoyama. Generalization of semi-regular sequences: Maximal Gröbner basis degree, variants of genericness, and related conjectures (2024). arXiv:2410.23211. https://arxiv.org/abs/2410.23211
Antoine Joux, Vanessa Vitse. A Crossbred Algorithm for Solving Boolean Polynomial Systems. Number-Theoretic Methods in Cryptology (NuTMiC 2017), Lecture Notes in Computer Science, 2018. DOI: 10.1007/978-3-319-76620-1_1. https://doi.org/10.1007/978-3-319-76620-1_1
Damien Vidal, Claire Delaplace, Sorina Ionica. An analysis of the Crossbred Algorithm for the MQ Problem. IACR Communications in Cryptology (2024). DOI: 10.62056/ak86cy7qiu. https://doi.org/10.62056/ak86cy7qiu
John Baena, Daniel Cabarcas, Sharwan K. Tiwari, Javier A. Verbel, Luis Villota. Admissible parameters for the Crossbred algorithm and semi-regular sequences over finite fields. Designs, Codes and Cryptography (2025). DOI: 10.1007/s10623-025-01610-2. https://doi.org/10.1007/s10623-025-01610-2
Andre Esser, Paolo Santini. Not Just Regular Decoding: Asymptotics and Improvements of Regular Syndrome Decoding Attacks. Advances in Cryptology – CRYPTO 2024. DOI: 10.1007/978-3-031-68391-6_6. https://doi.org/10.1007/978-3-031-68391-6_6
Tianrui Wang, Anyu Wang, Kang Yang, Hanlin Liu, Yu Yu, Jun Zhang, Xiaoyun Wang. A Hybrid Algorithm for the Regular Syndrome Decoding Problem. Advances in Cryptology – ASIACRYPT 2025. DOI: 10.1007/978-981-95-5113-2_15. https://doi.org/10.1007/978-981-95-5113-2_15
Hanlin Liu, Xiao Wang, Kang Yang, Longhui Yin, Yu Yu. AGB 2.0: Refined Algebraic Attack against Regular Syndrome Decoding for PCG Applications. IACR Cryptology ePrint Archive, Report 2025/1476 (2025). https://eprint.iacr.org/2025/1476
Alessio Caminata, Ryann Cartor, Alessio Meneghetti, Rocco Mora, Alex Pellegrini. Quadratic Modelings of Syndrome Decoding. Post-Quantum Cryptography (PQCrypto 2025). DOI: 10.1007/978-3-031-86599-2_2 (arXiv:2412.04848). https://arxiv.org/abs/2412.04848
Dheerendra Mishra, Kuldeep Namdeo, Namita Srivastava. The rise and resilience of multivariate cryptography: Advances, pitfalls, and promising pathways. Computer Science Review (2026). DOI: 10.1016/j.cosrev.2025.100860. https://doi.org/10.1016/j.cosrev.2025.100860
Pierre Briaud, Itai Dinur, Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai. Quantum Advantage via Solving Multivariate Polynomials (2025). arXiv:2509.07276. https://arxiv.org/abs/2509.07276