The cipher nobody deployed
In early 1978, Robert McEliece at Caltech’s Jet Propulsion Laboratory in Pasadena published a technical report on a public-key cryptosystem built on error-correcting codes. The mathematics was sound. The keys were the size of a short novel. That same month, RSA’s creators submitted a paper with keys compact enough to type in a terminal. RSA became the foundation of internet security. McEliece’s cryptosystem spent forty-seven years unbroken and undeployed.
On March 11, 2025, the National Institute of Standards and Technology announced the selection of HQC — Hamming Quasi-Cyclic — as its fifth post-quantum cryptographic standard, seven months after publishing its first three post-quantum algorithms and declaring the competition’s primary phase complete. HQC is a code-based algorithm: a direct descendant of McEliece’s 1978 idea, built on the same mathematical foundation — the difficulty of decoding random linear codes — but finally freed of the key-size problem that made the original undeployable.
The improvement came from structural algebra. McEliece used Goppa codes — a class with strong security properties but keys that ran to hundreds of kilobytes. A team including Philippe Gaborit at the University of Limoges and Gilles Zémor at the University of Bordeaux built HQC on quasi-cyclic codes: structures with a repeating algebraic symmetry that compresses the same mathematical hardness into keys a few kilobytes long. Where Classic McEliece needed the storage of a small document per key, HQC fits inside a standard TLS handshake.
The obvious question is why NIST needed a fifth algorithm at all. Its first four — ML-KEM, ML-DSA, SLH-DSA, and FN-DSA — were sufficient for migration. But three of the four are built on lattice problems: the hardness of certain geometric puzzles in high-dimensional space. Lattice cryptography looks resistant to quantum attacks, but “looks resistant” is not the same as “proven resistant,” and a structural weakness in one lattice scheme tends to cast shadows across the others. Dustin Moody, who led the post-quantum standardization project, put it plainly: HQC was chosen to provide “a fallback option to address potential vulnerabilities in ML-KEM.” Code-based cryptography uses entirely different mathematics. If lattice cryptography fails, code-based cryptography survives it.
The mathematical tradition HQC draws from runs back to Shannon’s 1948 paper on communication theory, which established that reliable transmission through noisy channels was theoretically possible — the conceptual seed for every error-correcting code that followed. McEliece’s cryptosystem was the first to put those codes to work for secrecy rather than noise suppression. HQC carries that lineage forward. The draft standard is expected in 2026; the final version in 2027.
Robert McEliece died on May 8, 2019, in Pasadena, before NIST published any of the post-quantum standards his work influenced. His own algorithm, Classic McEliece, entered the competition and reached the fourth round before being passed over — its key sizes still unwieldy. HQC is not exactly the cipher he designed. The mathematics McEliece put on paper in 1978 is unbroken. Only the key size changed — and with it, forty-seven years of waiting.
Sources
- NIST Post-Quantum Cryptography Standardization — NIST — March 11, 2025 HQC selection announcement; competition overview.
- NIST Selects HQC as Backup Algorithm for Post-Quantum Encryption — OODAloop — Dustin Moody quote; rationale for mathematical diversity and non-lattice backup.
- NIST Selects HQC as Fifth Algorithm for Post-Quantum Encryption — Encryption Consulting — Code-based vs. lattice comparison; HQC technical background.
- Classic McEliece — classic.mceliece.org — Key size characteristics of the original McEliece scheme.
- Robert McEliece — Wikipedia — Biography, Caltech/JPL affiliation, May 8, 2019 death.