Quasipolynomial Cryptanalysis of the McEliece Cryptosystem (or: PIR Meets McEliece)
What a lovely hat
Is it made out of tin foil?
Paper 2026/1630
Quasipolynomial Cryptanalysis of the McEliece Cryptosystem (or: PIR Meets McEliece)
Ashrujit Ghoshal, IIT Madras
Yuval Ishai, Technion, AWS
Aayush Jain, Carnegie Mellon University
Nuozhou Sun, Carnegie Mellon University
Abstract
The McEliece code-based cryptosystem, utilizing binary Goppa codes, is the earliest public-key encryption scheme that is still considered post-quantum secure. We present a simple, classical quasipolynomial-time distinguisher for Goppa--McEliece in the asymptotic "Classic McEliece" regime: for code length $n$, extension degree $m=\Theta(\log n)$, Goppa degree $t=\Theta(n/\log n)$, and public-code dimension $k=\Theta(n)$, the algorithm runs in time $n^{{\mathcal O}(\log n)}$ and distinguishes the McEliece public key from the uniform distribution over $\mathbb F_2^{k\times n}$ with advantage $1-o(1)$. The distinguisher is not merely asymptotic: it applies to all Classic McEliece parameter sets considered in the NIST process and yields improved (though not yet practical) concrete attack estimates.
Our distinguishing attack originated from a failed attempt to construct doubly efficient private information retrieval (PIR) protocols from algebraic locally decodable codes, and can be intuitively explained from the PIR perspective. We extend this provable algorithm to a heuristic $n^{{\mathcal O}(\log n)}$-time ciphertext-decryption attack that recovers the message from a noisy codeword.
Metadata
Available format(s)
Category<br>Attacks and cryptanalysis
Publication info<br>Preprint.
Keywords<br>McEliececode based cryptoPIR
Contact author(s)
ashrujit @ cse iitm ac in<br>yuval ishai @ gmail com<br>aayushja @ andrew cmu edu<br>nuozhous @ andrew cmu edu
History
2026-08-10: approved
2026-08-07: received
See all versions
Short URL<br>https://ia.cr/2026/1630<br>License
CC BY
BibTeX<br>Copy to clipboard
@misc{cryptoeprint:2026/1630,<br>author = {Ashrujit Ghoshal and Yuval Ishai and Aayush Jain and Nuozhou Sun},<br>title = {Quasipolynomial Cryptanalysis of the {McEliece} Cryptosystem (or: {PIR} Meets {McEliece})},<br>howpublished = {Cryptology {ePrint} Archive, Paper 2026/1630},<br>year = {2026},<br>url = {https://eprint.iacr.org/2026/1630}
Note: In order to protect the privacy of readers, eprint.iacr.org<br>does not use cookies or embedded third party content.