Paper 2026/1630
Quasipolynomial Cryptanalysis of the McEliece Cryptosystem (or: PIR Meets McEliece)
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.
BibTeX
@misc{cryptoeprint:2026/1630,
author = {Ashrujit Ghoshal and Yuval Ishai and Aayush Jain and Nuozhou Sun},
title = {Quasipolynomial Cryptanalysis of the {McEliece} Cryptosystem (or: {PIR} Meets {McEliece})},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1630},
year = {2026},
url = {https://eprint.iacr.org/2026/1630}
}