Code-Based Cryptography and the McEliece Algorithm

Code-based cryptography is one of the oldest families of post-quantum algorithms. Its flagship, the McEliece cryptosystem, was proposed in 1978 — older than RSA — and has resisted cryptanalysis for nearly half a century.

The Core Idea

Code-based schemes rely on error-correcting codes. The sender scrambles a message by adding a controlled amount of noise; only someone with the secret decoding key (a carefully chosen code) can remove the noise and recover the message. Without the key, removing the noise is computationally infeasible — and no quantum algorithm is known to do it efficiently.

Why It Is Quantum-Resistant

The underlying problem — decoding a random linear code — is hard for both classical and quantum computers. Unlike factoring, there is no Shor-style shortcut. This long track record is exactly why NIST kept Classic McEliece as a fourth-round candidate for key encapsulation.

The Trade-off: Large Public Keys

Classic McEliece's main drawback is its public key size — often around one megabyte. That is far larger than lattice-based ML-KEM keys. For bandwidth-constrained environments this is a problem, but for applications where keys can be pre-distributed or stored, it is manageable.

Where Code-Based Cryptography Fits

• Long-term key encapsulation where conservative security matters more than bandwidth.
• Embedded and IoT systems that can store pre-shared keys.
• Hybrid schemes combined with ML-KEM for defence in depth.

Classic McEliece vs ML-KEM

| Property | Classic McEliece | ML-KEM (FIPS 203) | |---|---|---| | Public key | ~1 MB | ~1 KB | | Ciphertext | Small | Small | | Maturity | 45+ years | ~10 years | | Standardised | Not yet (NIST round 4) | Yes (FIPS 203) |

Practical Takeaway

Code-based cryptography is not the default choice for most deployments — ML-KEM is. But for organisations that need maximum long-term assurance and can tolerate large keys, Classic McEliece is a serious, time-tested option. It also serves as a reminder that post-quantum security is not a single algorithm but a portfolio of options with different trade-offs.

When you design a quantum-safe strategy, keep code-based schemes in your back pocket as a conservative alternative if lattice assumptions ever come under pressure.