Code-Based Cryptography
Code-based cryptography is a family of post-quantum cryptography whose security rests on the hardness of decoding random linear error-correcting codes, a problem that mathematicians have studied since the 1970s and still can’t solve efficiently, on a classical or a quantum computer. It’s the oldest and best-studied corner of post-quantum cryptography: the founding scheme, the McEliece cryptosystem, dates to 1978 and has never been practically broken. That long, quiet track record is its whole appeal, and it comes at a price that’s just as famous, keys that are enormous compared to everything else in the field. The family does key establishment (KEMs), and it’s the main non-lattice alternative to ML-KEM, which is why NIST reached into it for a backup standard.
The short version:
- Code-based cryptography secures data on the difficulty of decoding a random-looking error-correcting code, a foundation completely separate from the lattice math behind the primary standards.
- It’s a key-establishment family. There’s no widely standardized code-based signature scheme, so it doesn’t cover the signing side of the transition.
- It has the longest unbroken track record of any post-quantum family, going back to the McEliece cryptosystem in 1978.
- Its defining cost is size: code-based schemes have historically needed very large public keys, which limits where they can be deployed.
- Its strategic value is mathematical diversity. If lattice cryptography were ever weakened, a code-based backup would be unaffected, which is exactly why NIST selected the code-based KEM HQC in March 2025 to sit behind ML-KEM.
Think about how a scratched CD still plays. The disc stores every song wrapped in extra redundancy, so a player can reconstruct the music even after some of the bits are lost or flipped. That redundancy is an error-correcting code, and correcting errors is easy when you hold the key to the code’s structure and genuinely hard when you don’t. Code-based cryptography turns that gap into a lock. You publish a scrambled version of an error-correcting code that looks like random noise, and to send you a secret, someone deliberately garbles a message with a burst of errors. Anyone can add the errors. Only you, holding the private structure, can strip them back out and read what’s underneath. A quantum computer doesn’t give an attacker a shortcut through that.
How does code-based cryptography work?
Code-based cryptography builds its security on the syndrome decoding problem: given a random-looking linear code and a codeword that’s been corrupted with errors, recover the original. The general version of this problem is NP-hard, and after decades of effort there’s no known efficient way to solve it, which is the ground the whole family stands on.
Source: the NP-hardness of general decoding is the classical result carried in the private-vault source note for this concept; the schemes below rely on the difficulty of decoding the specific random-looking codes they publish.
The mechanism, in the McEliece tradition, has a clean shape:
- Key generation. You start with an error-correcting code you can decode efficiently because you know its hidden structure, then apply a scrambling transformation. The result, your public key, looks like an ordinary random code with no exploitable structure.
- Encapsulation. A sender takes your public key and encodes a fresh secret, then adds a carefully bounded pattern of errors on top. Adding errors is trivial; the sender needs nothing but the public key.
- Decapsulation. You use the hidden structure in your private key to correct those errors and recover the secret. Without that structure, correcting the errors means solving the hard decoding problem.
That shared secret then feeds ordinary symmetric cryptography and key derivation, the same downstream flow as any other KEM. What’s different is only the foundation. There’s no factoring and no discrete logarithm here, so Shor’s algorithm, which demolishes RSA and elliptic-curve cryptography, has nothing to attack. Grover’s algorithm offers only the generic quadratic speedup on brute-force search, and parameter sizes already absorb it.
Source: NIST IR 8545, Status Report on the Fourth Round of the NIST PQC Standardization Process, March 2025, which standardizes the code-based KEM HQC on exactly this quantum-resistance basis.
Why does it matter for the post-quantum transition?
Code-based cryptography matters most as mathematical diversity insurance. The primary NIST standards for both key establishment and signatures, ML-KEM and its lattice siblings, all rest on the same broad family of lattice assumptions. That concentration is efficient, and it’s also a single point of failure: a future cryptanalytic advance against lattices, classical or quantum, could weaken several of the primary standards at once. An organization running only lattice-based PQC would then have to re-migrate everything simultaneously.
Code-based schemes rest on a completely different foundation, so a lattice break wouldn’t touch them. That’s the reasoning NIST stated plainly when it selected HQC on March 11, 2025: “We want to have a backup standard that is based on a different math approach than ML-KEM,” and HQC “will serve as a backup defense in case quantum computers are someday able to crack ML-KEM.”
Source: NIST, “NIST Selects HQC as Fifth Algorithm for Post-Quantum Encryption”, March 11, 2025.
For most migration programs, that makes the family a Phase 2 consideration rather than a first move. You deploy ML-KEM now because it’s the finalized default, and you keep a code-based option on the roadmap as the answer to the question every mature program eventually asks: what happens if the assumption underneath our primary standard turns out to be weaker than we thought? Keeping a second, independent family available is the instinct behind crypto-agility.
What are the members?
Three code-based KEMs are worth knowing. All three were candidates in the fourth round of the NIST standardization process, which studied BIKE, Classic McEliece, HQC, and SIKE for key establishment. Only one came out of it with a standard.
Source: NIST IR 8545, March 2025: “The only key-establishment algorithm that will be standardized is HQC.”
| Member | NIST status | Key-size profile | Notes |
|---|---|---|---|
| HQC | Selected March 11, 2025 as the code-based backup KEM; draft standard expected ~2026, final expected 2027 | Larger keys and ciphertexts than ML-KEM, far smaller than Classic McEliece | Built on quasi-cyclic codes; the deployable code-based KEM to track for diversity |
| Classic McEliece | Round 4 candidate; not selected as a NIST standard | Very large public key (hundreds of kilobytes up to roughly a megabyte); very small ciphertext | The founding 1978 construction (binary Goppa codes); longest track record; conservative, high-assurance, and out-of-band-keyed niches |
| BIKE | Round 4 candidate; not selected as a NIST standard | Compact quasi-cyclic keys, larger than ML-KEM’s | Built on QC-MDPC codes; carries a non-negligible decryption-failure probability and more side-channel sensitivity than the lattice default |
HQC (Hamming Quasi-Cyclic) is the one that made it. NIST chose it as the fifth post-quantum algorithm and the code-based counterweight to ML-KEM, with a draft standard expected in about a year from the announcement and a final standard expected in 2027 after public comment.
Source: NIST, March 11, 2025.
It’s selected but not yet finalized, so it’s a “track closely and design for” algorithm, not a “deploy broadly today” one.
Classic McEliece is the elder of the family, the direct descendant of Robert McEliece’s 1978 scheme. Its size profile is the inverse of almost everything else: a very large public key paired with a very small ciphertext. That’s disqualifying for any protocol that ships the public key on every handshake, and genuinely useful in the narrow case where a static key can be provisioned once, out of band, and only the tiny ciphertext crosses the wire afterward. NIST didn’t select it, but it remains the most conservative option on the strength of its track record.
BIKE (Bit Flipping Key Encapsulation) is the other quasi-cyclic contender. It produces compact keys, but it carries a small non-zero chance that a valid message fails to decapsulate, which complicates its security analysis, and its bit-flipping decoder has been more sensitive to timing side-channel concerns. NIST didn’t advance it to standardization either.
What are the tradeoffs?
The strengths and the costs of code-based cryptography are both easy to name.
- Strength: confidence. A 40-plus-year history without a practical break gives the family the longest confidence horizon in post-quantum cryptography. When the question is “how sure are we this is hard,” code-based schemes have the most evidence to point to.
- Strength: independence. Its security has nothing to do with factoring, discrete logs, or lattices. Whatever breaks the mainline standards, code-based schemes are structurally out of the blast radius.
- Cost: size. Public keys are large, in the historically extreme case (Classic McEliece) very large. That size lands on bandwidth, protocol handling, and storage, which is where the real integration work sits, not on CPU.
- Cost: KEM-only. There’s no widely standardized code-based signature scheme, so the family doesn’t help with authentication, certificates, or code signing. Those roles fall to lattice and hash-based signatures.
- Cost: maturity. The selected member, HQC, isn’t a finalized standard yet, and the surrounding library and validation ecosystem is younger than the lattice one. That’s a reason to design for it now and deploy it deliberately, not a reason to wait on it before migrating to ML-KEM.
The honest summary: code-based cryptography buys assurance and independence with bytes on the wire and a narrower job description.
Common misconceptions
“Code-based cryptography is the new default.” The finalized primary KEM is ML-KEM, and it’s what most programs deploy first. HQC is the selected code-based backup, valued for diversity, and it should never be a reason to delay an ML-KEM migration.
“Post-quantum means signatures.” Code-based cryptography does key establishment only. It solves the confidentiality half of the transition and does nothing for authentication on its own. If the problem in front of you is signing, this family isn’t the answer.
“NIST selected all the code-based finalists.” Of the fourth-round key-establishment candidates, only HQC will be standardized. Classic McEliece and BIKE were studied and not selected, and SIKE was withdrawn after it was broken. Treating Classic McEliece or BIKE as a NIST standard is a factual error.
Source: NIST IR 8545, March 2025.
“The big keys make it insecure.” The large public key is a deployment cost, not a weakness. In the one place the profile fits, a static key loaded out of band with only a tiny ciphertext crossing the link, that size becomes an advantage.
Code-based cryptography is the family you keep on the roadmap so a single bad day for lattice math isn’t a bad day for your whole estate. Everything here is the map, given freely. When your team needs to decide where a code-based backup actually belongs in your protocols and estate, that’s what an alignment briefing is for.
Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.