Code-Based Cryptography, Explained: The Oldest Post-Quantum Idea Still Standing

Lattices underpin the main post-quantum standards, but they aren’t the only bet. NIST is also keeping a code-based alternative in reserve. The category goes back to Robert McEliece’s 1978 public-key system, one of the oldest major designs now counted as post-quantum, and its modern binary-Goppa-code versions have resisted practical attack for nearly 50 years. In 2025 NIST selected a code-based scheme, HQC, as a backup to its main key-establishment standard, ML-KEM, because it rests on substantially different math. Code-based designs carry a cost, though, and it’s a big one: size. Here’s how they work and where they fit.

Turning error correction into a lock

Error-correcting codes usually do the opposite of hiding things. They add redundancy so a garbled message can still be recovered, the trick that lets a scratched disc or a noisy signal come through clean. The original McEliece scheme turns that machinery into a lock. Its public key describes a structured error-correcting code disguised to look like a random one.

To encrypt, you encode a value with that public code and then add a deliberate pattern of errors. The private key contains the hidden structure needed to decode the result and remove the errors. Anyone else is left with the syndrome-decoding problem, recovering a low-weight error pattern from public code data. The general syndrome-decoding problem is NP-complete, and the best known attacks against the cryptographic instances used here still take exponential time.

Not every code-based scheme works the McEliece way. HQC, the one NIST picked, uses coding theory differently. Its quasi-cyclic structure is public, and its private key contains sparse secret values. The scheme’s security rests on structured syndrome-decoding assumptions. And the category itself isn’t spotless. Researchers have broken several McEliece variants built from other kinds of codes, so the security lives in the exact code and parameters, and the label “code-based” alone doesn’t guarantee much.

Why quantum computers don’t produce a Shor-style break

The reason this survives a quantum computer is subtler than the marketing suggests. Shor’s algorithm efficiently solves the factoring and discrete-logarithm problems behind RSA and elliptic-curve crypto. No known method lets it solve the syndrome-decoding problems behind HQC or Classic McEliece in anything like polynomial time, so there’s no Shor-style collapse waiting for them.

That doesn’t mean quantum computers are useless here. They can speed up classical decoding attacks through Grover-style search and related techniques, but the best known attacks remain exponential. The parameter sets account for those known quantum speedups. The value for NIST is that this hardness comes from a different place than the lattice problems, so a breakthrough aimed at ML-KEM’s assumptions wouldn’t automatically reach it.

The oldest scheme still standing: McEliece

Code-based cryptography dates to 1978, when Robert McEliece built a public-key system on a category of error-correcting codes called Goppa codes. Nearly 50 years on, no practical attack is known against the recommended binary-Goppa-code parameters, which is an unusually long clean run for a public-key design.

Attacks and security estimates have sharpened over the decades, and the parameter sizes have grown to keep pace, but the core idea has held. That record carried Classic McEliece, the modern version, deep into NIST’s process as a finalist. NIST didn’t standardize it in the end. The agency cited its enormous public keys and slow key generation, which make it unattractive for many common applications. McEliece-based encryption has since entered international standardization through an ISO amendment, so the design lives on outside the NIST track.

HQC: the smaller code-based option

HQC is the compromise NIST reached for. In March 2025 it selected HQC as a backup key-encapsulation mechanism alongside ML-KEM, giving the encryption side of the migration a second option on different assumptions. HQC is code-based too, but far lighter than McEliece. Its public keys run from about 2,200 bytes at the lowest security level to about 7,200 at the highest, against Classic McEliece’s 261 kilobytes to more than 1.3 megabytes across the same levels.

The tradeoff shows up in its ciphertexts, which are larger than ML-KEM’s, and in its newer security assumptions, which lack McEliece’s long history. ML-KEM stays the more compact choice overall, with public keys from 800 to about 1,570 bytes. NIST selected HQC in 2025 and has said it expects to finalize the standard in 2027.

Implications for your wallet

Place HQC and Classic McEliece beside ML-KEM. They establish shared symmetric keys, and they don’t produce signatures. A key-encapsulation mechanism hands two parties a shared secret, and a symmetric cipher then uses that secret to protect traffic or stored data.

So, a code-based scheme could one day help guard your encrypted data, and none of these three touches the signature that authorizes spending from your wallet. Protecting that requires a post-quantum signature and the blockchain support to use it. ML-DSA is one standardized example, though Bitcoin doesn’t accept it today.

The value of code-based crypto for a crypto holder is indirect. It gives the post-quantum world a separately studied family of assumptions to fall back on. Classic McEliece brings the long cryptanalytic history, and HQC brings the practical NIST backup, still being finalized. Between them, the encryption side of the transition doesn’t rest on lattices alone. Your wallet’s protection still comes down to signatures, and that migration requires separate changes to the blockchain protocol.