Code-Based Cryptography Primer

Coding-theory terms used on this page (tap to expand)
Syndrome
The result s = H·r. Zero means r is a valid codeword; a non-zero syndrome encodes where the errors are.
Weight
How many 1-bits a vector has. "Sparse" = low weight; the private rows have weight w/2 = 71, the error has weight t.
Circulant
A square matrix in which each row is the row above it, shifted one step to the right (wrapping around). Fully described by its first row.
Ring F₂[x]/(xʳ−1)
Polynomials with 0/1 coefficients where xʳ = 1. Multiplying by x is exactly a cyclic shift — so a circulant matrix is a polynomial in this ring.
Systematic form
A code layout where the message bits appear verbatim inside the codeword, followed by parity bits — so decoding just reads off the first block.
LPN
Learning Parity with Noise — recovering a secret from many noisy linear equations over F₂. The average-case hard problem underneath BIKE.

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.

Enter exactly 4 binary digits (0 or 1)

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.
H =
H₀ r × r circulant
H₁ r × r circulant

BIKE-1 (Level 1): r = 12,323 — each circulant block defined by a row of weight w/2 = 71

See it: one row builds a whole block

The static [H₀ | H₁] box above just asserts "circulant." Here's the same idea you can poke. Toggle a bit in the first row and watch every other row — the same row shifted one step right — re-fill the block. That is what quasi-cyclic means, and why one short row is enough to store the whole matrix.

Go deeper The LPN / Syndrome-Decoding 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.