Paper 2026/1630 Original: eprint.iacr.org/2026/1630 ↗

Quasipolynomial Cryptanalysis of the McEliece Cryptosystem (or: PIR Meets McEliece)

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 and a heuristic \(n^{{\mathcal O}(\log n)}\)-time key-recovery attack that outputs an equivalent decryption key. While the decryption attack is not concretely efficient, the key-recovery attack is much closer to the distinguisher and may be relevant to NIST security levels.