Classic McEliece

Classic McEliece is a code-based key-encapsulation mechanism whose security rests on the difficulty of decoding a random-looking binary Goppa code. It descends directly from the cryptosystem Robert McEliece published in 1978, which makes it the oldest public-key encryption scheme still regarded as secure, and it was a NIST finalist that continued into the fourth round of the PQC standardization process.

#How it works

The public key is the generator (or parity-check) matrix of a binary Goppa code that has been scrambled so that it looks like a random linear code. Anyone can use it to add a fixed number of errors to a codeword, but only the holder of the secret key knows the underlying code structure and can run an efficient decoder to remove those errors. Classic McEliece uses the Niederreiter form of this idea, encoding the shared secret as a low-weight error vector and transmitting its syndrome as the ciphertext.

Two independent hardness assumptions protect it. Recovering the secret from the public key requires distinguishing a permuted Goppa code from a random one (a structural attack), and recovering a message requires decoding a random linear code (the syndrome decoding problem, which is NP-hard in the general case). Neither has yielded a practical attack for the recommended parameters in more than four decades of study. A quantum computer gains only the quadratic speedup of Grover-style search against the decoding problem, and parameters are sized with that margin already included.

The submission wraps a one-way encryption core in a Fujisaki-Okamoto style transform to reach IND-CCA2 security as a KEM. A design goal is that decryption never fails: unlike lattice and quasi-cyclic schemes, Classic McEliece has no decryption failure rate to analyze, which removes one class of chosen-ciphertext concern.

#Sizes and performance

The defining tradeoff is bandwidth. Public keys are very large, from roughly 261 kilobytes to over 1 megabyte, because the key is essentially a full code description. In exchange, ciphertexts are among the smallest of any post-quantum KEM, and encapsulation and decapsulation are fast. The shared secret is 32 bytes. Sizes below are in bytes, from the official specification.

Private keys are comparatively small, on the order of 6 to 14 kilobytes. The profile is the opposite of HQC and BIKE, the two quasi-cyclic code-based candidates, which cut key size to a few kilobytes at the cost of larger ciphertexts and a nonzero decryption failure rate. Full cross-scheme figures are in the algorithm comparison.

#NIST outcome and ISO track

Classic McEliece was named a finalist in the third round in 2020 and carried into a fourth evaluation round in 2022 alongside BIKE, HQC, and the isogeny scheme SIKE. In the fourth-round status report NIST IR 8545, published in March 2025, NIST selected HQC and declined to standardize both BIKE and Classic McEliece. The stated reason for Classic McEliece was practical rather than cryptographic: its multi-hundred-kilobyte public keys are awkward for protocols that transmit a fresh key per session, such as general web traffic. NIST recorded confidence in its security and noted that the design team is pursuing standardization through ISO, so the algorithm has a standardization path outside the NIST portfolio.

#Where the large keys fit

The size profile suits deployments that reuse a long-lived key and are dominated by many small messages, or that value maximum conservatism against a future cryptographically relevant quantum computer over minimum bandwidth. Because the underlying assumption is old and well studied, Classic McEliece is a frequent choice for defense against harvest now, decrypt later threats where a static recipient key is acceptable. It is implemented in liboqs and is commonly deployed in hybrid combination with a classical key exchange such as X25519, so that a break in either component alone does not compromise the session.

#Limitations

The public key size is the dominant constraint and rules the scheme out of latency-sensitive handshakes that negotiate a new key on every connection. Implementations must also generate keys and decode in constant time to avoid leaking the secret code structure through timing, and key generation is slower than encapsulation. These are engineering costs rather than security weaknesses, and they are the reason the scheme is positioned as a conservative option rather than a general-purpose default.