Dr. Sarah ChenWhat Is McEliece Cryptography?
McEliece is a public-key encryption scheme proposed by Robert McEliece in 1978, making it the oldest post-quantum cryptographic proposal still in active consideration. Its security rests on a problem from coding theory: decoding a random linear error-correcting code is NP-hard in general. With the right structured code (Goppa codes), the scheme provides a trapdoor: the legitimate key holder can decode efficiently, but an attacker with only the public key cannot.
McEliece predates the quantum computing threat by over a decade. It was not designed as a response to Shor's algorithm. It just happens to use a mathematical problem that Shor's algorithm does not attack. The problem of decoding a general linear code has no periodic structure, no group homomorphism, and no algebraic shortcut that quantum computers can exploit. This is why a proposal from 1978 is still being seriously analyzed in 2024.
The scheme works as follows: the private key is an efficiently decodable Goppa code (a code that can correct up to t errors). The public key is a scrambled, permuted version of the generator matrix for that code, which looks like a random linear code to an observer who does not know the scrambling. Encryption adds a random error vector with weight at most t to the encoded message. Decryption strips the scrambling, decodes the errors using the private Goppa code structure, and recovers the message.
45 Years Without a Break: The Security Track Record
The original McEliece parameters (1,024-bit Goppa codes, t = 50) were broken in 2008 by information set decoding (ISD) attacks that brought the effective security below 80 bits. This was not a structural break of the scheme. It was a parameter inadequacy. Scaling the parameters restores security.
Classic McEliece, the NIST candidate submission, uses parameters chosen to provide 128-bit security against the best known ISD attacks: a [6960, 5413] binary Goppa code with t = 119 for the smallest parameter set (mceliece348864), and a [6960, 5413, 119] code for mceliece460896 at approximately 128-bit security.
No structural attack against McEliece with properly chosen Goppa codes has been published in 45 years of analysis. This is a remarkable track record. Compare it to elliptic curve cryptography, which is roughly 30 years old, or RSA, where the factoring record has been pushed incrementally by algorithmic improvements. McEliece's hardness has remained stable across multiple generations of cryptographic research.
The security confidence is high enough that McEliece proponents argue it should be considered more conservative than lattice-based schemes, which have a shorter cryptanalysis history and more active attack improvements. The post-quantum cryptography guide discusses this diversity argument in the context of portfolio selection.
The Key Size Problem
Classic McEliece's security conservatism comes at a severe cost. Public key sizes are orders of magnitude larger than any other post-quantum scheme:
- mceliece348864: 261,120-byte public key, 128-byte ciphertext, approximately 128-bit security.
- mceliece460896: 524,160-byte public key, 188-byte ciphertext, approximately 128-bit security (higher assurance).
- mceliece6688128: 1,044,992-byte public key, 240-byte ciphertext, 192-bit security.
- mceliece8192128: 1,357,824-byte public key, 240-byte ciphertext, 256-bit security.
Compare this to ML-KEM-512: 800-byte public key at the same 128-bit security level. McEliece-460896 requires 655x more space for its public key than ML-KEM-512. Note that ciphertext sizes are small (128 to 240 bytes), because encryption just adds an error vector to an encoded message. The cost is entirely in the public key.
This asymmetry creates a practical barrier for almost every network protocol. A TLS handshake that includes a 524KB public key requires multiple TCP packets and increases handshake latency significantly. For comparison, a typical TLS 1.3 handshake with X25519 fits in under 3KB total. Certificate chains, OCSP responses, and session tickets would all need to carry this overhead.
Why NIST Did Not Standardize McEliece as a Primary Recommendation
NIST's evaluation criteria for post-quantum standards explicitly included security, performance, and "characteristics affecting implementation and deployment." Key size falls under the third criterion. NIST explicitly noted in its Round 3 report that Classic McEliece's security and design are sound, but that the public key sizes "present significant challenges for many applications."
NIST selected ML-KEM (KYBER) as its primary key encapsulation standard because it provides 128-bit security with 800-byte public keys and fast operations. The 655x key size reduction is not a small optimization. It is the difference between a scheme that can be deployed in existing infrastructure and one that requires redesigning storage, transmission, and processing systems.
Classic McEliece was not standardized as a primary recommendation, but it remains under consideration as a backup candidate. NIST's position is that portfolio diversity matters and that if lattice problems are someday broken, a code-based alternative should be ready. The backup candidates, including BIKE and HQC, offer better key sizes than Classic McEliece. But Classic McEliece's 45-year track record gives it a security conservatism argument that the newer structured-code schemes cannot match. See the BIKE and HQC explainer for the current status of code-based backup candidates.
How McEliece Compares to Other Code-Based Schemes
The 45-year security of McEliece comes specifically from using binary Goppa codes, which have resisted all known algebraic attacks. Structured code variants (quasi-cyclic, quasi-dyadic) have repeatedly been broken when the structure was exploited to reduce the decoding problem to a smaller effective dimension.
BIKE and HQC achieve small key sizes by using quasi-cyclic codes, which introduce algebraic structure. This structure is what enables 1,541-byte public keys instead of 524KB. The question is whether that algebraic structure introduces attack surfaces that classic Goppa codes do not have. The security analysis for quasi-cyclic code schemes is substantially less mature than for Goppa code McEliece.
This is the fundamental tension: security conservatism argues for Classic McEliece (45 years, no structural attacks), while practicality argues for BIKE or HQC (modern key sizes, but shorter analysis history). NIST's response is to standardize the lattice schemes as primary and keep the code-based schemes as backups pending more analysis.
Where McEliece Is Appropriate
Classic McEliece is the correct choice in scenarios where key size is not a constraint and the priority is maximizing security margin:
Long-term data encryption vaults. Encrypting data that must remain confidential for 50 or more years, stored in systems where a 524KB public key can be stored once and reused. Key distribution is a one-time setup cost. The ciphertext (128 bytes for mceliece460896) is small.
Air-gapped systems with infrequent key exchange. Systems that exchange keys quarterly or annually, where the bandwidth cost of a large public key is irrelevant. Intelligence and defense applications sometimes fall into this category.
Applications requiring the longest-established security track record. If the threat model requires a post-quantum scheme that has been analyzed by the widest possible community over the longest time period, McEliece's 45-year history is unmatched.
For blockchain infrastructure, McEliece's key sizes make it impractical for on-chain key registration, transaction signing, or any operation where public keys appear in block data. Even storing 524KB public keys in smart contract state would consume hundreds of thousands of gas units at current Ethereum pricing. The quantum-safe smart contracts discussion covers practical key size constraints in on-chain environments.
Summary
McEliece (1978) is the oldest post-quantum cryptographic proposal, with 45 years of cryptanalysis without a structural break. Its public keys for 128-bit security range from 261KB to 524KB, roughly 655 times larger than ML-KEM-512's 800-byte keys. NIST did not standardize it as a primary recommendation due to these key sizes, but it remains a backup candidate and the correct choice for applications with long time horizons, infrequent key exchange, and no bandwidth constraints. For practical deployments, BIKE and HQC offer code-based security with 3-order-of-magnitude smaller keys at the cost of shorter cryptanalysis history.
