BIKE: Bit Flipping Key Encapsulation

BIKE: Bit Flipping Key Encapsulation

Introduction

Two parties who want a shared key can use a key encapsulation mechanism, or KEM. One party publishes a public key. The other uses it to produce a random key together with a ciphertext, and the first party recovers the same key from that ciphertext. BIKE is a KEM whose security does not rest on factoring or on the discrete logarithm. It rests on the difficulty of decoding a certain kind of error-correcting code, a problem that is believed to resist quantum computers.

BIKE was one of the code-based candidates of the NIST post-quantum standardization process. It reached the fourth round. In March 2025, NIST announced that it would standardize only HQC from that round, and it did not select BIKE. The scheme is still a good one to study, because its pieces are simple: polynomials with coefficients 0 and 1, a sparse secret, and a decoder that repairs a noisy message one bit at a time.

This guide builds BIKE from the round 4 specification. It reproduces all 300 known-answer tests that the BIKE team published, for the three security levels, and it explains the decoder with the numbers of a real run. The Kyber guide and the HQC guide cover two other post-quantum KEMs, and the Classic McEliece guide covers the oldest code-based one.

Table of Contents

• History and Standards
• The Idea: a Sparse Code in Disguise
• The Three Algorithms
• Sampling and Hashing
• The Black-Gray-Flip Decoder
• Decoding Failures and the Rejection Rule
• Parameters and Sizes
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Where It Stands
• Limitations
• Security Status
• FAQ
• References

History and Standards

Code-based encryption is old. The NIST report on the fourth round calls the McEliece scheme of 1978 the original code-based cryptosystem, and it describes Classic McEliece as a descendant that is based on binary Goppa codes. Its keys are very large. BIKE follows a different path that the specification traces to the use of quasi-cyclic moderate-density parity-check codes, or QC-MDPC codes, in the McEliece scheme. These codes allow much smaller keys: the smallest public key of Classic McEliece in the NIST report has 261,120 bytes, and a BIKE public key at the first level has 1,541.

The BIKE submission is the work of a team of 18 people from universities and companies in several countries. The package lists INRIA, the Universities of Limoges and Toulouse, Worldline, Intel, Amazon Web Services, and Google among their affiliations. BIKE entered the NIST process, and by the third round the team had narrowed it to a single variant, built from the older BIKE-2 with a modern security transform. In the fourth round the team made one more change. The specification of version 5.1, dated 10 October 2022, replaced the sampler of fixed-weight vectors with a data-oblivious one, which removes the risk of certain side-channel attacks.

This guide follows version 5.1, the specification of the round 4 submission. The team released version 5.2 on 10 October 2024. Its list of changes after round 4 has three items. The recommended decoder is now BIKE-Flip, which has essentially the same features as BGF and resists failures better when weak keys occur. The sampler of constant-weight words comes in two flavors, a fixed-time one for the error and a uniform one for key generation. The CCA transform now hashes part of the public key together with the message, to resist multi-target key attacks. Version 5.2 comes with new known-answer tests. For the first test of Level 1 the seed is the same, and the public key, the ciphertext, and the shared key differ from the round 4 file. I did not implement version 5.2, so every check in this guide refers to version 5.1 and the round 4 package.

NIST selected four key-establishment candidates for the fourth round: BIKE, Classic McEliece, HQC, and SIKE. NIST IR 8545 reports that SIKE was broken, and that the only algorithm selected for standardization is HQC. The reasons for BIKE are these. NIST has confidence in the IND-CPA security of BIKE and HQC, but both need a sufficiently low decryption failure rate to reach IND-CCA2 security. NIST found the analysis of that rate more mature for HQC than for BIKE, and decided to standardize only HQC. BIKE has not been selected, and NIST says the algorithms that were not selected are not under consideration by the current process.

The Idea: a Sparse Code in Disguise

Work in the ring R = F2[X] / (X^r - 1). Its elements are polynomials of degree below r with coefficients 0 and 1, where X^r counts as 1. Adding two polynomials is an XOR. Multiplying by X rotates the coefficients by one place. The weight of a polynomial is its number of coefficients equal to 1.

The secret key is a pair (h0, h1) of sparse polynomials, each of weight w / 2. Together they describe the parity checks of a linear code of length 2r, and the sparse checks make that code easy to decode. The public key is the same code in a disguise: the dense polynomial h = h1 * h0^-1. An outsider sees a dense, random-looking h. The owner knows that h came from two sparse polynomials.

A message is hidden in an error (e0, e1): a pair of polynomials of small total weight t. The ciphertext is the syndrome of that error, c0 = e0 + e1 * h. Finding an error of weight t from its syndrome in a code with no known structure is the problem of syndrome decoding. For the owner of (h0, h1) it is easy, because c0 * h0 = e0 * h0 + e1 * h1, which is the syndrome of the error under the sparse checks. A decoder for sparse checks recovers (e0, e1) from it.

The parameters must fit this picture. The specification requires that r is prime and that 2 has order r - 1 modulo r, so that the ring has no unwanted structure. It requires that w is even and w / 2 odd, so that h0 always has an inverse. My test checks these conditions for all three parameter sets. It also confirms that a polynomial of even weight, such as 1 + X, has no inverse in the ring.

The Three Algorithms

The specification gives the KEM in three short procedures.

Key generation. The owner of the key does three things.

1. Sample the sparse pair (h0, h1), each of weight w / 2.
2. Compute the public key h = h1 * h0^-1.
3. Choose a random 32-byte string sigma. It is part of the secret key.

Encapsulation. The sender uses the public key h for these steps:

1. Choose a random 32-byte string m.
2. Compute the error (e0, e1) = H(m).
3. The ciphertext is c = (c0, c1) with c0 = e0 + e1 * h and c1 = m xor L(e0, e1).
4. The shared key is K = K(m, c).

Decapsulation. Given the secret key and c:

1. Run the decoder to get e' = decoder(c0 * h0, h0, h1). A failure counts as e' = (0, 0).
2. Unmask the message with m' = c1 xor L(e').
3. If e' = H(m'), the key is K(m', c). Otherwise the key is K(sigma, c).

The last step is the heart of the security transform. If the ciphertext is genuine, the decoder returns exactly the error that H(m) produced, and m' is m. If anything is wrong, e' does not match H(m'). The receiver then returns a key that depends on the secret sigma and on the ciphertext, so an attacker who sends modified ciphertexts learns nothing about whether a decoding failed.

To invert h0 in the ring, my code uses the extended Euclidean algorithm over F2, with Python integers for the polynomials. For the key of the worked example below it takes 11,563 steps at the first level. The reference code uses the library NTL for the inversion.

Sampling and Hashing

BIKE needs three kinds of pseudorandom values, and all of them come from SHAKE256.

• A sparse polynomial of weight wt and length len. Algorithm 3 of the specification reads wt numbers of 32 bits from a SHAKE256 stream. For i from wt - 1 down to 0, the number s_i gives the position i + floor((len - i) * s_i / 2^32). If that position is already taken, the algorithm uses i instead. The position i is always free at that point, so nothing is ever rejected. The specification says that this technique is immune to an attack on the earlier sampler and that its output is close to uniform.
• The secret key. The key generation calls Algorithm 3 twice on the same stream, with a seed of 32 bytes, for h0 and then h1.
• The error H(m). The function H calls Algorithm 3 on the stream of m, with weight t and length 2r. The first r positions belong to e0 and the others to e1.

The functions K and L are hashes. L(e0, e1) hashes the two polynomials, each written as ceil(r / 8) bytes, and K(m, c) hashes m || c0 || c1. The specification says that these are the ℓ = 256 bits of a 384-bit digest. The text calls the hash SHA384, but the reference code uses SHA3-384, and it keeps the first 32 bytes of the digest. My code does the same, and it reproduces the known-answer tests only with that choice.

A polynomial is written as bytes in little-endian order. The first byte holds the coefficients of X^0 to X^7, with X^0 in the lowest bit.

The Black-Gray-Flip Decoder

The decoder starts from the syndrome s = c0 * h0 and tries to find the error. It is a bit-flipping decoder, and its logic is simple. A bit of the error is likely to be wrong when many of the parity checks that contain it fail. For each position j the decoder counts the failing checks that contain j, in a number called ctr(j). The count lies between 0 and w / 2. If the count reaches a threshold T, the decoder flips the bit.

The specification selects the Black-Gray-Flip decoder, BGF, and gives it in Algorithm 1. It runs a fixed number of iterations, NbIter = 5, so there is no data-dependent loop. Each iteration has these steps:

1. Compute the syndrome s + e * H^T of the current estimate, and its weight S.
2. Compute the threshold from that weight. For Level 1 it is T = max(floor(0.0069722 * S + 13.530), 36). The threshold shrinks as the syndrome gets lighter.
3. Flip every position with ctr >= T. These positions are called black. Positions with T - 3 <= ctr < T are called gray.
4. In the first iteration only, test the black positions again with the lower threshold (d + 1) / 2 + 1, where d = w / 2, and then the gray positions. This step repairs flips made by mistake.

After the last iteration the decoder returns the error if its syndrome equals s, and a failure otherwise.

How does the code compute ctr fast? For the sparse polynomial h0 with positions k, the count for position j is the number of positions k with the bit j + k of the syndrome set. That is a sum of 71 rotations of the syndrome. My code adds them with a bit-sliced counter: the counters of all 12,323 positions are stored as a few bit planes, one Python integer for each bit of the counter, and each rotation is added with a carry-save adder. A comparison with a threshold is also done on the planes. This is my own formulation. The reference code counts position by position, and the results are the same.

Decoding Failures and the Rejection Rule

A bit-flipping decoder can fail. It may run out of iterations before the syndrome reaches zero. The decoding failure rate, DFR, is the chance that this happens for a random key and a random error. It matters in two ways. A failure breaks the exchange, because the two parties get different keys. It also helps an attacker. The specification cites the reaction attack: if the DFR is 2^-S, an attacker who can observe failures may recover the secret key with an effort of about 2^S.

This is why the parameters aim at a failure rate of 2^-128, 2^-192, and 2^-256 for the three levels. The specification is open about what it can prove. The DFR of the BGF decoder has been studied by simulation and extrapolation. The estimate is not a proven bound. The text says for that reason that the BIKE instantiation with the BGF decoder does not make a formal claim of IND-CCA security.

NIST’s own report goes further. It describes a class of weak keys, based on a gathering property, that cause a failure rate of at least 2^-117 for Level 1. It says that the thresholds of the decoder were altered in the fourth round to reduce the risk of a decryption failure, and it mentions a decoder called BIKE-flip that starts with a high threshold and lowers it. The team adopted BIKE-Flip as the recommended decoder in version 5.2. I implemented the BGF decoder of version 5.1, with the thresholds that it lists. The report also says that a model predicted a failure rate of 2^-129.5 for typical keys if the Level 1 block length grows from 12,323 to 13,477.

The check e' = H(m') handles the other problem, a modified ciphertext. My run shows how strict it is. I changed a single bit of c0 in the worked example below. The decoder still succeeds, and it returns an error of weight 135. That error is the real one plus 1 extra bit, which fits the new syndrome. It is not the error that H(m') produces, so the check fails. The receiver then outputs K(sigma, c), which is 95d9cd7d9c3d138ab947c31e2bebc9c2821b5671fb9ef8bde0e3cd07064d6fe7 in my run, and not the real key.

Parameters and Sizes

The specification gives one parameter set for each of the three NIST security levels, each tuned for a failure rate that matches its level.

Level	Block length r	Row weight w	Error weight t	Public key	Ciphertext	Target DFR
1	12,323	142	134	1,541 bytes	1,573 bytes	2^-128
3	24,659	206	199	3,083 bytes	3,115 bytes	2^-192
5	40,973	274	264	5,122 bytes	5,154 bytes	2^-256

The shared key has 32 bytes at every level. The secret key of the known-answer tests holds h0, h1, and sigma, which is 3,114, 6,198, and 10,276 bytes. The NIST report lists a smaller decapsulation key of 281 bytes for Level 1, which suggests a compact form of the secret key. The sizes of the public key and the ciphertext equal the ones in that report.

For speed, the NIST report gives measurements of an optimized implementation of Level 1 on x86_64: 637 thousand cycles for key generation, 111 thousand for encapsulation, and 1,428 thousand for decapsulation. The report states that BIKE is 6 to 10 times slower than HQC in key generation and 5 to 7 times slower in decapsulation, and that BIKE is about twice as fast as HQC in encapsulation. BIKE’s keys and ciphertexts are smaller. The report says that HQC ciphertexts are about three times larger, and that HQC public keys are about 41 to 47 percent larger.

Interactive Visualizer

The visualizer above runs the whole exchange, for real, in your browser, with the three parameter sets of BIKE. Choose a level and enter three 32-byte values in hexadecimal: the seed of the key, the value sigma, and the message m. The log shows every step on both sides.

• Key generation. The two sparse samples, the inversion of h0, and the public key.
• Encapsulation. The error from H(m), the ciphertext c0 and c1, and the shared key.
• The channel. A field lets you flip bits of c0 by position. With no flips, the ciphertext arrives unchanged.
• Decapsulation. The syndrome, one row for each step of the decoder with its threshold and the number of flipped positions, the check e' = H(m'), and the final key.

The default values are the seeds that the test generator of the BIKE team produces for the first known-answer test of Level 1, so the public key starts with the bytes of that test. Flip one bit and the receiver’s key changes, which shows the rejection rule at work. A run of Level 5 takes longer, because its polynomials have 40,973 coefficients.

A Worked Example

The first known-answer test of Level 1 starts from the 48-byte seed 061550234d158c5ec95595fe04ef7a25767f2e24cc2bc479d09d86dc9abcfde7056a8c266f9ef97ed08541dbd2e1ffa1. The random generator of the test suite, an AES-256 counter generator, produces the key seed 7c9935a0b07694aa0c6d10e4db6b1add2fd81a25ccb148032dcd739936737f2d and sigma = b505d7cfad1b497499323c8686325e4792f267aafa3f87ca60d01cb54f29202a. A second call gives the message m = eb4a7c66ef4eba2ddb38c88d8bc706b1d639002198172a7b1942eca8f6c001ba.

The sparse polynomial h0 has weight 71, and its first positions are 105, 281, 304, 454. The public key h is dense: it has 6,177 coefficients equal to 1 of 12,323. It starts with the bytes 07d0317a8bdb2d2438ab54042832af07d8a980f84e10debe, as the known-answer test says. The error from H(m) has weight 134, split into 64 for e0 and 70 for e1. The ciphertext part c0 has weight 6,126 and starts with 2c360eb591f5f30d64df178dc8f56252cf203ce20589b6fb, and c1 is 72998a3940aa9c63e036c10acead09fea5b372d0b517bc8227a9d2f0760423aa. The shared key is:

c748cc2121532efeeba47f446e8393b7202400463bebde6e45882acab8ddeec6

The receiver computes the syndrome s = c0 * h0, which has weight 4,804. The decoder then runs. This is its log in my code:

Step	Syndrome weight	Threshold	Positions flipped
Iteration 1	4,804	47	21
Iteration 1, black positions again	4,281	37	0
Iteration 1, gray positions	4,281	37	43
Iteration 2	3,306	36	72
Iterations 3, 4, and 5	0	36	0

After the second iteration the syndrome weight is zero, so the decoder has found an error. It is exactly the error (e0, e1) of the sender, and the receiver gets the same key. Over 300 random key pairs and messages at Level 1, the syndrome reached zero after 2 iterations in 210 cases and after 3 in 90 cases, and every decapsulation recovered the key. That is an observation from a small sample. It says nothing about a failure rate near 2^-128.

Python Implementation

This is a complete BIKE with the three parameter sets. Polynomials are Python integers, and the decoder works on bit planes. The class Params holds the parameters of one level.

# bike.py
# BIKE (Bit Flipping Key Encapsulation), round 4 specification, version 5.1: the key encapsulation
# mechanism, the Black-Gray-Flip decoder, and the SHAKE256-based samplers.
# A polynomial of F2[X]/(X^r - 1) is a Python integer: bit i is the coefficient of X^i.
# Teaching code. It is not constant time, so it must not handle real secrets.

import hashlib
from dataclasses import dataclass


@dataclass(frozen=True)
class Params:
    name: str
    r: int          # the block length, a prime
    w: int          # the row weight of the parity-check matrix
    t: int          # the weight of the error
    c0: float       # threshold(S) = max(floor(c0 + c1 * S), floor_t)
    c1: float
    floor_t: int
    tau: int = 3    # the gap that defines the gray positions
    iterations: int = 5
    ell: int = 32   # bytes of the shared secret and of the seeds

    @property
    def d(self):
        return self.w // 2

    @property
    def r_bytes(self):
        return (self.r + 7) // 8


LEVEL1 = Params("BIKE Level 1", 12323, 142, 134, 13.530, 0.0069722, 36)
LEVEL3 = Params("BIKE Level 3", 24659, 206, 199, 15.2588, 0.005265, 52)
LEVEL5 = Params("BIKE Level 5", 40973, 274, 264, 17.8785, 0.00402312, 69)
LEVELS = {1: LEVEL1, 3: LEVEL3, 5: LEVEL5}


# ---------- arithmetic in F2[X]/(X^r - 1) ----------

def rotate(a, k, r):
    """a * X^k: a cyclic shift of the r coefficients."""
    k %= r
    return ((a << k) | (a >> (r - k))) & ((1 << r) - 1)


def support(a):
    """The positions of the 1 bits, in increasing order."""
    positions, i = [], 0
    while a:
        low = (a & -a).bit_length() - 1
        positions.append(i + low)
        a >>= low + 1
        i += low + 1
    return positions


def mul(a, b, r):
    """The product of two polynomials: the sum of the shifts of a by the positions of the 1 bits of b."""
    result = 0
    for k in support(b):
        result ^= rotate(a, k, r)
    return result


def inverse(a, r):
    """The inverse of a modulo X^r - 1, by the extended Euclidean algorithm over F2.
    The number of steps depends on a, so this is not constant time. Real code needs a fixed-time inversion."""
    r0, r1 = (1 << r) | 1, a
    t0, t1 = 0, 1
    while r1 != 1:
        if r1 == 0:
            raise ValueError("the polynomial is not invertible")
        shift = r0.bit_length() - r1.bit_length()
        if shift < 0:
            r0, r1, t0, t1 = r1, r0, t1, t0
            shift = -shift
        r0 ^= r1 << shift
        t0 ^= t1 << shift
    # reduce t1 modulo X^r - 1
    result = 0
    while t1:
        result ^= t1 & ((1 << r) - 1)
        t1 >>= r
    return result


def to_bytes(a, p):
    return a.to_bytes(p.r_bytes, "little")


def from_bytes(data):
    return int.from_bytes(data, "little")


# ---------- the samplers (Algorithm 3 of the specification) ----------

def sample_positions(stream, length, weight):
    """`weight` distinct positions below `length`, from a stream of SHAKE256 output. Nothing is ever rejected."""
    positions = set()
    for i in range(weight - 1, -1, -1):
        word = int.from_bytes(stream.read(4), "little")
        position = i + ((length - i) * word >> 32)
        positions.add(i if position in positions else position)
    return positions


class Shake256Stream:
    """The stream of bytes of SHAKE256 for one seed, read a little at a time."""

    def __init__(self, seed):
        self.seed, self.buffer, self.pos = seed, b"", 0

    def read(self, n):
        while len(self.buffer) - self.pos < n:
            self.buffer = hashlib.shake_256(self.seed).digest(max(2 * len(self.buffer), 1088))
        out = self.buffer[self.pos:self.pos + n]
        self.pos += n
        return out


def bits(positions):
    value = 0
    for position in positions:
        value |= 1 << position
    return value


# ---------- the functions H, K, and L ----------

def function_h(p, m):
    """H(m): the error (e0, e1), of weight t, from the 32 bytes m."""
    e = bits(sample_positions(Shake256Stream(m), 2 * p.r, p.t))
    return e & ((1 << p.r) - 1), e >> p.r


def function_l(p, e0, e1):
    return hashlib.sha3_384(to_bytes(e0, p) + to_bytes(e1, p)).digest()[:p.ell]


def function_k(p, m, c0, c1):
    return hashlib.sha3_384(m + to_bytes(c0, p) + c1).digest()[:p.ell]


# ---------- the Black-Gray-Flip decoder (Algorithm 1 of the specification) ----------

def counters(s, h_support, r):
    """For every position j, the number of positions k of h with the bit (j + k) of s set, as bit planes.
    The reference code counts one position at a time. Both ways give the same counts."""
    planes = []
    for k in h_support:
        carry = rotate(s, -k, r)  # bit j of this is bit j + k of s
        for i in range(len(planes)):
            planes[i], carry = planes[i] ^ carry, planes[i] & carry
            if not carry:
                break
        else:
            planes.append(carry)
    return planes


def at_least(planes, threshold, r):
    """The set of positions whose counter is at least `threshold`."""
    full = (1 << r) - 1
    if threshold <= 0:
        return full
    if threshold >= 1 << len(planes):
        return 0
    greater, equal = 0, full
    for i in range(len(planes) - 1, -1, -1):
        if (threshold >> i) & 1:
            equal &= planes[i]
        else:
            greater |= equal & planes[i]
            equal &= ~planes[i] & full
    return greater | equal


def syndrome_of(e0, e1, h0, h1, r):
    return mul(h0, e0, r) ^ mul(h1, e1, r)


def decode(p, s, h0, h1, log=None):
    """The error (e0, e1) with e0 h0 + e1 h1 = s, or None when the decoder fails."""
    r = p.r
    s0, s1 = support(h0), support(h1)
    e0 = e1 = 0
    black = [0, 0]
    gray = [0, 0]
    for iteration in range(1, p.iterations + 1):
        syndrome = s ^ syndrome_of(e0, e1, h0, h1, r)
        weight = bin(syndrome).count("1")
        threshold = max(int(p.c0 + p.c1 * weight), p.floor_t)
        planes = [counters(syndrome, s0, r), counters(syndrome, s1, r)]
        flip = [at_least(planes[b], threshold, r) for b in (0, 1)]
        gray = [at_least(planes[b], threshold - p.tau, r) & ~flip[b] for b in (0, 1)]
        black = flip[:]
        e0, e1 = e0 ^ flip[0], e1 ^ flip[1]
        if log is not None:
            log.append((iteration, weight, threshold, bin(flip[0]).count("1") + bin(flip[1]).count("1")))
        if iteration == 1:
            for mask in (black, gray):  # first the black positions, then the gray ones, with a threshold of (d + 1) / 2 + 1
                syndrome = s ^ syndrome_of(e0, e1, h0, h1, r)
                planes = [counters(syndrome, s0, r), counters(syndrome, s1, r)]
                limit = (p.d + 1) // 2 + 1
                moved = [at_least(planes[b], limit, r) & mask[b] for b in (0, 1)]
                e0, e1 = e0 ^ moved[0], e1 ^ moved[1]
                if log is not None:
                    log.append((0, bin(syndrome).count("1"), limit, bin(moved[0]).count("1") + bin(moved[1]).count("1")))
    if s == syndrome_of(e0, e1, h0, h1, r):
        return e0, e1
    return None


# ---------- the key encapsulation mechanism ----------

def keygen(p, seed1, seed2):
    """The secret key (h0, h1, sigma) and the public key h, from two 32-byte seeds."""
    stream = Shake256Stream(seed1)
    h0 = bits(sample_positions(stream, p.r, p.d))
    h1 = bits(sample_positions(stream, p.r, p.d))
    h = mul(h1, inverse(h0, p.r), p.r)
    return (h0, h1, seed2), h


def encaps(p, h, m):
    """The ciphertext (c0, c1) and the shared key, from the public key and 32 bytes m."""
    e0, e1 = function_h(p, m)
    c0 = e0 ^ mul(h, e1, p.r)
    c1 = bytes(a ^ b for a, b in zip(m, function_l(p, e0, e1)))
    return (c0, c1), function_k(p, m, c0, c1)


def decaps(p, secret_key, ciphertext, log=None):
    h0, h1, sigma = secret_key
    c0, c1 = ciphertext
    s = mul(h0, c0, p.r)
    error = decode(p, s, h0, h1, log) or (0, 0)  # a failure counts as the error (0, 0)
    m_prime = bytes(a ^ b for a, b in zip(c1, function_l(p, *error)))
    if function_h(p, m_prime) == error:
        return function_k(p, m_prime, c0, c1)
    return function_k(p, sigma, c0, c1)  # implicit rejection


if __name__ == "__main__":
    p = LEVEL1
    secret_key, h = keygen(p, bytes(range(32)), bytes(range(32, 64)))
    (c0, c1), key = encaps(p, h, bytes(range(64, 96)))
    print("public key (%d bytes) starts with %s" % (p.r_bytes, to_bytes(h, p)[:24].hex()))
    print("ciphertext (%d bytes) starts with %s" % (p.r_bytes + p.ell, to_bytes(c0, p)[:24].hex()))
    print("shared key from encapsulation:", key.hex())
    print("shared key from decapsulation:", decaps(p, secret_key, (c0, c1)).hex())
    broken = decaps(p, secret_key, (c0 ^ (1 << 5) ^ (1 << 700) ^ (1 << 9000) ^ (1 << 12000), c1))
    print("shared key after 4 bit flips in c0:", broken.hex())

Running it produces this output:

public key (1541 bytes) starts with 002924183bbfa89110027b76e4107ce712c4b362b563139e
ciphertext (1573 bytes) starts with fc0a8c17e1ec36f66b814b2872ab86736ad0391026846a15
shared key from encapsulation: 043a87d63a93ce11809b594f5d1906aa267acb8637fc56646910450c9f68e3d1
shared key from decapsulation: 043a87d63a93ce11809b594f5d1906aa267acb8637fc56646910450c9f68e3d1
shared key after 4 bit flips in c0: 211c2f2beb6fba5e61173a094c26f17b1cc3fc576d0ae184693a8efb23bebb98

I checked this code against the official known-answer tests of the BIKE round 4 package, which belong to version 5.1 and which I read from the files and did not run. For each of the three levels, the test reads the 100 test vectors from the file. For each vector, it starts the generator of the test suite with the given seed, which I wrote from the code in the package. It then generates the key pair, encapsulates a message, and decapsulates. The public key, the secret key, the ciphertext, and the shared key all match for all 300 vectors, and decapsulation recovers the shared key every time. The AES inside the generator matches the vector of FIPS 197. The two hash functions agree with the SHAKE256 and SHA3-384 of Python. I also compared my reading of the sampler and of the decoder with the reference source of the package. I did not run that code.

Further tests cover the arithmetic: inverses multiply back to 1, and multiplication is commutative. The sampler returns exactly the requested number of positions. A single flipped bit is rejected, and a changed c1 is rejected too. The visualizer code has its own SHAKE256 and SHA3-384. They match OpenSSL for input lengths from 0 to 299 and for larger ones. The page code matches all 47 test vectors that this Python code produces, including known-answer tests of all three levels. I ran its page in a simulated browser.

Where It Stands

• A NIST candidate that was not selected. BIKE reached the fourth round of the NIST process. NIST selected HQC and said that the other fourth-round algorithms are not under consideration by the current process. The report adds that NIST found BIKE a good complement to ML-KEM, because it rests on a different problem, and that it offers smaller keys and ciphertexts than HQC.
• Ephemeral keys. The specification says that BIKE is designed primarily for synchronous protocols such as TLS with a fresh key pair for each session, and that a given private key should be used for only one decapsulation. This usage gives forward secrecy, and IND-CPA security suffices for it.
• Static keys. The specification allows long-term keys, but it says that this needs IND-CCA security and a low enough failure rate, and that it loses forward secrecy.
• Code-based alternatives. Classic McEliece has public keys that are much larger than BIKE’s, and a track record that goes back to 1978. BIKE trades both away for small keys, and it needs a decoder whose failure rate must be estimated.
• Experiments in protocols. The NIST report cites experiments with TLS 1.3 and QUIC that compare BIKE and HQC. HQC gives faster handshakes under good network conditions, and BIKE performs better when there is packet loss.

Limitations

This is a teaching implementation, not a production one:

• Not constant time. The code branches on secret values, and Python integers take time that depends on their size. The specification says the decoder must be constant time to avoid side-channel attacks.
• Slow inversion. The inversion by Euclid’s algorithm leaks the number of steps. Real implementations use a fixed-time method.
• No randomness source. The functions take their seeds as arguments. A real program must draw them from a secure random source.
• Own decoder code. The decoder is my bit-sliced formulation of the Algorithm of the specification. The known-answer tests verify the sampler, the hashes, the key generation, and the encapsulation completely, and they verify the decoder only on inputs that it decodes correctly. They cannot show how it behaves near its failure rate.
• Key reuse. The code does not stop you from decapsulating many ciphertexts with one key. The specification advises against it.
• Level choice. The code runs all three levels, and the third level is slow in Python.

Security Status

The security of BIKE rests on two problems from coding theory, which the specification calls the quasi-cyclic syndrome decoding problem and the quasi-cyclic codeword finding problem. Their best known solvers are variants of information set decoding. The parameters are chosen so that those solvers need more work than the claimed level. The specification proves IND-CPA security under these two assumptions. It proves IND-CCA security only under a third assumption, that the decoder is correct. That assumption is the reason that the choice of the decoder and its failure rate matter so much.

The known weak points are the ones discussed above. The failure rate is estimated, not proven. Weak keys can raise it. A decoder must run in constant time. Keys should be used once. Against quantum computers, the specification treats the problems as hard, and it chose its security levels with that in mind. For comparisons, see the Kyber guide for a lattice-based KEM and the Classic McEliece guide for a code-based one with a long record.

FAQ

What is a quasi-cyclic code?

A code whose parity-check matrix is made of circulant blocks, where each row is the previous row shifted by one place. A circulant matrix is the same thing as a polynomial in the ring F2[X] / (X^r - 1). This is why BIKE can write all its operations as polynomial arithmetic and store one polynomial of r bits in place of a whole matrix of r by r bits.

Why is the secret key sparse?

Because a sparse parity-check matrix allows the simple bit-flipping decoder. The public key h = h1 * h0^-1 is dense and hides that structure. Recovering the sparse pair from h is one of the hard problems that the security rests on.

What does the decoder do when it fails?

It returns a failure. Decapsulation then takes e' = (0, 0), computes m', finds that e' is not H(m'), and returns K(sigma, c). The sender and the receiver end up with different keys, and an attacker cannot tell a decoding failure from a modified ciphertext.

Why was BIKE not selected by NIST?

NIST has confidence in the IND-CPA security of BIKE and HQC, and both need a sufficiently low decryption failure rate for IND-CCA2 security. NIST judged the analysis of that rate to be less mature for BIKE than for HQC. It also noted that HQC needs no further changes for the security properties it wants. NIST selected only HQC and considers the other fourth-round algorithms not under consideration by the current process.

Can I use BIKE with a static key?

The specification allows it in principle but advises that BIKE is designed for ephemeral keys, with a fresh pair for each session and a single decapsulation for each key. Static keys require IND-CCA security and a failure rate low enough, and they give up forward secrecy.

How does BIKE compare with ML-KEM?

The security of BIKE rests on coding problems instead of lattices. NIST found that BIKE would complement ML-KEM well, because it has a different underlying security problem and balanced performance characteristics. The Kyber guide covers the scheme that became ML-KEM.

References

1. Aragon, Nicolas, and 17 other authors, who are listed in the specification. “BIKE: Bit Flipping Key Encapsulation.” Round 4 Submission, version 5.1, 10 October 2022. Available at: https://bikesuite.org

2. Alagic, Gorjan, et al. “Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Process.” NIST Internal Report 8545, March 2025. Available at: https://doi.org/10.6028/NIST.IR.8545

3. NIST. “Round 4 Submissions.” Post-Quantum Cryptography Standardization, the BIKE submission package with the reference implementation and the known-answer tests of version 5.1. Available at: https://csrc.nist.gov/projects/post-quantum-cryptography. The package itself is at BIKE-Round4.zip

4. BIKE team. “BIKE: Bit Flipping Key Encapsulation,” specification version 5.2, 10 October 2024, with its own known-answer tests. Available at https://bikesuite.org

5. Federal Information Processing Standard 197. “Advanced Encryption Standard (AES).” NIST, November 2001. Available at: https://doi.org/10.6028/NIST.FIPS.197