# Classic McEliece: The 47-Year-Old PQC Candidate **Source**: https://quantumsequrity.com/blog/classic-mceliece-deep-dive **Category**: PQC Algorithms --- [← Back to Blog](../../blog.html) PQC Algorithms # Classic McEliece: The 47-Year-Old PQC Candidate 10 min read In 1978, Robert J. McEliece published a paper called "A Public-Key Cryptosystem Based on Algebraic Coding Theory" in the JPL DSN Progress Report. RSA had been published the year before. Diffie-Hellman key exchange was two years old. Public-key cryptography was new and the field had no idea which mathematical foundations would last. McEliece proposed using error-correcting codes called Goppa codes as a hard-problem foundation. The scheme he described, with minor parameter updates, is still considered secure 47 years later. That continuity is unusual. Most cryptographic schemes from the late 1970s have been broken outright (knapsack-based schemes), abandoned (Rabin), or made obsolete by efficiency improvements (early RSA modes). McEliece survived because the underlying problem (decoding random linear codes) is genuinely hard, even on a quantum computer. The price for that survival is enormous public keys, more than 1 megabyte for the highest-security parameter set. This article walks through what Classic McEliece is, why its public keys are so large, why NIST kept it on the table for 47 years, and where it fits in a 2026 post-quantum deployment. ## The Library With Locked Bookshelves Imagine a library where every book is a number. To send someone a secret message, you pick the page and shelf where their book lives. The owner of the library has a master index that lets them go straight to that page in seconds. An outsider has to search the entire library, shelf by shelf, to find the book. The library is the public key. The master index is the private key. The search difficulty is the security. McEliece's idea was: pick a special kind of error-correcting code (a Goppa code) where the owner has an efficient decoding algorithm, and an outsider sees only a scrambled-looking code where decoding is NP-hard. The "library" (public key) is huge because it must encode all the structural information of the code without revealing the trapdoor. The decoding speedup the owner gets is dramatic enough that practical use is feasible despite the bandwidth cost. ## The Goppa Code Foundation Goppa codes were introduced by Valery Goppa in 1970 as a class of algebraic-geometric codes with strong error-correction properties. McEliece used a class of binary Goppa codes as his trapdoor in the 1978 paper. The scheme works because: 1. **Decoding random linear codes is NP-hard** (Berlekamp-McEliece-van Tilborg, 1978). This is the worst-case problem. 2. **Decoding Goppa codes is easy if you know the structure** (the patterson algorithm gives O(n^2) decoding). 3. **A scrambled Goppa code looks random** to anyone without the trapdoor, so the worst-case hardness applies. The security of Classic McEliece rests on point 3, the indistinguishability of a scrambled Goppa code from a random linear code. This has been studied for 47 years. There have been some attacks on related code families (Reed-Solomon, Reed-Muller), but plain binary Goppa codes have resisted all of them. ### Why Quantum Does Not Break It Shor's algorithm breaks RSA and ECC because their hard problems (factoring and discrete log) have hidden periodic structure that the quantum Fourier transform can find. The hard problem for McEliece (random linear code decoding) has no such structure. The best known quantum attack on McEliece is information-set decoding sped up by Grover's algorithm, which gives only a square-root speedup. The 256-bit security parameter set still provides 128 bits of post-quantum security against this attack, the same trade-off as AES-256. This is why McEliece sits in the "conservative" category of post-quantum schemes. It does not need a new mathematical assumption that emerged in the 2010s. It needs only the assumption that decoding random linear codes is hard, which has held since 1978. ## The Public Key Size Problem The catch is brutal: Classic McEliece public keys are huge. Here are the FIPS-style parameter sizes from the Round 4 submission: | Parameter set | Security level | Public key size | Ciphertext size | |------------------|------------------|-----------------|-----------------| | mceliece348864 | NIST Category 1 | 261,120 bytes | 96 bytes | | mceliece460896 | NIST Category 3 | 524,160 bytes | 156 bytes | | mceliece6688128 | NIST Category 5 | 1,044,992 bytes | 208 bytes | | mceliece6960119 | NIST Category 5 | 1,047,319 bytes | 194 bytes | | mceliece8192128 | NIST Category 5 | 1,357,824 bytes | 208 bytes | A megabyte public key is a problem. For comparison, ML-KEM-768 has a 1,184-byte public key. Any deployment scenario where the public key has to ship in-band with the handshake (TLS, IKE, signal-style messaging) is fundamentally hostile to McEliece. But for scenarios where the public key is fetched once and stored, the bandwidth cost amortises across many sessions. A long-running IPsec tunnel that establishes once and stays open for months pays the megabyte cost once. A document signing chain where the public key sits in a directory pays the cost on directory load, not per-signature. ### Ciphertext Sizes Are Tiny McEliece compensates with extremely small ciphertexts. At Category 5, the ciphertext is 208 bytes versus ML-KEM-1024's 1,568 bytes. For high-volume key encapsulation against a fixed public key (the "encrypted file shared with one recipient" pattern), McEliece's 208 bytes per file is competitive with ML-KEM. Only the upfront key delivery is painful. ## NIST's Treatment of Classic McEliece NIST's Round 4 (2022 onward) included Classic McEliece as an alternate KEM. The Round 4 alternates were the "non-lattice diversity" candidates, kept alive in case lattice schemes ever fell. McEliece, BIKE, and HQC were the three Round 4 KEMs. SIKE was eliminated in August 2022. In March 2025, NIST IR 8528 announced HQC as the Round 4 winner for non-lattice KEM standardisation. Classic McEliece was not standardised at that time, but NIST explicitly noted that the scheme remained "a strong conservative candidate" and that future standardisation discussion was possible. The reason HQC won over McEliece was practical: HQC's smaller key sizes made it deployable in protocols that McEliece could not fit into. That said, ISO/IEC 18033-2 (the international cipher catalogue) standardised a McEliece variant. CFRG (the IRTF crypto research group) has working drafts. McEliece is alive in standards bodies even though it does not have a NIST FIPS slot. ### Why NIST Kept It Through Round 4 NIST IR 8413 (the Round 3 final report) flagged Classic McEliece as the most conservative KEM candidate. Its assumption is the oldest, its cryptanalysis history is the longest, and its security has held up across more attack iterations than any other PQC candidate. If a future attack on lattices ever emerges, McEliece is the closest thing the community has to a "guaranteed safe" alternative. NIST keeps it on the table specifically because the cost of being wrong about lattices is enormous. ## Where Classic McEliece Lives in 2026 Real-world deployments are limited but exist: - **Niagara Networks** uses McEliece-style schemes in some military communications equipment. - **Several embedded HSM vendors** offer Classic McEliece as a non-FIPS alternative for customers who want pure-code KEM. - **Academic libraries** like libpqcrypto, pqcrypto-rust, and the Open Quantum Safe project ship reference implementations. - **OpenPGP draft extensions** include McEliece as one of the candidate post-quantum KEMs for long-term archival use. The deployment scenarios share a common shape: long-lived public keys, infrequent key rotation, large bandwidth budgets, and strong demand for non-lattice diversity. PGP-style encrypted email archives, defence-grade secure messaging with pre-shared key bundles, long-term file vaults. These are exactly the scenarios where the megabyte public key is acceptable. ## Classic McEliece in QNSQY QNSQY does not ship Classic McEliece in any tier as of 2026. The reason is operational: QNSQY is a file-encryption product where users routinely share encrypted files with new recipients. A megabyte public key per recipient creates a poor user experience. QNSQY's non-lattice diversity comes from [HQC](hqc-explained.html), which has 7 KB to 14 KB ciphertexts (still large compared to ML-KEM but two orders of magnitude smaller than McEliece). HQC is a NIST Round 4 winner, and shipping the standardised scheme over a non-standardised one matches QNSQY's "FIPS only" policy. If a customer with strict requirements (national security archive, classified document storage) needed Classic McEliece specifically, QNSQY's hybrid envelope format is extensible enough to accommodate a custom KEM. This is a Business tier conversation, not a default capability. ### Where McEliece Could Become Relevant Despite the bandwidth challenge, Classic McEliece could become relevant for QNSQY in specific scenarios. Long-term archival is the most plausible. A document archive with a 50-year retention requirement, where the recipient is fixed at encryption time and the public key is stored in a directory rather than transmitted with each operation, can absorb the megabyte cost. If a future cryptanalytic result weakens lattice or code-based schemes that are currently in the FIPS suite, having McEliece as the deepest fallback would be valuable. The 47-year cryptanalytic record is unmatched by any other post-quantum candidate. For now, the operational cost is too high relative to HQC's coverage of the same diversity slot. But the QNSQY architecture preserves the ability to add McEliece without forking the file format, which means the option remains open for future use cases that justify the bandwidth. ## The McEliece Lessons Three things to take away from 47 years of Classic McEliece: 1. **Old is good in cryptography**. RSA from 1977 is still secure (with parameter updates). McEliece from 1978 is still secure. The new schemes (lattice, isogeny) have not been studied for as long. A scheme that has survived 47 years of attack is more trustworthy than one that has survived 7. 2. **Size matters and so does survival**. McEliece pays a heavy bandwidth cost for its survival. NIST chose ML-KEM for bandwidth reasons even though McEliece has a stronger pedigree. The right scheme is the one that fits your operational profile, not necessarily the one with the longest history. 3. **Conservative diversity is non-negotiable**. NIST keeps McEliece, BIKE, and HQC alive because if lattices ever fall, the world cannot be left without a working KEM. The same logic applies to enterprise deployments: do not put all your post-quantum chips on lattices. For the broader picture on KEM choices, see [Hybrid Encryption Explained](hybrid-encryption.html), [ML-KEM Explained](ml-kem-explained.html), and [HQC Explained](hqc-explained.html). ## Frequently Asked Questions ### Why did NIST not standardise Classic McEliece? NIST chose HQC over Classic McEliece in March 2025 (IR 8528) primarily because HQC's smaller keys make it deployable in mainstream protocols. McEliece's megabyte public keys are too large for typical TLS or IKE handshakes. McEliece remains a strong candidate for niche use cases and may yet be standardised in a future round, but it lost the Round 4 KEM slot. ### Could a quantum computer break Classic McEliece? Not at standardised parameter sets. The best known quantum attack is information-set decoding sped up by Grover's algorithm, giving only a square-root speedup. The Category 5 parameter set retains 128 bits of post-quantum security against this attack, the same as AES-256. ### Has anyone tried to attack Classic McEliece? Continuously, for 47 years. Various attacks have targeted related code families (Reed-Solomon, Reed-Muller, Goppa codes with specific structures). None have broken the binary Goppa code variant that Classic McEliece uses. The cryptanalysis record is the longest of any post-quantum scheme. ### Why is the public key so much bigger than the ciphertext? The public key encodes the entire generator matrix of the (scrambled) Goppa code. For a code of length n with k information symbols and rate k/n, the generator matrix has k*(n-k) bits, which scales as O(n^2) for the parameters NIST chose. The ciphertext encodes only n bits of error-corrupted message. So the public key is quadratic in n while the ciphertext is linear, and that ratio is the price of using error-correcting codes as a trapdoor. ## Sources 1. McEliece, R. J. "A Public-Key Cryptosystem Based on Algebraic Coding Theory." DSN Progress Report 42-44, January-February 1978. https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF 2. NIST. "Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Process." NIST IR 8528, March 2025. https://csrc.nist.gov/pubs/ir/8528/final 3. Bernstein, D. J., Chou, T., Lange, T., et al. "Classic McEliece: conservative code-based cryptography." NIST PQC submission, October 2020. https://classic.mceliece.org/nist/mceliece-20201010.pdf 4. Berlekamp, E., McEliece, R., van Tilborg, H. "On the inherent intractability of certain coding problems." IEEE Transactions on Information Theory, 1978. https://ieeexplore.ieee.org/document/1055873 5. ISO/IEC 18033-2:2006. "Information technology - Security techniques - Encryption algorithms - Part 2: Asymmetric ciphers." https://www.iso.org/standard/37971.html 6. NIST. "Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process." NIST IR 8413, July 2022. https://csrc.nist.gov/pubs/ir/8413/final ## Related Articles - [HQC Explained](hqc-explained.html) - [ML-KEM Explained](ml-kem-explained.html) - [Lattice-Based Cryptography Explained](lattice-based-cryptography-explained.html) - [NIST FIPS Guide for Post-Quantum Standards](nist-fips-guide.html) - [What Is Post-Quantum Cryptography?](what-is-post-quantum-cryptography.html) --- ### Protect Your Data Before Q-Day Arrives QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats. [Try QNSQY](../../pricing.html)