Code-Based Cryptography

Code-based cryptography is the oldest post-quantum family, dating to McEliece in 1978. Its security rests on the difficulty of decoding random linear error-correcting codes — an NP-hard problem with no known quantum shortcut. The classic scheme has survived 45+ years of attack, making it a trusted, conservative KEM choice despite very large public keys.

The Hard Problem: Syndrome Decoding

An error-correcting code adds redundancy so that a few flipped bits can be corrected. For a structured code with a known decoder this is easy; for a random-looking linear code it is hard. The underlying problem is syndrome decoding: given a parity-check matrix and a syndrome, find a low-weight error vector that produces it. The general syndrome-decoding problem is NP-hard. To date, no known classical or quantum algorithm efficiently breaks these code-based constructions at the relevant parameters.

The trick of code-based encryption is to disguise a code that the owner can decode efficiently as one that looks random to everyone else. The public key is the scrambled code; the private key is the structure that enables fast decoding.

McEliece and Goppa Codes

The original McEliece cryptosystem (1978) uses binary Goppa codes. Remarkably, it has never been broken in over four decades of cryptanalysis — an exceptional track record. The cost is size:

McEliece's giant public keys make it impractical for many handshake protocols, but its conservatism makes it attractive where keys can be provisioned once and stored — and where confidence against future cryptanalysis matters most.

Structured Codes: Smaller Keys, New Risks

To make code-based KEMs practical, newer schemes use structured codes (quasi-cyclic, QC-MDPC) that compress the key dramatically:

• BIKE — uses QC-MDPC codes for keys of just a few kilobytes. However, some QC-MDPC constructions face decoding failures that can enable reaction attacks, where an adversary learns secret information from whether decapsulation succeeds. This requires careful analysis and constant-time decoding.
• HQC — uses structured codes but is engineered with a clean, well-quantified decoding-failure analysis, giving stronger assurance. NIST selected HQC for standardization in 2025 as a code-based KEM to diversify away from lattice-based ML-KEM.

Tradeoffs

• Pro — Decades of cryptanalysis (McEliece); a hard problem unrelated to lattices.
• Con — Very large keys (McEliece) or, for structured variants, decoding-failure risk that must be carefully bounded.
• Use — KEMs only; no practical signatures from this family in the standards.

Standards & references

• Classic McEliece project — the conservative binary-Goppa KEM.
• HQC project — the structured code-based KEM selected by NIST in 2025.
• NIST PQC project — the standardization process and selections.
• Resources — full standards register