Code-Based Cryptography Primer
Error-Correcting Codes: The Foundation
Error-correcting codes (ECCs) allow a sender to encode data so that a receiver can detect and correct errors introduced during transmission. Cryptographers discovered that the difficulty of decoding a random linear code can be used as the basis for a public-key cryptosystem.
The idea: the private key is a structured code that's easy to decode. The public key disguises this structure so that decoding looks like solving a hard problem for anyone without the private key.
Simple Parity Check Example
A parity check matrix H defines which bit patterns are valid codewords. If a received word r satisfies H ยท r = 0, it's valid. Otherwise, the non-zero result (the syndrome) reveals where errors occurred.
QC-MDPC Codes
Quasi-Cyclic Moderate-Density Parity-Check (QC-MDPC) codes are the mathematical backbone of BIKE.
- Quasi-Cyclic (QC): The parity check matrix H is built from circulant blocks โ each block is fully determined by its first row, which is cyclically shifted to fill the remaining rows. This gives compact key representation.
- Moderate-Density Parity-Check (MDPC): H is sparse but not as sparse as classical LDPC codes. The row weight w is roughly O(โn), providing a balance between decodability and security.
- Structure: H = [Hโ | Hโ] where Hโ and Hโ are rรr circulant matrices, each defined by a single row polynomial of weight w/2.
BIKE-1 (Level 1): r = 12,323 โ each circulant block defined by a row of weight w/2 = 71
The LPN Hardness Assumption
BIKE's security rests on the Learning Parity with Noise (LPN) problem โ specifically, the difficulty of decoding a random quasi-cyclic code. Given a random syndrome s = H ยท e where e is a sparse error vector, recovering e is believed to be hard even for quantum computers.
This is related to the Syndrome Decoding Problem, which has been studied since the 1960s and is NP-hard in the worst case.
From Codes to Key Encapsulation
BIKE builds a Key Encapsulation Mechanism (KEM) on top of QC-MDPC codes. The private key holder knows the sparse structure of H and can decode efficiently. Everyone else faces a hard decoding problem. Next: let's generate a BIKE keypair.
BIKE Key Generation
BIKE key generation produces a keypair using QC-MDPC code structure. We use BIKE-1 (Level 1) parameters for speed in the browser.
| Parameter Set | Security Level | r (block size) | w (row weight) | t (error weight) |
|---|---|---|---|---|
| BIKE-1 | Level 1 | 12,323 | 142 | 134 |
| BIKE-3 | Level 3 | 24,659 | 206 | 199 |
| BIKE-5 | Level 5 | 40,973 | 274 | 264 |
Generate BIKE-1 Keypair
Press "Generate Keypair" to create a BIKE-1 key pair.
Key Structure
Private Key
A pair of sparse polynomials (hโ, hโ) in the ring Fโ[x]/(xr โ 1), each of weight w/2 = 71.
These define the sparse rows of the QC-MDPC parity check matrix H = [Hโ | Hโ].
Public Key
A single polynomial h = hโโปยน ยท hโ mod (xr โ 1).
This is the systematic form of the code โ knowing h without the sparse factorization doesn't help decode.
Key Size Comparison
BIKE achieves much smaller keys than Classic McEliece while staying in the same code-based security family. ML-KEM has the smallest keys overall. RSA-2048 is not post-quantum secure.
Keys generated. Now let's use them to encapsulate and share a secret.
Encapsulation & Decapsulation
KEM Flow: Alice โ Bob
- Alice encapsulates: Using Bob's public key, generates a random error vector e of weight t = 134, computes ciphertext c = e ยท [1 | h]แต and derives shared secret K from e.
- Bob decapsulates: Using his private key (hโ, hโ), computes syndrome s = H ยท cแต, then applies the Black-Gray-Flip (BGF) decoder to recover e, and derives the same K.
- Shared secret match: KAlice = KBob โ used to key a symmetric cipher.
The Black-Gray-Flip Decoder
BIKE uses the Black-Gray-Flip (BGF) bit-flipping decoder for decapsulation:
- Compute syndrome: s = H ยท cแต โ reveals the error pattern
- Classify bits: Count how many unsatisfied parity checks each bit participates in. Bits exceeding a threshold T are "Black" (high confidence errors), those near T are "Gray" (uncertain).
- Flip Black bits in the first iteration โ these are almost certainly errors.
- Subsequent iterations: Flip both Black and Gray bits, recompute syndrome, repeat.
- Convergence: When syndrome reaches zero, the error vector is recovered.
Decapsulation Failure Rate (DFR): BIKE has a non-zero DFR โ the decoder may fail to converge for some error patterns. For BIKE-1 (Level 1), DFR < 2โ128. This is low enough for most applications but means BIKE is not suitable for protocols requiring perfect correctness (zero DFR). ML-KEM has DFR < 2โ139 which is essentially negligible.
Try It: Encapsulate & Decapsulate
โ Generate a keypair in first.
End-to-End: KEM + AES-256-GCM
BIKE + AES-256-GCM provides a complete post-quantum secure channel. But how does BIKE compare to the standardized ML-KEM?
BIKE vs ML-KEM Comparison
Side-by-Side: Key Sizes, Ciphertext, Performance
| Property | BIKE-1 | ML-KEM-512 | BIKE-3 | ML-KEM-768 | BIKE-5 | ML-KEM-1024 |
|---|---|---|---|---|---|---|
| Security Level | 1 | 1 | 3 | 3 | 5 | 5 |
| Public Key (bytes) | 1,541 | 800 | 3,083 | 1,184 | 5,122 | 1,568 |
| Ciphertext (bytes) | 1,573 | 768 | 3,115 | 1,088 | 5,154 | 1,568 |
| Shared Secret (bytes) | 32 | 32 | 32 | 32 | 32 | 32 |
| Security Assumption | QC-MDPC Decoding | QC-MDPC Decoding | QC-MDPC Decoding | |||
| vs | Module-LWE | vs | Module-LWE | vs | Module-LWE | |
| Decap Failure Rate | < 2โ128 | < 2โ139 | < 2โ192 | < 2โ164 | < 2โ256 | < 2โ174 |
| NIST Status | Round 4 Alt | Standardized | Round 4 Alt | Standardized | Round 4 Alt | Standardized |
Visual: Public Key + Ciphertext Sizes
Security Assumption Diversity
ML-KEM (Lattice-Based)
Built on the Module Learning With Errors (Module-LWE) problem. Lattice problems are relatively new in cryptography (studied since ~1996). ML-KEM is the NIST standard โ the recommended default.
Recommended DefaultBIKE (Code-Based)
Built on the Syndrome Decoding / QC-MDPC Decoding problem. Code-based cryptography dates to McEliece (1978) โ the oldest post-quantum proposal still unbroken. BIKE provides algorithmic diversity.
Diversity Use CasesKey tradeoff: BIKE has much smaller keys than Classic McEliece (the other code-based candidate) but has a non-zero decapsulation failure rate, unlike ML-KEM's essentially negligible DFR. For protocols requiring perfect correctness, ML-KEM is the better choice.
Both KEMs have their place. Let's explore why code-based post-quantum crypto matters for the future.
Why Code-Based Post-Quantum Crypto Matters
Cryptographic Diversity
The NIST post-quantum standardization process selected ML-KEM (lattice-based) as the primary KEM standard. But the process also advanced code-based and isogeny-based alternatives because no single mathematical assumption should be a single point of failure.
If a breakthrough attack against lattice problems emerges, code-based schemes like BIKE and Classic McEliece would remain secure โ and vice versa. This is the cryptographic diversity argument.
45+ Years of Cryptanalysis
Robert McEliece proposed the first code-based public-key cryptosystem in 1978 โ making it the oldest post-quantum proposal still considered secure. The core hardness assumption (syndrome decoding) has withstood decades of cryptanalytic effort.
- 1978: McEliece cryptosystem proposed (Goppa codes)
- 1986: Niederreiter dual formulation
- 2013: Misoczki et al. propose MDPC-McEliece โ precursor to BIKE
- 2017: BIKE submitted to NIST PQC competition
- 2022: BIKE advances to NIST Round 4
- 2024โ2026: BIKE under active evaluation for potential standardization
BIKE's Role in the PQ Landscape
BIKE occupies a specific niche in the post-quantum ecosystem:
- Compact alternative to Classic McEliece: Public keys ~1.5 KB vs ~261 KB at Level 1
- Same mathematical family: Both rely on the hardness of decoding random codes
- Tradeoff: BIKE has non-zero DFR; Classic McEliece has zero DFR but enormous keys
- Use cases: Where ML-KEM is primary but code-based diversity is desired as a backup or in hybrid constructions
Why This Matters in 2026+
Post-quantum migration is underway across the internet. The critical lesson from decades of cryptographic history:
Don't put all your eggs in one mathematical basket.
ML-KEM should be the default choice for most deployments. But organizations with long-term security requirements should consider hybrid approaches that include code-based schemes like BIKE โ ensuring that a breakthrough against lattices doesn't compromise everything at once.
Explore More
ML-KEM (Kyber) โ The standardized lattice-based KEM crypto-lab-mceliece-gate
Classic McEliece โ Same code-based family, different tradeoffs crypto-lab-dilithium-seal
ML-DSA (Dilithium) โ Lattice-based digital signatures crypto-lab-sphincs-ledger
SLH-DSA (SPHINCS+) โ Hash-based digital signatures crypto-compare
Side-by-side KEM category comparison