Classic McEliece: The Inconvenient Veteran of Post-Quantum Cryptography

Introduction

When people talk about post-quantum cryptography, the same names come up almost every time: ML-KEM, ML-DSA, SLH-DSA. These NIST standards are new, modern and mostly built on lattice problems. They are the present, and they will stay that way for the foreseeable future.

And then there is Classic McEliece.

Robert McEliece introduced the scheme in 1978. Nobody was talking about "post-quantum" yet, quantum computers existed only on paper, and the internet didn't even have its modern name. Since then, dozens of research papers have tried to break it, and none has succeeded. In more than 45 years, the security margin against classical attacks has moved by less than one percent.

This isn't marketing. It's the documented history of the scheme.

Classic McEliece is not the most glamorous algorithm in the PQC world. Its public keys are huge, between 261 KB and 1.35 MB depending on the parameter set, and critics usually bring that up first. But if you only look at key size, you miss the bigger picture. Classic McEliece is the most conservative and longest-studied KEM in post-quantum cryptography, and security authorities explicitly recommend it. These include the BSI in its TR-02102-1 (January 2026) and the Dutch NLNCSA.

This article looks at why it is still relevant, and why that may be precisely because of these qualities.

Deep Dive

The Foundation: Error-Correcting Codes as a Basis for Security

To understand Classic McEliece, we need a short detour into coding theory. This branch of mathematics was originally developed for a completely different problem: transmitting data reliably over noisy channels.

The basic idea is to add redundant information to a message, which is what's called a code. The receiver can then detect and correct transmission errors, even if some bits were flipped along the way. Claude Shannon laid the theoretical groundwork in 1948. In 1978, Robert McEliece asked a different question: what if this structure were used for encryption instead of error correction?

Classic McEliece relies on the fact that decoding a random linear code is, in general, extremely hard. The best known attacks belong to a family called Information-Set Decoding (ISD). Without access to the hidden mathematical structure, an attacker faces a problem that even quantum computers cannot solve efficiently. Grover's algorithm only gives a quadratic speedup, which can be offset with moderately larger keys.

The private key is exactly this hidden structure: a binary Goppa code, which can be decoded efficiently. The public key shows that a code exists, but not which one.

Key Generation: The Heart of the System

A Goppa code is defined by two components.

The first is a monic irreducible polynomial g of degree t over a finite field $\mathbb{F}_{2^m}$. Irreducible means the polynomial can't be factored into simpler polynomials, much like a prime number can't be split into smaller factors.

The second is a sequence α of n pairwise distinct elements from the same field.

These two components define a parity-check matrix H. The public key is this matrix in systematic form (I ∣ T), where I is an identity matrix and T is the part that actually gets published.

One technical detail: the "f" variants, such as mceliece8192128f, use a semi-systematic form. This makes key generation succeed more reliably and run faster, which matters for implementations that have to generate many key pairs.

The private key has a useful property that is often overlooked. It can be compressed to a seed of 32 to 40 bytes, from which all required polynomials and matrices can be reconstructed deterministically. Next to the huge public key, that's a real practical advantage.

Encapsulation: A Syndrome Instead of Encryption

Encapsulation works quite differently from what you might know from RSA or elliptic curves. No key is wrapped and sent. Instead:

1. The sender generates a random error vector e of length n with a Hamming weight of exactly t. In other words, e contains exactly t ones and zeros everywhere else.
2. The ciphertext is C=He, the product of the public parity-check matrix and the error vector. In coding theory, this is called the syndrome of e.
3. The session key K is derived by hashing e and C.

Without the private Goppa code, recovering e from the syndrome C is computationally infeasible, and so is recovering the session key. This is exactly the decoding problem described above.

Decapsulation: Deterministic and Error-Free

The receiver uses g and α from the private key to run the Goppa decoding algorithm, recovers e from C and derives the same session key K.

Classic McEliece is deterministic and never fails to decrypt a valid ciphertext. Lattice-based schemes behave differently here: ML-KEM has a tiny but non-zero failure probability, which is kept negligible through careful parameter choices. Classic McEliece simply doesn't have this problem.

Security Analysis: Decades of Cryptanalysis

The security of Classic McEliece rests on three pillars.

A stable hardness assumption: since 1978, all improvements in ISD attacks combined have changed the key size needed for a given security level by less than one percent. That is remarkably stable. Lattice-based schemes like ML-KEM, by comparison, have only existed in their modern form since the early 2000s, so their long-term security margin is naturally less proven.

Quantum resistance: Grover's algorithm reduces attack complexity asymptotically to its square root. For Classic McEliece 8192128, the parameter set with the highest security level, this reduction is already accounted for in the choice of key size.

IND-CCA2 security: thanks to the KEM construction, the scheme is protected against adaptive chosen-ciphertext attacks, the strongest attacker model that matters in practice.

Strengths, Weaknesses and an Uncomfortable Trade-Off

Every cryptographic decision involves trade-offs, and Classic McEliece shows this more clearly than most.

What Classic McEliece does well

The ciphertexts are tiny, between 128 and 208 bytes depending on the parameter set, and fit easily into a single network packet. When many messages are exchanged with the same key pair, the cost of sending the large public key pays off quickly.

It is also very hardware-friendly. Because the algorithm is built on binary matrix operations, it runs extremely fast on FPGAs, which can be a deciding factor for embedded systems and hardware security modules.

The obvious weakness

The public keys are large. Very large: 261 KB for mceliece348864 and up to 1.35 MB for mceliece8192128. That is why Classic McEliece is a poor fit for protocols like TLS. A handshake that has to transfer a public key of more than a megabyte simply doesn't scale.

One frequently discussed workaround is caching public keys. ISPs or network infrastructure could store them and only send the compact ciphertexts. That works in controlled environments, but it also turns Classic McEliece into a scheme for specific use cases rather than a general replacement for classical KEMs.

Standardisation Status: Why Classic McEliece Still Matters

NIST did not select Classic McEliece as a final standard and moved it to a fourth round for further evaluation instead. That sounds like a setback, but the full picture is more nuanced.

The BSI lists it as a recommended algorithm in its technical guideline TR-02102-1. The Dutch NLNCSA explicitly recommends it for applications where maximum security matters more than efficiency. The Classic McEliece team has also submitted a proposal for ISO standardisation (ISO/IEC 18033-2), and ISO has approved a preliminary work item for PQC KEMs that explicitly includes Classic McEliece.

Within the PQC ecosystem, Classic McEliece serves as a security anchor. Lattice-based schemes share related mathematical foundations, so a structural weakness found in one could affect the others. Code-based cryptography rests on completely different mathematics, so an attack that breaks ML-KEM would leave Classic McEliece untouched.

This isn't a purely theoretical concern. It's the principle of cryptographic diversification, and the same reason hybrid schemes are deployed today instead of relying on a single algorithm.

Conclusion: The Awkward Veteran Has Its Place

Classic McEliece isn't the right algorithm for every use case. If you're securing TLS handshakes or resource-constrained IoT devices, there are better options. The key sizes are a real drawback, and there's no way around that.

But if you need conservative, well-tested security for long-lived data, critical infrastructure or scenarios where bandwidth matters less than cryptographic caution, Classic McEliece is a strong choice. It has withstood more than 45 years of cryptanalysis without a single structural weakness being found.

That's a hard track record to beat.