BIKE

BIKE (Bit Flipping Key Encapsulation) is a code-based key-encapsulation mechanism built on quasi-cyclic moderate-density parity-check (QC-MDPC) codes, notable for public keys only a few kilobytes in size. It reached the fourth round of the NIST post-quantum standardization process but was not selected; in March 2025 NIST chose HQC as the code-based backup to ML-KEM.

#How it works

BIKE's public key is a QC-MDPC code: a linear code whose parity-check matrix is sparse and has quasi-cyclic structure. Encapsulation encodes a random error vector into a ciphertext; decapsulation recovers that error by iterative bit-flipping decoding, which repeatedly flips the bits that violate the most parity checks until a valid codeword emerges. Security reduces to the hardness of decoding random quasi-cyclic codes (a syndrome decoding problem), believed hard for both classical and quantum computers. Grover's algorithm yields only the generic square-root speedup, which parameter sizing absorbs. Like other modern KEMs, BIKE wraps an IND-CPA core in a Fujisaki-Okamoto transform to reach IND-CCA2 security.

#Compact keys

The quasi-cyclic structure lets the whole public key be represented by a single polynomial, so keys and ciphertexts are only a few kilobytes, far smaller than Classic McEliece, whose public keys run from about 261 kilobytes to over 1 megabyte. This compactness was BIKE's main appeal within code-based cryptography: sizes close to HQC and within the same order of magnitude as lattice KEMs. Figures below are in bytes, from the round 4 specification at bikesuite.org.

#The decoding-failure-rate problem

Bit-flipping decoders do not always succeed: there is a nonzero decoding failure rate (DFR). For chosen-ciphertext security the DFR must be cryptographically small (below 2^-128 at the lowest security level), because a decoding failure can leak information about the secret key. A 2016 reaction attack by Guo, Johansson, and Stankovski demonstrated that an attacker who observes failures against a reused (static) key can reconstruct it. BIKE responded with the Black-Gray-Flip (BGF) decoder and parameters chosen for a very low DFR. The residual difficulty is fundamental: the DFR of an iterative decoder cannot be computed exactly, so it is estimated by extrapolating from simulations. The security argument therefore rests on an assumption about decoder behavior rather than a closed-form bound.

#Why NIST did not select it

When NIST closed the fourth round, it standardized HQC rather than BIKE as the code-based KEM. The status report (NIST IR 8545) cited HQC's decapsulation failure rate as more convincingly bounded, whereas BIKE's depends on decoder extrapolation, and judged HQC's overall security analysis more mature. Performance was not the deciding factor: BIKE is competitive and in several settings faster. The concern was confidence in the worst-case DFR and its interaction with IND-CCA2 security, so NIST preferred the candidate whose failure rate it could pin down.

#Status

BIKE is not on a NIST standardization track. Its specification remains published at bikesuite.org, and implementations exist in research libraries such as liboqs for experimentation and hybrid testing, but it is not recommended for production use. The niche it competed for, a non-lattice KEM diversifying the NIST portfolio against a possible break in lattice cryptography, is now filled by HQC.