Meneghetti, Pellegrini and Sala constructed explicit polynomial-time reductions between maximum-likelihood decoding (MLD) of linear codes and the multivariate quadratic system problem (MQ), proving the two problems polynomial-time isomorphic and thereby linking the security foundations of code-based and multivariate post-quantum cryptography. Their paper leaves three linked directions open: characterize the structural and algebraic properties of the special-form quadratic systems in the image of the reduction from MLD to MQ — in particular those coming from real code-based cryptosystems such as the permuted Goppa codes hidden in Classic McEliece public keys — and decide whether these systems admit algorithms asymptotically faster than for arbitrary MQ; dually, characterize the codes produced by the reverse reduction and what it reveals on masked multivariate public keys; and formalize the precise computational problem of recovering a private key from a public key in both families and study its complexity. All three cores remain open: subsequent work improved the reduction's efficiency and advanced distinguishers and structure recovery for Goppa codes, and Rainbow was broken by a dedicated key-recovery attack, but no characterization of the reduction images, no asymptotic speedup for their special-form systems, and no general complexity-theoretic treatment of key recovery exists.

Background

Two families of post-quantum public-key cryptography rest on two NP-complete algorithmic problems. On the code-based side, the hardness pillar is the maximum-likelihood decoding problem (MLD): given a parity-check matrix HH of a linear code of length nn over a finite field, a syndrome ss, and an integer tt, find an error vector ee of Hamming weight (number of nonzero entries) at most tt with He⊤=sHe^{\top}=s. MLD — in its decision form — was proved NP-complete by Berlekamp, McEliece and van Tilborg in 1978, and its hardness underpins the McEliece cryptosystem and its modern variant Classic McEliece, a NIST post-quantum standardization finalist. In Classic McEliece the public key is a permuted, disguised parity-check matrix of a binary irreducible Goppa code (an algebraically structured code defined by a polynomial over an extension field, for which a fast bounded-distance decoder exists); only the legitimate key holder knows the hidden Goppa structure. On the multivariate side, the pillar is the MQ problem: given mm quadratic polynomials in nn variables over a finite field, find a common zero. MQ is NP-complete over any finite field, and multivariate schemes such as Rainbow (a signature scheme built on the Oil-and-Vinegar construction, in which secret 'oil' and 'vinegar' variable layers make the hidden quadratic system easy to solve by Gaussian elimination while the published, masked system looks generic) rely on the difficulty of solving and of distinguishing the masked system from a generic one. The security of both families thus rests on two questions: solving generic instances, and distinguishing a masked easy instance from a generic one (equivalently, recovering the secret structure). Meneghetti, Pellegrini and Sala built two explicit polynomial-time reductions: α\alpha, mapping any MLD instance to a quadratic system (the costliest part is the Hamming-weight computation encoding, which introduces recursively defined variables and equations that force the solution vector to have the prescribed weight), and β\beta, mapping any MQ instance to an MLD instance (via systems put in a suitable standard form). After making β\beta one-to-one by appending equations that encode the original instance's coefficients, they proved MLD and MQ polynomial-time isomorphic. This equivalence makes concrete three research questions, which are the subject of this record: what the special-form systems in the image of α\alpha look like and whether they are easier than generic MQ (a polynomial-time algorithm for all image systems would collapse MQ, and hence both families, to P); dually what structure the codes in the image of β\beta carry; and how to model, precisely and in these algebraic languages, the problem of extracting secret keys from public keys. For context on tools: algebraic attacks on such questions typically rewrite the problem as a polynomial system and solve it with Gröbner bases (multivariate generalizations of Gaussian elimination), whose cost is governed by quantities such as the degree of regularity (the degree at which generic polynomial-system solving stabilizes); the follow-up literature below also uses invariants like the square of a code (the span of component-wise products of its codewords) and graded Betti numbers of the homogeneous coordinate ring of a shortened dual code.

Problem Statement

For the polynomial-time reductions α\alpha: MLD→\toMQ and β\beta: MQ→\toMLD of Meneghetti–Pellegrini–Sala (arXiv:2109.05806), determine whether the equivalence between the two problems transfers computational or cryptanalytic advantage between the code-based and multivariate post-quantum families. Concretely, the source poses three linked questions whose common objective is this transfer-of-advantage question: (1) Characterize the image of α\alpha (and of the composition α∘β\alpha\circ\beta): what structural and algebraic properties do the quadratic systems produced from MLD instances have, and do these special-form systems admit exact or heuristic algorithms asymptotically faster than those available for arbitrary MQ instances? In particular, this should be studied for MLD instances arising from real code-based cryptosystems, where the parity-check matrix hides a permuted algebraic code — e.g. the binary irreducible Goppa codes underlying Classic McEliece public keys. (2) Dually, characterize the image of β\beta (and of β∘α\beta\circ\alpha): do the families of codes produced by these reductions carry hidden algebraic structure exploitable by decoding algorithms, and what is revealed by mapping MQ instances originating from masked multivariate cryptosystems (public quadratic systems with a secret layered structure, as in the Oil-and-Vinegar family exemplified by Rainbow) through β\beta? (3) Formalize and analyze the precise computational problem of recovering the private key from the public key in code-based and multivariate cryptosystems in these algebraic languages: rather than naively applying the reductions, model the exact complexity of extracting the secret structure (such as the hidden Goppa code in a Classic McEliece public key, or the secret-layer structure of an Oil-and-Vinegar-type public key) from the public key, and assess whether α\alpha and β\beta yield new attack strategies or complexity-theoretic insight into key recovery versus solving generic instances. These three directions are independent and each is posed on its own: (1) asks for a structural and algebraic characterization of the image systems together with an exact-or-heuristic asymptotic-complexity verdict relative to arbitrary MQ; (2) asks for a characterization of the codes in the reverse-reduction image together with a statement of what that structure reveals about masked multivariate public keys; and (3) asks for a formal complexity-theoretic model of the key-recovery problem together with its relation to generic-instance solving. Note on currency: Rainbow itself has been broken by a dedicated key-recovery attack (Beullens 2022), so the multivariate instances in (2) and (3) are now to be read as the surviving masked-multivariate schemes (e.g. modern UOV descendants), while the code-based questions and the general formalization of (3) are unaffected.

References

  1. Alessio Meneghetti, Alex Pellegrini, Massimiliano Sala, 'On the equivalence of two post-quantum cryptographic families', Annali di Matematica Pura ed Applicata, 2022. DOI: 10.1007/s10231-022-01267-x, arXiv:2109.05806, https://arxiv.org/abs/2109.05806
  2. Alessio Caminata, Ryann Cartor, Alessio Meneghetti, Rocco Mora, Alex Pellegrini, 'Quadratic Modelings of Syndrome Decoding', Post-Quantum Cryptography (LNCS), 2025. DOI: 10.1007/978-3-031-86599-2_2, arXiv:2412.04848, https://arxiv.org/abs/2412.04848
  3. Ward Beullens, 'Breaking Rainbow Takes a Weekend on a Laptop', IACR Cryptology ePrint Archive 2022/214, 2022, https://eprint.iacr.org/2022/214
  4. Alain Couvreur, Rocco Mora, Jean-Pierre Tillich, 'A new approach based on quadratic forms to attack the McEliece cryptosystem', arXiv:2306.10294, 2023, https://arxiv.org/abs/2306.10294
  5. Rocco Mora, 'On the matrix code of quadratic relationships for a Goppa code', Advances in Mathematics of Communications, 2025. DOI: 10.3934/amc.2024026, https://arxiv.org/abs/2310.20497
  6. Hugues Randriambololona, 'The syzygy distinguisher', arXiv:2407.15740, 2024, https://arxiv.org/abs/2407.15740
  7. Axel Lemoine, Rocco Mora, Jean-Pierre Tillich, 'Understanding the new distinguisher of alternant codes at degree 2', Designs, Codes and Cryptography, 2025. DOI: 10.1007/s10623-025-01626-8, https://doi.org/10.1007/s10623-025-01626-8
  8. Axel Lemoine, 'The Tangent Space Attack', arXiv:2505.10184, 2025, https://arxiv.org/abs/2505.10184
  9. E. Berlekamp, R. McEliece, H. van Tilborg, 'On the inherent intractability of certain coding problems (Corresp.)', IEEE Transactions on Information Theory, 1978. DOI: 10.1109/TIT.1978.1055873, https://doi.org/10.1109/TIT.1978.1055873
  10. Jean-Charles Faugère, Valerie Gauthier-Umana, Ayoub Otmani, Ludovic Perret, Jean-Pierre Tillich, 'A Distinguisher for High-Rate McEliece Cryptosystems', IEEE Transactions on Information Theory, 2013. DOI: 10.1109/TIT.2013.2272036, https://doi.org/10.1109/TIT.2013.2272036
  11. Latifa Mostari, Alban Goupil, Abdelmalik Taleb-Ahmed, 'A Survey of Structural Attacks on Post-Quantum Cryptosystems Based on Goppa Codes: Evolution, Scope, and Impact on their Variants in the Hamming Metric', Archives of Computational Methods in Engineering, 2026. DOI: 10.1007/s11831-026-10567-x, https://doi.org/10.1007/s11831-026-10567-x