The DOI matches its Crossref record, with a small difference in title or year; 1 of the 1 references it cites were found in a registry or an index.
On the matrix code of quadratic relationships for a Goppa code
Open accessAbstract
In this article, we continue the analysis started in [8] for the matrix code of quadratic relationships associated with a Goppa code. We provide new sparse and low-rank elements in the matrix code and categorize them according to their shape. Thanks to this description, we prove that the set of rank 2 matrices in the matrix codes associated with square-free binary Goppa codes, i.e. those used in the Classic McEiece cryptosystem, is much larger than what is expected, at least in the case where the Goppa polynomial degree is 2. We build upon the algebraic determinantal modeling introduced in [8] to derive a structural attack on these instances. Our method can break in just a few seconds some recent challenges to recover the key of the McEliece cryptosystem, consistently reducing their estimated security level. We also provide a general method, valid for any Goppa polynomial degree, to transform a generic pair of support and multiplier into a pair of support and Goppa polynomial.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source says what the claim attributes to it.
In the citing paper
“During the fourth round, there has been significant progress in cryptanalysis techniques that are applicable to key recovery and the related problem of distinguishing a Goppa code from a random linear code [46, 66-69].”
From Status report on the fourth round of the NIST post-quantum cryptography standardization process (2025) · cites this paper as [69]
The cited source says what the claim attributes to it.
In the citing paper
“Nonetheless, algebraic attacks that target the structure of Goppa codes and achieve either key recovery or a distinguisher from a random linear code have remained an active area of research [46, 65-69].”
From Status report on the fourth round of the NIST post-quantum cryptography standardization process (2025) · cites this paper as [69]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
On insecurity of cryptosystems based on generalized Reed-Solomon codes
SIDELNIKOV, V. M., & SHESTAKOV, S. O. (1992) · Discrete Mathematics and Applications · doi:10.1515/dma.1992.2.4.439 · Cited by 235
Flagged first, then by citations
Research works printed but not linked: 28
- Daniel J. Bernstein. Grover vs. McEliece. In Nicolas Sendrier, editor, Post-Quantum Cryptography 2010, volume 6061 of LNCS, pages 73-80. Springer, 2010.
- Anja Becker, Antoine Joux, Alexander May, and Alexander Meurer. Decoding random binary linear codes in 2 n{20 : How 1 `1 " 0 improves information set decoding. In Advances in Cryptology -EUROCRYPT 2012, LNCS. Springer, 2012.
- Leif Both and Alexander May. Optimizing BJMM with Nearest Neighbors: Full Decod- ing in 2 2{21n and McEliece Security. In WCC Workshop on Coding and Cryptography, September 2017.
- Magali Bardet, Rocco Mora, and Jean-Pierre Tillich. Polynomial time key-recovery attack on high rate random alternant codes. CoRR, abs/2304.14757, 2023. · arXiv
- Anne Canteaut and Florent Chabaud. A new algorithm for finding minimum-weight words in a linear code: Application to McEliece's cryptosystem and to narrow-sense BCH codes of length 511. IEEE Trans. Inform. Theory, 44(1):367-378, 1998.
- Nicolas Courtois, Matthieu Finiasz, and Nicolas Sendrier. How to achieve a McEliece- based digital signature scheme. In Advances in Cryptology -ASIACRYPT 2001, vol- ume 2248 of LNCS, pages 157-174, Gold Coast, Australia, 2001. Springer.
- Alain Couvreur, Rocco Mora, and Jean-Pierre Tillich. A new approach based on qua- dratic forms to attack the McEliece cryptosystem. In International Conference on the Theory and Application of Cryptology and Information Security, pages 3-38. Springer, 2023.
- Il'ya Dumer. Two decoding algorithms for linear codes. Probl. Inf. Transm., 25(1):17- 23, 1989.
- Arne Dür. The automorphism groups of Reed-Solomon codes. Journal of Combinato- rial Theory, Series A, 44:69-82, 1987.
- Jean-Charles Faugère, Valérie Gauthier, Ayoub Otmani, Ludovic Perret, and Jean- Pierre Tillich. A distinguisher for high rate McEliece cryptosystems. In Proc. IEEE Inf. Theory Workshop-ITW 2011, pages 282-286, Paraty, Brasil, October 2011.
- Sudhir R Ghorpade and Christian Krattenthaler. The Hilbert series of Pfaffian rings. In Algebra, Arithmetic and Geometry with Applications: Papers from Shreeram S. Abhyankar's 70th Birthday Conference, pages 337-356. Springer, 2004.
- Ghazal Kachigar and Jean-Pierre Tillich. Quantum information set decoding algo- rithms. In Post-Quantum Cryptography 2017, volume 10346 of LNCS, pages 69-89, Utrecht, The Netherlands, June 2017. Springer.
- Pierre Loidreau and Nicolas Sendrier. Weak keys in the McEliece public-key cryp- tosystem. IEEE Trans. Inform. Theory, 47(3):1207-1211, 2001.
- Robert J. McEliece. A Public-Key System Based on Algebraic Coding Theory, pages 114-116. Jet Propulsion Lab, 1978. DSN Progress Report 44.
- Alexander May, Alexander Meurer, and Enrico Thomae. Decoding random linear codes in Op2 0.054n q. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology -ASIACRYPT 2011, volume 7073 of LNCS, pages 107-124. Springer, 2011.
- Alexander May and Ilya Ozerov. On computing nearest neighbors with applications to decoding of binary linear codes. In E. Oswald and M. Fischlin, editors, Advances in Cryptology -EUROCRYPT 2015, volume 9056 of LNCS, pages 203-228. Springer, 2015.
- Rocco Mora. Algebraic techniques for decoding Reed-Solomon codes and cryptanalyz- ing McEliece-like cryptosystems. PhD thesis, Sorbonne Université, 2023.
- Irene Márquez-Corbella and Ruud Pellikaan. Error-correcting pairs for a public-key cryptosystem. CBC 2012, Code-based Cryptography Workshop, 2012. Available on http://www.win.tue.nl/ ~ruudp/paper/59.pdf.
- Florence J. MacWilliams and Neil J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, Amsterdam, fifth edition, 1986.
- Rocco Mora and Jean-Pierre Tillich. On the dimension and structure of the square of the dual of a goppa code. Designs, Codes and Cryptography, 91(4):1351-1372, 2023.
- N. Patterson. The algebraic decoding of Goppa codes. IEEE Trans. Inform. Theory, 21(2):203-207, 1975.
- Eugene Prange. The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory, 8(5):5-9, 1962.
- Hugues Randriambololona. On products and powers of linear codes under componen- twise multiplication. In Algorithmic arithmetic, geometry, and coding theory, volume 637 of Contemp. Math., pages 3-78. Amer. Math. Soc., Providence, RI, 2015.
- Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 21(2):120-126, 1978.
- Nicolas Sendrier. Finding the permutation between equivalent linear codes: The sup- port splitting algorithm. IEEE Trans. Inform. Theory, 46(4):1193-1203, 2000.
- Nicolas Sendrier. On the use of structured codes in code based cryptography. In L. Storme S. Nikova, B. Preneel, editor, Coding Theory and Cryptography III, pages 59-68. The Royal Flemish Academy of Belgium for Science and the Arts, 2010.
- Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factor- ing. In S. Goldwasser, editor, FOCS, pages 124-134, 1994.
- Jacques Stern. A method for finding codewords of small weight. In G. D. Cohen and J. Wolfmann, editors, Coding Theory and Applications, volume 388 of LNCS, pages 106-113. Springer, 1988.
Cited by
Sorted by citations
Status report on the fourth round of the NIST post-quantum cryptography standardization process
Alagic, G., Bros, M., Ciadoux, P., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Liu, Y.-K., Miller, C., et al. (2025) · doi:10.6028/nist.ir.8545 · Cited by 211
Metadata
- Authors
- Mora, R.
- Corresponding author
- Mora, Rocco
- ORCID
- Mora, Rocco
- Venue
- Advances in Mathematics of Communications
- Published
- 2025
- Volume
- 19
- Issue
- 3
- Pages
- 829-852
- ISSN
- 1930-5338 (ISSN-L)
- 1930-5346
- OpenAlex
- W4399785204
- Cited by
- 3
- References
- 1
- Citations by year
- 2026: 3
- FWCI
- 0.44
- Type
- journal article
- Language
- en
- Open access
- diamond
- doi.org
- Licence
- cc-by
- Locations
- Advances in Mathematics of Communications (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion, cc-by)
- HAL (submittedVersion, cc-by)
- arXiv (Cornell University) (cc-by)
- Topics
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Coding theory and cryptography
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Physical Sciences › Computer Science › Computer Networks and Communications › Cryptography and Data Security
- Keywords
- Goppa codes, McEliece cryptosystem, structural attacks, key recovery, binary Goppa codes, code-based cryptography
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
