<figure><img src="image_1.png" /></figure>

HAL
open science

# BIKE Decoding Failure, Weak Keys & Error Floors

Nicolas Sendrier

► To cite this version:

Nicolas Sendrier. BIKE Decoding Failure, Weak Keys & Error Floors. 2024 NIST Post-Quantum Cryptography Seminar, NIST, Sep 2024, Gaithersburg, United States. [https://doi.org/10.1145/3784846](https://doi.org/3784846)

HAL Id: hal-04914446

https://inria.hal.science/hal-04914446v1

Submitted on 27 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
# BIKE
## Bit-flipping Key Encapsulation

NIST PQC Seminars
September 27th, 2024

<figure><img src="image_2.png" /></figure>

Nicolas Aragon, University of Limoges, France
Paulo L. Barreto, University of Washington Tacoma, USA
Slim Bettaieb, TII, UAE
Loïc Bidoux, TII, UAE
Olivier Blazy, Ecole Polytechnique, France
Jean-Christophe Deneuville, ENAC, Federal University of Toulouse, France
Philippe Gaborit, University of Limoges, France
Santosh Ghosh, Nvidia, USA
Shay Gueron, University of Haifa, and Meta, Israel & USA

Tim Güneysu, Ruhr-Universität Bochum & DFKI, Germany
Carlos Aguilar Melchor, University of Toulouse, France
**Rafael Misoczki**, Meta, USA
Edoardo Persichetti, Florida Atlantic University, USA
Jan Richter-Brockmann, Ruhr-Universität Bochum, Germany
**Nicolas Sendrier**, INRIA, France
Jean-Pierre Tillich, INRIA, France
Valentin Vasseur, Thales, France
Gilles Zémor, IMB, University of Bordeaux, France
# Agenda

* BIKE Overview

* Key Features

* Performance

* Specification

* Security

* Modes of usage

* BIKE Decoding

* Improved Results

<figure><img src="image_3.png" /></figure>
# Key Features

* Competitive performance

* "BIKE has the most competitive performance among the non-lattice based KEMs" [NIST-IR8413]

* Robust security

* Based on **well-known** coding-theory problems

* Foundational cryptosystem was proposed **more than a decade ago** [MTSB'13]

* Simple implementation

* Polynomial ring arithmetic

* Bit flipping decoding

<figure><img src="image_4.png" /></figure>
# BIKE Performance

Security Level 1

<table><thead><tr><th rowspan="2"></th><th colspan="2">Communication Bandwidth (bytes)</th><th colspan="3">Speed (kcycles)</th></tr><tr><th>Public Key</th><th>Ciphertext</th><th>Key Generation</th><th>Encapsulation</th><th>Decapsulation</th></tr></thead><tbody><tr><th>BIKE</th><td>1,540</td><td>1,572</td><td>589</td><td>97</td><td>1,135</td></tr><tr><th>HQC</th><td>2,249</td><td>4,497</td><td>187</td><td>419</td><td>833</td></tr><tr><th>Classic McEliece</th><td>261,120</td><td>128</td><td>140,870</td><td>46</td><td>137</td></tr><tr><th>Kyber</th><td>800</td><td>768</td><td>123</td><td>155</td><td>289</td></tr></tbody></table>

BIKE performance numbers from Drucker, Gueron, Kostic, "Additional implementation of BIKE (Bit Flipping Key Encapsulation)", https://github.com/awslabs/bike-kem.

<figure><img src="image_5.png" /></figure>
# BIKE Performance

Security Level 3

<table><thead><tr><th rowspan="2"></th><th colspan="2">Communication Bandwidth (bytes)</th><th colspan="3">Speed (kcycles)</th></tr><tr><th>Public Key</th><th>Ciphertext</th><th>Key Generation</th><th>Encapsulation</th><th>Decapsulation</th></tr></thead><tbody><tr><th>BIKE</th><td>3,082</td><td>3,114</td><td>1,823</td><td>223</td><td>3,887</td></tr><tr><th>HQC</th><td>4,522</td><td>9,042</td><td>422</td><td>946</td><td>1,662</td></tr><tr><th>Classic McEliece</th><td>524,160</td><td>188</td><td>441,517</td><td>83</td><td>273</td></tr><tr><th>Kyber</th><td>1,184</td><td>1,088</td><td>213</td><td>249</td><td>275</td></tr></tbody></table>

BIKE performance numbers from Drucker, Gueron, Kostic, "Additional implementation of BIKE (Bit Flipping Key Encapsulation)", https://github.com/awslabs/bike-kem.

<figure><img src="image_6.png" /></figure>
# BIKE Overview

* Niederreiter-based KEM instantiated with QC-MDPC codes.

* Leverage Fujisaki-Okamoto Transform [DGKP'21].

* [New] State-of-the-art QC-MDPC Decoding Failure Rate analysis.

* [New] BIKE-Flip Decoder with strengthened resilience to weak keys.

<figure><img src="image_7.png" /></figure>
# BIKE Overview

* Block circulant matrices are isomorphic to $\mathcal{R} = \mathbb{F}_2[x]/(x^r - 1)$.

* Index 2 Quasi-Cyclic codes admit a parity check matrix ($n = 2r$).

$$ H = \left[ \begin{array}{c|c} h_0 & h_1 \\ \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3] \draw (0,0) circle (0.4); \node at (0.2,0) {0}; \draw (0.4,0) circle (0.4); \node at (0.2,0.4) {$h_0$}; \draw (0.4,0.4) circle (0.4); \node at (0.2,0.8) {$h_1$}; \end{tikzpicture} & \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3] \draw (0,0) circle (0.4); \node at (0.2,0) {$h_0$}; \draw (0.4,0) circle (0.4); \node at (0.2,0.4) {$h_1$}; \draw (0.4,0.4) circle (0.4); \node at (0.2,0.8) {$h_0$}; \draw (0.4,0.8) circle (0.4); \node at (0.2,1.2) {$h_1$}; \end{tikzpicture} \end{array} \right] \quad \text{with } (h_0, h_1) \in \mathcal{R}^2 $$

* QC-MDPC if $w = |h_0| + |h_1| \approx \sqrt{n}$.

* Decoding: find $(e_0, e_1) \in \mathcal{R}^2$ s.t. $s = e_0h_0 + e_1h_1$ for small $t = |e_0| + |e_1|$.

* Bit-flipping decoders succeed (i.e. $(e_0, e_1) = \text{decode}(e_0h_0 + e_1h_1, h_0, h_1)$) with high probability if $t \approx w \approx \sqrt{n}$.
# BIKE Specification

**KeyGen**: () ↦ (h₀, h₁, σ), h

Output: (h₀, h₁, σ) ∈ H<sub>w</sub> × M, h ∈ R

1: (h₀, h₁) ←<sup>D</sup> H<sub>w</sub> ▷ (1)

2: h ← h₁h<sub>0</sub><sup>-1</sup>

3: σ ←<sup>$</sup> M

**Encaps**: h ↦ K, c

Input: h ∈ R

Output: K ∈ K, c ∈ R × M

1: m ←<sup>$</sup> M

2: (e₀, e₁) ← H(m)

3: c ← (e₀ + e₁h, m ⊕ L(e₀, e₁))

4: K ← K(m, c)

**Decaps**: (h₀, h₁, σ), c ↦ K

Input: ((h₀, h₁), σ) ∈ H<sub>w</sub> × M, c = (c₀, c₁) ∈ R × M

Output: K ∈ K

1: e' ← decoder(c₀h₀, h₀, h₁) ▷ e' ∈ R<sup>2</sup> ∪ {⊥}

2: m' ← c₁ ⊕ L(e') ▷ with the convention ⊥ = (0, 0)

3: **if** e' = H(m') **then** K ← K(m', c) **else** K ← K(σ, c)

## Parameters

* r : block length

* w : row weight

* t : error weight

* ℓ : shared secret size

* M : message space in {0, 1}<sup>ℓ</sup>

* K : key space in {0, 1}<sup>ℓ</sup>

## NOTATION

F₂: Binary finite field.

R: Cyclic polynomial ring F₂[X]/(X³ - 1).

H<sub>w</sub>: Private key space {⟨h₀, h₁⟩ ∈ R<sup>2</sup> | |h₀| = |h₁| = w/2}

E<sub>t</sub>: Error space {⟨e₀, e₁⟩ ∈ R<sup>2</sup> | |e₀| + |e₁| = t}

|g|: Hamming weight of a binary polynomial g ∈ R.

u ←<sup>$</sup> U: Variable u is sampled uniformly at random from the set U.

⊕: exclusive or of two bits, componentwise with vectors

## Functions

* H : M → E<sub>t</sub>.

* K : M × R × M → K.

* L : R<sup>2</sup> → M

<figure><img src="image_8.png" /></figure>
# BIKE Security

* **Assumption 1.** Hardness of $QCSD_{r,t}$

* **Assumption 2.** Hardness of $QCCF_{r,w}$

* **Assumption 3.** Correctness of the decoder.

BIKE is proven IND-CPA secure under assumptions 1 and 2.

BIKE is proven IND-CCA secure under assumptions 1, 2, and 3.

<figure><img src="image_9.png" /></figure>
# BIKE Security

**QCSD<sub>(r,t)</sub>:** Quasi-Cyclic Syndrome Decoding.

Instance: $(h, s) \in \mathcal{R}_{odd} \times \mathcal{R}_{p(t)}$ an integer $t > 0$.

Property: There exists $(e_0, e_1) \in \mathcal{E}_t$ such that $e_0 + e_1 h = s$.

**QCCF<sub>(r,w)</sub>:** Quasi-Cyclic Codeword Finding

Instance: $h \in \mathcal{R}_{odd}$, an even integer $w > 0$, with $w/2$ odd.

Property: There exists $(h_0, h_1) \in \mathcal{H}_w$ such that $h_1 + h_0 h = 0$.

**Decoding correctness:** refers to [HHK'17] where a KEM is $\delta$-correct if the decapsulation fails with probability at most $\delta$ on average over all keys and messages. Similarly, a decoder will be $\delta$-correct if its failure rate is at most $\delta$ on average when the input is drawn uniformly.

<figure><img src="image_10.png" /></figure>
# BIKE Practical Security

* The best techniques to solve codeword finding and syndrome decoding:

* Variants of Prange's Information Set Decoding (ISD) [Pran62]

* Work factor of any ISD variant A to decode t errors in a (n, k)-binary code:

$$WF_A(n, k, t) = 2^{ct(1+o(1))}$$

* The quasi-cyclic case

* Codeword finding and decoding are a bit easier for quasi-cyclic codes.

* Adversary gains a factor r for codeword finding and factor $\sqrt{r}$ for decoding

* The best quantum attack against BIKE

* Grover's algorithm [Gro96] applied to ISD

<figure><img src="image_11.png" /></figure>
# BIKE - Modes of Usage

* BIKE can use different decoders without affecting interoperability.

* The decoder must be implementable in constant-time to avoid side-channel attacks, and its DFR must be low enough to match the security requirement.

* BIKE ephemeral keys usage.

* The party that initiates a session needs to: a) Generate a fresh private/public key pair for every session; b) Refuse to decapsulate more than one incoming ciphertext with that key.

* The IND-CPA security property suffices for this type of usage.

* BIKE long-term static keys usage.

* This usage requires IND-CCA security and therefore a low enough DFR for the specified decoder (see next discussion). However, this usage model implies the loss of forward secrecy.
Nicolas' Slides on Decoding and DFR recent results.

<figure><img src="image_12.png" /></figure>
# References

* [DGK]: Drucker, Gueron, Kostic, "Additional implementation of BIKE (Bit Flipping Key Encapsulation)". https://github.com/awslabs/bike-kem.

* [DGK'20]: Drucker, N., Gueron, S., Kostic, D.: Fast Polynomial Inversion for Post Quantum QC-MDPC Cryptography. Cyber Security Cryptography and Machine Learning. pp. 110–127. Springer International Publishing, Cham (2020). https://doi.org/10.1007/978-3-030-49785-9_8

* [DGK'23]: Drucker, N., Gueron, S., Kostic, D.: To Reject or Not Reject: That Is the Question. The Case of BIKE Post Quantum KEM. In: Latifi, S. (ed.) ITNG 2023 20th International Conference on Information Technology-New Generations. pp. 125–131. Springer International Publishing, Cham (2023).

* [DGKP'21] Drucker, N., Gueron, S., Kostic, D., Persichetti, E.: On the applicability of the Fujisaki-Okamoto transformation to the BIKE KEM. Int. J. Comput. Math. Comput. Syst. Theory 6(4), 364–374 (2021). https://doi.org/10.1080/23799927.2021.1930176

* [GHJ'22]: Qian Guo, Clemens Hlauschek, Thomas Johansson, Norman Lahr, Alexander Nilsson, and Robin Leander Schröder. Don't reject this: Key-recovery timing attacks due to rejection-sampling in HQC and BIKE. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2022(3):223–263, 2022.

* [HHK'17]: Dennis Hofheinz, Kathrin Hövelmanns, and Eike Kiltz. A modular analysis of the Fujisaki-Okamoto transformation. In Theory of Cryptography Conference, pages 341–371. Springer, 2017.

* [MTSB'13]: Misoczki, Rafael, Jean-Pierre Tillich, Nicolas Sendrier, and Paulo SLM Barreto. "MDPC-McEliece: New McEliece variants from moderate density parity-check codes." In 2013 IEEE international symposium on information theory, pp. 2069-2073. IEEE, 2013.

* [Sen'23]: Nicolas Sendrier. Secure sampling of constant-weight words – Application to BIKE. Cryptology ePrint Archive, Report 2021/1631, August 2023.

* [WWW'23]: Wang, Tianrui, Anyu Wang, and Xiaoyun Wang. "Exploring Decryption Failures of BIKE: New Class of Weak Keys and Key Recovery Attacks." Annual International Cryptology Conference. Cham: Springer Nature Switzerland, 2023.

<figure><img src="image_13.png" /></figure>
Questions?

https://bikesuite.org

<figure><img src="image_14.png" /></figure>
# BIKE Decoding Failure
## Weak Keys & Error Floors

Nicolas Sendrier, Inria, France

<figure><img src="image_15.png" /></figure>

NIST PQC Seminars, September 27, 2024
Introduction:
BIKE Security & DFR
QC-MDPC (Quasi-Cyclic Moderate Parity Check) Codes

Block circulant $r \times r$ binary matrices are isomorphic to $\mathcal{R} = \mathbb{F}_2[x]/(x^r-1)$

---

Index 2 QC codes admit a parity check matrix ($n = 2r$)

$$ H = \left[ \begin{array}{c|c} h_0 & h_1 \\ \xrightarrow{\circ} & \xrightarrow{\circ} \end{array} \right] \quad \text{with } (h_0, h_1) \in \mathbb{R}^2 $$

QC-MDPC if $w = |h_0| + |h_1| \approx \sqrt{n}$

---

Decoding: find $(e_0, e_1) \in \mathbb{R}^2$ s.t. $s = e_0h_0 + e_1h_1$ for small $t = |e_0| + |e_1|$

Bit-flipping decoding succeeds* with high probability if $t \approx w \approx \sqrt{n}$

<figure><img src="image_16.png" /></figure>

<footnote>*successful decoding means $(e_0, e_1) = \text{decode}(e_0h_0 + e_1h_1, h_0, h_1)$</footnote>
McEliece (Niederreiter) scheme with index 2 binary QC-MDPC codes

$$ \mathcal{R} = \mathbf{F}_2[x]/(x^r - 1) $$

$$ \mathcal{H}_w = \{(h_0, h_1) \in \mathbb{R}^2 \mid |h_0| = |h_1| = d = w/2\} $$

$$ \mathcal{E}_t = \{(e_0, e_1) \in \mathbb{R}^2 \mid |e_0| + |e_1| = t\} $$

**Secret:** $(h_0, h_1) \in \mathcal{H}_w$

**Public:** $h = h_0^{-1}h_1 \in \mathbb{R}$

**Encrypt:** $(e_0, e_1) \in \mathcal{E}_t \mapsto c = e_0 + he_1$

**Decrypt:** $c \mapsto (e_0, e_1) = \text{decode}(h_0c, h_0, h_1)$

<table><thead><tr><th>Security</th><th>λ</th><th>r</th><th>d</th><th>t</th></tr></thead><tbody><tr><td>Level 1</td><td>128</td><td>12 323</td><td>71</td><td>134</td></tr><tr><td>Level 3</td><td>192</td><td>24 659</td><td>103</td><td>199</td></tr><tr><td>Level 5</td><td>256</td><td>40 973</td><td>137</td><td>264</td></tr></tbody></table>

<figure><img src="image_17.png" /></figure>
Decoding Failure Rate

$$
\mathcal{R} = \mathbf{F}_2[x]/(x^r - 1)
$$

$$
\mathcal{H}_w = \{(h_0, h_1) \in \mathbb{R}^2 \mid |h_0| = |h_1| = d = w/2\}
$$

$$
\mathcal{E}_t = \{(e_0, e_1) \in \mathbb{R}^2 \mid |e_0| + |e_1| = t\}
$$

Decoding Failure Rate:

$$
DFR = \Pr((e_0, e_1) \neq \text{decode}(e_0h_0 + e_1h_1, h_0, h_1))
$$
with $(e_0, e_1)$ and $(h_0, h_1)$ uniformly distributed in $\mathcal{E}_t$ and $\mathcal{H}_w$

<figure><img src="image_18.png" /></figure>
# DFR & CCA Security

IND-CCA reduction [HHK17]: breaking BIKE requires a computational effort

$$ \geq \min \left( \frac{1}{\text{DFR}}, 2^{\lambda_{\text{CPA}}} \right) $$

$2^{\lambda_{\text{CPA}}}$: “hardness of decoding”

Proving DFR $\le 2^{-\lambda}$ (e.g. $\lambda = 128$) by simulation is out of reach

---

High DFR allows failure attacks:

[Guo, Johansson, Stankovski, Asiacrypt 2016]

[Wang, Wang, Wang, Crypto 2023]

[HHK17] Hofheinz, Hövelmanns, Kiltz, A modular analysis of the Fujisaki-Okamoto transformation, TCC 2017

<figure><img src="image_19.png" /></figure>
BIKE DFR Estimates (1)

<figure><img src="image_20.png" /></figure>

Fix the row weight *w* and the error weight *t*

The failure rate can be measured for small block length *r*

<figure><img src="image_21.png" /></figure>
BIKE DFR Estimates (2)

<figure><img src="image_22.png" /></figure>

There are models for the waterfall region allowing extrapolation: asymptotic [Tillich, 2018], Markovian [Sendrier, Vasseur, 2019]

There are works in progress to model the error floor region

<figure><img src="image_23.png" /></figure>
# Roadmap

Introduction: BIKE Security & DFR

I. Coordinate Distance Spectrum

II. Weak Keys

III. *m*-gathering Weak Keys

IV.1 *m*-gathering Key Spectrum

IV.2 Bogus Positions

IV. New BIKE Decoder

V. Weak Keys and Error Floors: Perspectives and Open Questions

<figure><img src="image_24.png" /></figure>
# I. Coordinate Distance Spectrum
[Guo, Johansson, Stankovski, Asiacrypt 2016]

Distance spectrum, $h \in \mathcal{R} = \mathbb{F}_2[x]/(x^r - 1)$

$$ \mathrm{Sp}(h) = \{\mathrm{d}(i, j) \mid h_i = h_j = 1\}. $$

Coordinate distance

$$ \mathrm{d}(i, j) = \min(i - j \mod r, j - i \mod r), \quad 0 \le \mathrm{d}(i, j) \le \lfloor r/2 \rfloor, $$

Multiplicity

$$ \mu(\delta, h) = \left| \{ (i, j) \mid h_i = h_j = 1, 0 \le i \le j < r, \mathrm{d}(i, j) = \delta \} \right|. $$

<figure><img src="image_25.png" /></figure>
Model: draw $d(d-1)/2$ elements uniformly in $\{1, \dots, (r-1)/2\}$ with repetition.

Ex: $(r, d) = (12323, 71)$ $h \in \mathbb{R}$ uniform of weight $d$

<table><thead><tr><th></th><th>Model</th><th>Simulation</th></tr></thead><tbody><tr><td>$|\text{Sp}(h)|$</td><td>2045.1</td><td>2054.4</td></tr><tr><td>$\mu = 1$</td><td>1660.4</td><td>1675.4</td></tr><tr><td>$\mu = 2$</td><td>334.8</td><td>332.1</td></tr><tr><td>$\mu = 3$</td><td>44.98</td><td>42.64</td></tr><tr><td>$\mu = 4$</td><td>4.53</td><td>3.99</td></tr><tr><td>$\mu = 5$</td><td>0.36</td><td>0.29</td></tr><tr><td>$\mu = 6$</td><td>0.024</td><td>0.017</td></tr></tbody></table>

$$ \frac{r-1}{2} = 6161 $$

$$ \frac{d(d-1)}{2} = 2485 $$

(each row gives the average number of distances with multiplicity $\mu$)

<figure><img src="image_26.png" /></figure>
II. Weak Keys
Known Weak Keys

Parameter $m > 0$, $m < d$, typical value 10 to 30

**Type I:** [Drucker, Gueron, Kostic, 2019]

<figure><img src="image_27.png" /></figure>

+ blockwise rotation + isomorphisms $x \mapsto x^i$, $0 \le i < r$
→ multiplicities $m-1, m-2, \dots$ appear once

**Type II:** [Vasseur, 2021] one distance has multiplicity $\ge m$

**Type III:** [Vasseur, 2021] one inter-block distance has multiplicity $\ge m$

No indication that DFR($W$) · density($W$) $\ge 2^{-\lambda}$ if $W$ is one of those sets

<figure><img src="image_28.png" /></figure>
# m-gathering Weak Keys

[Wang, Wang, Wang, Crypto 2023]

$h_0$ and $h_1$ of weight $d$ in $\mathbb{F}_2[x]/(x^r - 1)$ a BIKE secret key

<figure><img src="image_29.png" /></figure>

Generalize by applying rotations and isomorphisms $x \mapsto x^i$, $0 < i < r$
e.g. $(m, \epsilon) = (4000, 1)$, density is $2^{-87.28}$ and the DFR is $2^{-29.33}$
→ contribution to the average DFR is $\ge 2^{-117}$
→ successful attack with $2^{117}$ Decaps queries

The same paper shows a second attack in $2^{98}$ with message reuse
It is canceled by binding the key to the message as in Kyber

[Drucker, Gueron, Kostic, 2021], Binding BIKE Errors to a Key Pair, LNCS 12716

<figure><img src="image_30.png" /></figure>
III. m-gathering Weak Keys
Observations on *m*-gathering Failures

1. Failure probability is strongly correlated with the spectrum cardinality.

2. The bit-flipping decoder features *bogus positions*: positions which are correct but look like errors.

<figure><img src="image_31.png" /></figure>
IV.1 *m*-gathering Key Spectrum
Spectrum Cardinality vs DFR for *m*-gathering Keys

<figure><img src="image_32.png" /></figure>

(the spectrum cardinality of a typical element of $\mathcal{R}$ is 2050)

<figure><img src="image_33.png" /></figure>
Spectrum Model for *m*-gathering Keys

Model: (for $\epsilon = 0$, $m < r/2$ before applying $x \mapsto x^i$)
draw $d(d-1)/2$ elements in $\{1, \dots, m-1\}$ with repetition according to
the distribution: $\text{Pr}(\delta) = \frac{2(m-\delta)}{m(m-1)}$, $1 \le \delta < m$

<figure><img src="image_34.png" /></figure>

<figure><img src="image_35.png" /></figure>
Distance Multiplicity for *m*-gathering Keys

<table><thead><tr><th rowspan="3"></th><th colspan="6">(m, ε)</th></tr><tr><th colspan="2">(2000, 0)</th><th colspan="2">(4000, 0)</th><th colspan="2">(6000, 0)</th><th rowspan="2">uniform</th></tr><tr><th>model</th><th>simul</th><th>model</th><th>simul</th><th>model</th><th>simul</th></tr></thead><tbody><tr><td>μ = 1</td><td>571.0</td><td>579.5</td><td>1 135.5</td><td>1 154.6</td><td>1 459.2</td><td>1 479.2</td><td>1 660.4</td></tr><tr><td>μ = 2</td><td>364.1</td><td>374.2</td><td>418.1</td><td>421.7</td><td>373.6</td><td>372.5</td><td>334.8</td></tr><tr><td>μ = 3</td><td>192.6</td><td>195.7</td><td>120.9</td><td>117.7</td><td>73.92</td><td>70.45</td><td>44.98</td></tr><tr><td>μ = 4</td><td>85.99</td><td>84.37</td><td>28.65</td><td>26.20</td><td>11.87</td><td>10.54</td><td>4.53</td></tr><tr><td>μ = 5</td><td>33.01</td><td>30.52</td><td>5.73</td><td>4.80</td><td>1.60</td><td>1.29</td><td>0.36</td></tr><tr><td>μ = 6</td><td>11.07</td><td>9.39</td><td>0.99</td><td>0.74</td><td>0.19</td><td>0.13</td><td>0.024</td></tr><tr><td>μ = 7</td><td>3.29</td><td>2.49</td><td>0.15</td><td>0.097</td><td>0.019</td><td>0.012</td><td>0.0014</td></tr><tr><td>μ = 8</td><td>0.88</td><td>0.57</td><td>0.020</td><td>0.011</td><td>0.0017</td><td>0.0008</td><td>0.000071</td></tr><tr><td>μ > 0</td><td>1 262.2</td><td>1 277.0</td><td>1 710.1</td><td>1 725.8</td><td>1 920.4</td><td>1 934.1</td><td>2 045.1</td></tr></tbody></table>

Expected number of distances of multiplicity $\mu$ for various gathering parameters

<figure><img src="image_36.png" /></figure>
IV.2 Bogus Positions
Input: $s \in \mathbb{F}_2^r, H \in \mathbb{F}_2^{r \times n}$

$\tilde{e} \leftarrow 0^n; \tilde{s} \leftarrow s$

**while** $\tilde{s} \neq 0$ **do**

$T \leftarrow \text{THRESHOLD}(\text{context})$

**for** $j = 0, \dots, n-1$ **do**

$\sigma_j \leftarrow \text{ctr}(H, \tilde{s}, j)$

**for** $j = 0, \dots, n-1$ **do**

**if** $\sigma_j \ge T$ **then**

$\tilde{e}_j \leftarrow \tilde{e}_j \oplus 1$

$\tilde{s} \leftarrow \tilde{s} - \text{col}(H, j)$

**return** $\tilde{e}$

$\text{ctr}(H, \tilde{s}, j)$ number of unsatisfied equations involving position $j$

a.k.a. **counter** of $j$

<figure><img src="image_37.png" /></figure>
Binomial model* for the counter value:

$$ \begin{cases} \text{correct position: } \sigma_j \sim \text{Bin}(d, \pi_0) \\ \text{error position: } \sigma_j \sim \text{Bin}(d, \pi_1) \end{cases} $$

Typically $d = 71$, $\pi_0 \approx 0.4$ and $\pi_1 \approx 0.6$, with an exact value depending on the parameters and on the syndrome weight $S$.

For given parameters $(r, d, t)$, the optimal threshold ([Chaulet 2017]) is well approximated by an affine function

$$ \text{e.g. } (r, d, t) = (12323, 71, 134) \rightarrow T = f_t(S) = 0.006258 \cdot S + 11.094. $$

$$ *\sigma \sim \text{Bin}(d, \pi) \Leftrightarrow \text{Pr}(\sigma = i) = \binom{d}{i} \pi^i (1 - \pi)^{d-i} $$

<figure><img src="image_38.png" /></figure>
BIKE Bit-Flipping Decoding

Input: $s \in \mathbb{F}_2^r, H \in \mathbb{F}_2^{r \times n}$

$$ \tilde{e} \leftarrow 0^n ; \tilde{s} \leftarrow s $$

**for** $i = 1, \dots, NbIter$ **do**

$$ T \leftarrow f_t(|\tilde{s}|) + \delta $$

**for** $j = 0, \dots, n-1$ **do**

$$ \sigma_j \leftarrow \text{ctr}(H, \tilde{s}, j) $$

**for** $j = 0, \dots, n-1$ **do**

**if** $\sigma_j \ge T$ **then**

$$ \tilde{e}_j \leftarrow \tilde{e}_j \oplus 1 $$

$$ \tilde{s} \leftarrow \tilde{s} - \text{col}(H, j) $$

**return** $\tilde{e}$

▷ NbIter = 7 for security level 1

▷ $\delta = 3$, $t$ is the initial error weight

The real BIKE decoder is more complex and features so-called black and gray steps which do not essentially change what is coming next

<figure><img src="image_39.png" /></figure>
m-gathering Bogus Positions

In-depth monitoring of *m*-gathering decoding failure instances reveals the
following fact:

When the decoding fails, we observe at the second (sometimes
the third) iteration that two things happen concomitantly

* a few correct positions (a dozen or so) have an extremely high counter value*, the *bogus positions*;

* the syndrome weight, and thus the threshold, is much lower
than expected (given the remaining error weight at that point).

The bogus positions are thus flipped, become errors and irrepara-
bly spoil the decoding process.

Presumably, bogus positions are related to the existence of high multi-
plicity distances in the key spectrum

<figure><img src="image_40.png" /></figure>

<footnote>*near to impossible in the binomial model for counters</footnote>
IV. New BIKE Decoder
For BIKE parameter $(r, d, t)$

Input: $s \in \mathbb{F}_2^r, H \in \mathbb{F}_2^{r \times n}$

$\tilde{e} \leftarrow 0^n ; \tilde{s} \leftarrow s$

**for** $i = 1, \dots, \text{NbIter}$ **do**

$T \leftarrow \text{max}(T_i + \delta, f_t(|\tilde{s}|))$

**for** $j = 0, \dots, n-1$ **do**

$\sigma_j \leftarrow \text{ctr}(H, \tilde{s}, j)$

**for** $j = 0, \dots, n-1$ **do**

**if** $\sigma_j \ge T$ **then**

$\tilde{e}_j \leftarrow \tilde{e}_j \oplus 1$

$\tilde{s} \leftarrow \tilde{s} - \text{col}(H, j)$

**return** $\tilde{e}$

$T_1 = f_t(|s|)$

$T_4 = (d+1)/2$

$T_2 = (2T_1 + T_4)/3$

$T_3 = (T_1 + 2T_4)/3$

$T_i = T_4, i > 4$

$f_t(x) = 0.006258 \cdot x + 11.094, \delta = 3, \text{NbIter} = 7$ (security level 1)

<figure><img src="image_41.png" /></figure>
New Decoder DFR – Waterfall

<table><thead><tr><th>r</th><th>10 620</th><th>10 650</th><th>10 680</th><th>10 700</th></tr></thead><tbody><tr><th>#samples</th><td>4.4 · 10<sup>9</sup></td><td>13.3 · 10<sup>9</sup></td><td>56.2 · 10<sup>9</sup></td><td>38.2 · 10<sup>9</sup></td></tr><tr><th>#failures</th><td>16 222</td><td>7 756</td><td>3 183</td><td>870</td></tr><tr><th>log<sub>2</sub>(DFR)</th><td>-18.04</td><td>-20.71</td><td>-23.46</td><td>-25.39</td></tr></tbody></table>

“Waterfall DFR extrapolation”:

* Level 1, $(r, d, t) = (12\,323,\,71,\,134)$, $\delta = 3$, $NbIter = 7 \rightarrow 2^{-181}$

* Level 3, $(r, d, t) = (24\,659,\,103,\,199)$, $\delta = 5$, $NbIter = 7 \rightarrow 2^{-266}$

* Level 5, $(r, d, t) = (40\,973,\,137,\,264)$, $\delta = 6$, $NbIter = 7 \rightarrow 2^{-343}$

<figure><img src="image_42.png" /></figure>
New Decoder DFR – m-gathering Simulation (1/4)

<table><thead><tr><th>(m, ε)</th><th>(1600, 0)</th><th>(1700, 0)</th><th>(1800, 0)</th><th>(1900, 0)</th><th>(2000, 0)</th><th>(2100, 0)</th></tr></thead><tbody><tr><th>#samples</th><td>9.5 · 10<sup>9</sup></td><td>9.6 · 10<sup>9</sup></td><td>9.6 · 10<sup>9</sup></td><td>9.6 · 10<sup>9</sup></td><td>15.7 · 10<sup>9</sup></td><td>9.4 · 10<sup>9</sup></td></tr><tr><th>#failures</th><td>79913</td><td>32596</td><td>13153</td><td>5293</td><td>3383</td><td>763</td></tr><tr><th>log<sub>2</sub>(DFR)</th><td>-16.86</td><td>-18.16</td><td>-19.48</td><td>-20.79</td><td>-22.15</td><td>-23.56</td></tr><tr><th>log<sub>2</sub>(density)</th><td>-188.41</td><td>-182.15</td><td>-176.26</td><td>-170.69</td><td>-165.41</td><td>-160.40</td></tr><tr><th>sum</th><td>-205.27</td><td>-200.31</td><td>-195.74</td><td>-191.48</td><td>-187.56</td><td>-183.96</td></tr></tbody></table>

<table><thead><tr><th>(m, ε)</th><th>(2200, 0)</th><th>(2300, 0)</th><th>(2400, 0)</th><th>(2500, 0)</th><th>(2600, 0)</th><th>(2700, 0)</th></tr></thead><tbody><tr><th>#samples</th><td>9.4 · 10<sup>9</sup></td><td>15.8 · 10<sup>9</sup></td><td>19.1 · 10<sup>9</sup></td><td>25.5 · 10<sup>9</sup></td><td>59.8 · 10<sup>9</sup></td><td>7.9 · 10<sup>9</sup></td></tr><tr><th>#failures</th><td>270</td><td>177</td><td>81</td><td>40</td><td>31</td><td>0</td></tr><tr><th>log<sub>2</sub>(DFR)</th><td>-25.06</td><td>-26.41</td><td>-27.81</td><td>-29.25</td><td>-30.84</td><td>-</td></tr><tr><th>log<sub>2</sub>(density)</th><td>-155.62</td><td>-151.06</td><td>-146.70</td><td>-142.51</td><td>-138.50</td><td>-134.63</td></tr><tr><th>sum</th><td>-180.68</td><td>-177.47</td><td>-174.51</td><td>-171.76</td><td>-169.34</td><td>-</td></tr></tbody></table>

<figure><img src="image_43.png" /></figure>
New Decoder DFR – *m*-gathering Simulation (2/4)

<table><thead><tr><th>(m, ε)</th><th>(1600, 1)</th><th>(1700, 1)</th><th>(1800, 1)</th><th>(1900, 1)</th><th>(2000, 1)</th></tr></thead><tbody><tr><th>#samples</th><td>9.3 · 10<sup>9</sup></td><td>9.3 · 10<sup>9</sup></td><td>9.3 · 10<sup>9</sup></td><td>9.3 · 10<sup>9</sup></td><td>13.6 · 10<sup>9</sup></td></tr><tr><th>#failures</th><td>17916</td><td>6904</td><td>2524</td><td>921</td><td>482</td></tr><tr><th>log<sub>2</sub>(DFR)</th><td>-18.98</td><td>-20.36</td><td>-21.82</td><td>-23.27</td><td>-24.75</td></tr><tr><th>log<sub>2</sub>(density)</th><td>-179.47</td><td>-173.31</td><td>-167.52</td><td>-162.05</td><td>-156.86</td></tr><tr><th>sum</th><td>-198.45</td><td>-193.67</td><td>-189.34</td><td>-185.31</td><td>-181.61</td></tr></tbody></table>

<table><thead><tr><th>(m, ε)</th><th>(2100, 1)</th><th>(2200, 1)</th><th>(2300, 1)</th><th>(2400, 1)</th><th>(2500, 1)</th></tr></thead><tbody><tr><th>#samples</th><td>10.1 · 10<sup>9</sup></td><td>20.1 · 10<sup>9</sup></td><td>25.2 · 10<sup>9</sup></td><td>25.3 · 10<sup>9</sup></td><td>59.9 · 10<sup>9</sup></td></tr><tr><th>#failures</th><td>132</td><td>94</td><td>47</td><td>16</td><td>12</td></tr><tr><th>log<sub>2</sub>(DFR)</th><td>-26.19</td><td>-27.68</td><td>-29.00</td><td>-30.56</td><td>-32.22</td></tr><tr><th>log<sub>2</sub>(density)</th><td>-151.93</td><td>-147.24</td><td>-142.76</td><td>-138.47</td><td>-134.36</td></tr><tr><th>sum</th><td>-178.12</td><td>-174.91</td><td>-171.76</td><td>-169.03</td><td>-166.58</td></tr></tbody></table>

<figure><img src="image_44.png" /></figure>
New Decoder DFR – *m*-gathering Simulation (3/4)

<figure><img src="image_45.png" /></figure>

Old decoder: DFR = $2^{-29.33}$ for $(m, \epsilon) = (4000, 1)$, density $2^{-87.28}$

<figure><img src="image_46.png" /></figure>
New Decoder DFR – *m*-gathering Simulation (4/4)

<figure><img src="image_47.png" /></figure>

Old decoder: for $(m, \epsilon) = (2500, 1)$, DFR · density = $2^{-145.8}$

<figure><img src="image_48.png" /></figure>
New Decoder – Features

* Larger thresholds

* Similar algorithmic cost

* Simpler logic, and hopefully simpler analysis

* Decoding failure rate:
  - Same behavior in the waterfall region: fast exponential decrease

- Better behavior against weak keys

<figure><img src="image_49.png" /></figure>
# V. Weak Keys & Error Floors

## Perspectives and Open Questions
Weak Keys and the New Decoder

* weak keys have abnormally high multiplicities*

* higher multiplicities trigger more decoding failures

* bogus positions occur with weak keys and trigger decoding failures

* bogus positions are handled by increasing the thresholds

* higher thresholds reduce the weak key DFR by orders of magnitude

<figure><img src="image_50.png" /></figure>

<footnote>*multiplicities of values in the coordinate distance spectrum of the secret key</footnote>
Error Floor Estimates

* distance to the closest *near-codeword*\* is the dominant factor for the error floor estimation

* multiplicities are meaningful to estimate error floors
relates to Tanner graphs and *near-codewords* (a.k.a. trapping sets)

* new models for *counters*†, straying from the typical case as the error pattern gets closer to a *near-codeword*

Work in progress, Markovian model taking into account near-codewords:

[Arpin, Billingsley, Lau, Perlner, Robinson, Tillich, Vasseur]

<figure><img src="image_51.png" /></figure>

<footnote>\*a small set (of linear cardinality) of low weight words with low weight syndromes
†number of unsatisfied parity equations involving a position</footnote>
$e \in \mathbb{F}_2^n$ the error pattern (Hamming weight $t$ at start)

$x \in \mathbb{F}_2^n$ the closest near-codeword (Hamming weight $d = w/2$)

$u$ the number of error positions in $x$ ($u = |e \star x| \ge 1$)

For a position in the support of $x$: *

$$ \begin{cases} \text{correct position: } \sigma_j \sim \text{Bin}(d-u, \pi_0) + \text{Bin}(u, \pi_1) \\ \text{error position: } \sigma_j \sim \text{Bin}(d-u+1, \pi_1) + \text{Bin}(u-1, \pi_0) \end{cases} $$

For other positions:

$$ \begin{cases} \text{correct position: } \sigma_j \sim \text{Bin}(d, \pi_0) \\ \text{error position: } \sigma_j \sim \text{Bin}(d, \pi_1) \end{cases} $$

Recall that typically $d = 71$, $\pi_0 \approx 0.4$, $\pi_1 \approx 0.6$

counter = number of unsatisfied parity equations

<figure><img src="image_52.png" /></figure>

<footnote>*[Arpin, Billingsley, Lau, Perlner, Robinson]</footnote>
Markovian Model Matching the Error Floor (Perfect Keys)

<figure><img src="image_53.png" /></figure>

[Tillich, Vasseur, 2024] model matches simulation for a toy example

<figure><img src="image_54.png" /></figure>
Markovian Models (for Sequential Bit-Flipping)

<figure><img src="image_55.png" /></figure>

[Sendrier, Vasseur, 2019] state : (|e|, |s|)

[*, ongoing] state : (|e|, |s|, u)

* [Arpin, Billingsley, Lau, Perlner, Robinson, Tillich, Vasseur]

<figure><img src="image_56.png" /></figure>
* Some correct positions may have higher counter values (and some erroneous positions may have lower counter values)
  *consistent with bogus positions*

* Near-codewords exist for all keys, their impact on error floors (and thus on decoding failures) depends on multiplicities
  *consistent with a higher DFR for weak keys*

Open Questions:

* Do all weak keys have untypical multiplicities? Converse?

* Are weak keys dominant for the average DFR/Error Floor?

<figure><img src="image_57.png" /></figure>
Conclusion
# Conclusions – BIKE DFR

Summing up ($\lambda$ the security parameter, e.g. $\lambda = 128$):

* Waterfall

DFR decreases exponentially in $O(\lambda^2)$ (block size)

* Error Floor (preliminary, work in progress)

The new Markovian model predicts the error floor

DFR seems to decrease exponentially in $O(\lambda)$ (error weight)

Perspectives to reduce the DFR

- improve the threshold schedule (with guarantees from the model)

- filter out keys with untypical spectrum (weak keys)

- increase the parameters

<figure><img src="image_58.png" /></figure>