I Want to Ride My BIKE: Customizing Bit-Flipping Decoders for Ephemeral Key KEMs

What it is

A preprint (ePrint 2026/2511, Preprint, approved 2026-10-17) on shrinking BIKE-style QC-MDPC code-based KEMs by tuning the decoder for ephemeral key pairs. It gives the first optimized implementation of the BF-max bit-flipping decoder and combines it with other decoders from the literature. The result is a family of decoding strategies with different trade-offs among DFR, execution time, public-key size and ciphertext size.

How it works

• Code-based KEMs normally need larger parameters to lower the Decoding Failure Rate (DFR), which inflates keys and ciphertexts.
• If each secret key is used for a single decapsulation, attackers have few chances to observe and exploit decryption failures. That lets the design accept a higher DFR and use smaller parameters.
• BF-max corrects more errors than the parallel bit-flipping decoders BIKE uses today, but its computational structure is harder to implement efficiently. That is the gap the paper's implementation closes.

Preconditions / Affected

The size savings depend on the ephemeral-key assumption: one decapsulation per secret key. The abstract says the baseline it beats, LeanBIKE, is also designed for ephemeral use. The 22% (vs. BIKE) and 2.79x (vs. HQC) combined-size figures compare against schemes that target long-term keys, so they are context rather than a like-for-like comparison. The only like-for-like result is the 7.8% reduction in both public-key and ciphertext size vs. LeanBIKE, at similar execution time and DFR.

What to do

• Consider this only for protocols that generate a fresh KEM key pair per handshake, such as IKEv2, where the paper says no code-based KEM would otherwise fit.
• Do not treat it as a drop-in replacement for standard BIKE or HQC where keys are reused. The DFR-for-size trade relies on keys not being reused.
• The abstract gives no code link, parameter table or concrete byte counts, so read the full paper for those before committing.

Caveats

• It is an unreviewed preprint, and the figures above come from the abstract alone.
• The abstract does not state which parameter set was chosen, the absolute sizes or the DFR value.
• It does not describe how the design behaves if a key is accidentally reused.