← Back to Blog Cryptography

BIKE: Bit-Flipping Key Encapsulation Explained

Q: Is BIKE secure?

Yes, at standardised parameter sets. BIKE has been studied since 2017 with no known catastrophic attacks. The decoding failure rate analysis has been refined multiple times during the NIST process, and the current parameters are believed to give the claimed security levels. NIST chose HQC over BIKE for reasons of analytical maturity and side-channel ease, not security weakness.

Q: Could BIKE be standardised in a future NIST round?

Possible. NIST has not closed the door on additional KEM standardisation. The signature on-ramp accepted new candidates in 2023, and a future KEM diversification call could give BIKE another shot. For now (2026), HQC is the standardised non-lattice KEM and BIKE is a research-grade alternative.

Q: What does QC-MDPC stand for?

Quasi-Cyclic Moderate Density Parity-Check. "Quasi-cyclic" means the code's parity-check matrix has a block-circulant structure that compresses storage. "Moderate Density" means the parity-check matrix has more 1s than a low-density code (LDPC) but fewer than a dense code. The combination gives small keys with manageable decoding complexity.

Q: Why is decoding failure such a big deal?

Because decoding failures leak private key information. If an attacker can deliberately submit ciphertexts that cause decoding failures and observe the failures (via a side channel like timing or an explicit error message), they can statistically learn the private key. Setting the DFR low enough that no attacker can ever observe a failure in a realistic time budget is the defence. BIKE targets DFR < 2^-128 for Category 1, but estimating that rate accurately requires careful analysis.

10 min read

BIKE: Bit-Flipping Key Encapsulation Explained - QNSQY post-quantum encryption guide

BIKE, short for Bit-Flipping Key Encapsulation, is a code-based KEM that NIST kept alive through Round 4 of the post-quantum competition. It uses Quasi-Cyclic Moderate Density Parity-Check (QC-MDPC) codes instead of the Goppa codes that Classic McEliece uses. The trade-off is smaller public keys (about 4 KB instead of a megabyte) at the cost of more complex security analysis around something called "decoding failure rate".

In March 2025, NIST chose HQC over BIKE for the Round 4 KEM slot (NIST IR 8528). BIKE was not standardised but is still considered a strong scheme. This article walks through how BIKE works, why decoding failure rate matters, and why it lost out to HQC.

The Suspicious Garbage Bag

Imagine someone hands you a garbage bag and tells you "there's a clean shirt in here, hidden among 10,000 dirty rags. Can you find it?" If you have a special detector that the bag's owner gave you (the private key), you can pull out the shirt instantly. Without the detector, you have to try every rag until you find the one that does not stink. That is what code-based encryption does, in code form.

BIKE's twist is that the "garbage bag" (ciphertext) is structured so that some rare combinations of rags can confuse even the detector. When that happens, the legitimate recipient fails to find the shirt and gets garbage instead. This is called a decoding failure. Most of the time it does not happen, but the rate at which it does happen is a critical security parameter, because an attacker who induces decoding failures can sometimes leak private key information.

The Code-Based Family Tree

Code-based cryptography started in 1978 with McEliece. The original McEliece scheme uses Goppa codes, which give very strong security but huge public keys. Researchers tried for decades to find code families with smaller keys without sacrificing security. Most attempts (Niederreiter variants, Reed-Solomon McEliece, Reed-Muller McEliece) eventually fell to attacks that exploited their algebraic structure.

QC-MDPC (Quasi-Cyclic Moderate Density Parity-Check) codes, introduced by Misoczki, Tillich, Sendrier, and Barreto in 2013, were a different approach. They take cryptographically random-looking codes (no algebraic structure) and add a quasi-cyclic block structure that compresses the key by a factor of 1000. The result is a code-based scheme with sub-10KB keys.

BIKE is the KEM built around QC-MDPC. Its design team includes Nicolas Aragon, Paulo Barreto, Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Shay Gueron, Tim Güneysu, and others.

How BIKE Works

The protocol has three steps: KeyGen, Encapsulate, Decapsulate.

KeyGen picks two sparse polynomials h0 and h1 (sparse means they have few non-zero coefficients). The public key is h = h1 * h0^-1 mod (x^r - 1). The private key is (h0, h1). The trapdoor: knowing h0 and h1 lets you decode efficiently. Without them, decoding is hard.

Encapsulate picks a random sparse pair (e0, e1), computes c = e0 + e1 * h, and derives a shared secret from (e0, e1) via a hash function. The KEM ciphertext is c.

Decapsulate uses (h0, h1) to "decode" the ciphertext, recovering (e0, e1). The shared secret is then re-derived from (e0, e1). If decoding fails (rare), the protocol applies an implicit-rejection step to keep the failure indistinguishable from success on the wire.

The Bit-Flipping Decoder

The "Bit-Flipping" part of the name comes from the decoding algorithm. Given the ciphertext c and the private key (h0, h1), the decoder iteratively flips bits of c based on parity-check constraints. Each iteration flips bits that violate the most checks. After enough iterations, c converges to the correct codeword and the error pattern (e0, e1) is recovered.

The decoder is fast (a few microseconds) but is not guaranteed to converge. For some random inputs, it produces a wrong answer. The probability of this is the Decoding Failure Rate (DFR), and it is the central security knob in BIKE.

Why Decoding Failure Rate Matters

A decoding failure leaks information about the private key. If an attacker can collect many ciphertexts that cause decoding failures, they can statistically reconstruct (h0, h1). This is called the GJS attack (Guo, Johansson, Stankovski, 2016) and applies to QC-MDPC schemes generally.

The defence is to set parameters so the DFR is astronomically low, on the order of 2^-128 or 2^-256. At those rates, an attacker would need an impractical number of ciphertexts to ever observe a single failure. BIKE's standardised parameter sets target DFR < 2^-128 for Category 1, < 2^-192 for Category 3, < 2^-256 for Category 5.

The catch is that estimating the DFR theoretically is hard. The decoder's behaviour is non-linear and depends on subtle interactions between the random error pattern and the private key. Most DFR estimates rely on a combination of theoretical analysis and large-scale empirical testing. NIST flagged "DFR analysis" as a key open problem during Rounds 3 and 4.

The Difference From HQC

HQC, the Round 4 KEM winner, also uses code-based math but in a way that avoids decoding failures entirely. HQC's design separates the message-recovery step from the trapdoor in a way that makes the decoding always succeed (with negligible probability of failure that does not leak private key info). The price is slightly larger ciphertexts than BIKE.

NIST cited HQC's "decoding failure analysis is more straightforward" as one factor in selecting HQC over BIKE in March 2025.

BIKE Parameter Sets

The Round 4 BIKE submission has three parameter sets:

Parameter set	Security level	Public key size	Ciphertext size	DFR target
BIKE-1	NIST Category 1	1,541 bytes	1,573 bytes	2^-128
BIKE-3	NIST Category 3	3,083 bytes	3,115 bytes	2^-192
BIKE-5	NIST Category 5	5,122 bytes	5,154 bytes	2^-256

Compared to Classic McEliece, BIKE keys are 100x to 200x smaller. Compared to ML-KEM-768 (1,184-byte public key, 1,088-byte ciphertext), BIKE-1 is in the same ballpark, slightly larger. For most deployment scenarios, BIKE-1 is small enough to fit in a TLS handshake or IKE message without additional fragmentation.

The Round 4 Decision

NIST IR 8528 (March 2025) selected HQC for standardisation. The official rationale called out:

DFR analysis maturity: HQC's decoding failure model is simpler and easier to verify.
Implementation simplicity: HQC's reference code has fewer subtle pitfalls than BIKE's bit-flipping decoder.
Side-channel resistance: HQC's constant-time implementation was easier to achieve.

NIST did not say BIKE was insecure. The report explicitly noted BIKE remained "a strong candidate" and that the Round 4 process was about choosing one non-lattice KEM, not eliminating others. BIKE's submission team has indicated they will continue refining the scheme and may submit it to future standardisation processes.

Where BIKE Lives Now

BIKE has reference implementations in liboqs (Open Quantum Safe), pqcrypto, and AWS-LC's experimental post-quantum suite. It is not on a NIST FIPS track but remains a viable scheme for environments that want to use a code-based KEM with smaller keys than Classic McEliece. Some enterprise HSM vendors include BIKE as an experimental option.

BIKE vs HQC vs Classic McEliece

The three Round 4 code-based KEM candidates form an interesting spectrum:

Classic McEliece: Oldest (1978), strongest cryptanalytic record, 1 MB public keys.
BIKE: Newest design (2017), QC-MDPC codes, 1.5 KB public keys, decoding failure complexity.
HQC: 2017, Hamming Quasi-Cyclic, 7-14 KB ciphertexts, no decoding failure issues.

NIST chose HQC because it strikes the best balance of size, simplicity, and analytical maturity for general-purpose deployment. McEliece survived because its security is the most conservative. BIKE survived because its design is elegant and its size is competitive, but the DFR analysis kept it just behind HQC in NIST's evaluation.

Why Side-Channel Resistance Matters Here

The bit-flipping decoder at BIKE's heart is iterative: it loops until the result converges or a maximum iteration count is reached. The iteration count varies depending on the random error pattern in each ciphertext. This timing variation is a potential side-channel: an attacker who can observe decapsulation timing might learn statistical information about the private key. Constant-time implementations of BIKE require running the maximum number of iterations every time, which costs performance.

HQC, by contrast, has a non-iterative decoding step that always takes the same time regardless of ciphertext content. Constant-time HQC is essentially the default behaviour, not an opt-in performance trade-off. NIST's IR 8528 cited this difference as one factor in HQC's selection. For deployment in environments that worry about timing side channels (cloud HSMs, network appliances, smart cards), HQC is a more forgiving choice.

BIKE in QNSQY

QNSQY does not ship BIKE. The scheme is not FIPS-standardised, and QNSQY's policy is to ship only NIST-standardised post-quantum algorithms. The non-lattice diversity in QNSQY's Business tier comes from HQC, which is the FIPS-bound winner.

If a customer needs BIKE specifically, the QNSQY hybrid envelope format is extensible. But the default deployment is ML-KEM (lattice) or HQC (code), not BIKE. For more on the alternatives, see Classic McEliece Deep Dive and HQC Explained.

The Code-Based Diversity Slot

The three Round 4 candidates (Classic McEliece, BIKE, HQC) covered the same conceptual slot in NIST's portfolio: a code-based KEM that provides non-lattice diversity. NIST's selection of HQC over BIKE means HQC fills that slot in FIPS-standardised deployments. BIKE's design remains technically interesting and the smaller key sizes are a real engineering accomplishment, but standards momentum favours HQC for the foreseeable future.

BIKE's value as a research scheme continues. The QC-MDPC code family it pioneered has applications beyond the specific BIKE construction, and DFR analysis techniques developed during BIKE's evaluation feed into other code-based work. Schemes like LEDAcrypt and Ouroboros (research-stage) build on similar foundations. So BIKE's loss in the Round 4 selection does not erase its contribution to the post-quantum field.

Frequently Asked Questions

Is BIKE secure?