Code-based cryptography

Code-based cryptography builds encryption schemes on the hardness of decoding random linear error-correcting codes. Its flagship, the McEliece cryptosystem proposed in 1978, is the oldest public key encryption scheme that remains unbroken, and the family gained renewed importance when NIST selected the code-based KEM HQC in 2025 as a backup to the lattice-based ML-KEM.

#The McEliece cryptosystem

Robert McEliece proposed the scheme in 1978, within two years of the invention of public-key cryptography itself (McEliece 1978). The private key is a binary Goppa code with an efficient decoder; the public key is a scrambled generator matrix that looks like a random code. Encryption encodes the message and adds deliberate errors; the legitimate receiver strips them with the secret decoder, while an attacker faces the general problem of decoding a random-looking linear code. That general decoding problem is NP-hard in its exact form, and the best known attacks, the information set decoding family first outlined by Prange in 1962, have improved only incrementally in six decades. Parameters chosen in 1978 required only moderate enlargement to stay ahead, an endurance record no other post-quantum candidate can match. No quantum algorithm better than Grover-type search is known for it; Shor's algorithm does not apply.

Harald Niederreiter published a dual formulation in 1986 that works with parity-check matrices and syndromes instead of generator matrices. It is provably equivalent in security, produces very small ciphertexts, and is the form modern instantiations use.

#Classic McEliece

Classic McEliece is the conservative modern packaging of the Niederreiter construction with binary Goppa codes, submitted to the NIST process and evaluated through its fourth round (classic.mceliece.org). Its profile is extreme in both directions:

Public keys of 0.26 to 1.36 megabytes rule out protocols that ship keys per connection, but ciphertexts under 210 bytes and fast encapsulation make it attractive where the public key moves rarely: static VPN configurations and similar long-lived deployments already use it. NIST's fourth-round report weighed exactly this tradeoff and declined to standardize Classic McEliece, citing the key sizes and its coverage by other selections, while noting its security record; the team continues standardization through ISO (NIST IR 8545).

#HQC

HQC (Hamming Quasi-Cyclic) takes the other route through coding theory (pqc-hqc.org). Instead of hiding a secret decodable code, its security rests on decoding random quasi-cyclic codes, with a public error-correcting layer handling noise. The design gives decryption failure rates that can be analyzed precisely, and keys small enough for ordinary protocols: public keys of 2249 to 7245 bytes and ciphertexts of 4433 to 14421 bytes across its three parameter sets, larger and slower than ML-KEM but entirely practical.

On March 11, 2025 NIST selected HQC as the fifth algorithm of the standardization process and the designated backup KEM, explicitly because it rests on different mathematics than the lattice problems under ML-KEM (NIST 2025). A draft standard is expected around 2026 to 2027. If an unexpected advance ever undermined lattice-based cryptography, HQC is the standing replacement; details are covered under HQC.

#Tradeoffs and limitations

The family's strength is the age and stability of its central assumption; its weakness is size. Code-based signature schemes have also historically fared poorly (early proposals were impractical or broken), so the family contributes KEMs, not signatures, to the post-quantum portfolio. In deployment terms, code-based KEMs serve as the diversity hedge of post-quantum cryptography: run alongside or instead of lattice schemes, often in hybrid configurations, insuring against a single mathematical surprise.