# Error floor prediction with Markov models for QC-MDPC codes

Sarah Arpin, Jun Bo Lau, Antoine Mesnard, Ray Perlner, Angela Robinson,
Jean-Pierre Tillich, Valentin Vasseur

► To cite this version:

Sarah Arpin, Jun Bo Lau, Antoine Mesnard, Ray Perlner, Angela Robinson, et al. Error floor prediction with Markov models for QC-MDPC codes. CRYPTO 2025 - 45th Annual International Cryptology Conference, Aug 2025, Santa Barbara, United States. pp.221-252, 10.1007/978-3-032-01855-7_8. hal-05461501

HAL Id: hal-05461501

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

Submitted on 16 Jan 2026

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.

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Error floor prediction with Markov models for
QC-MDPC codes

Sarah Arpin¹, Jun Bo Lau², Antoine Mesnard³, Ray Perlner⁴, Angela Robinson⁴, Jean-Pierre Tillich³, and Valentin Vasseur⁵

¹ Virginia Polytechnic Institute and State University, Department of Mathematics

² KU Leuven, COSIC, Belgium

³ INRIA

⁴ National Institute of Standards and Technology, Computer Security Division

⁵ Thales, Gennevilliers, France

**Abstract.** Quasi-cyclic moderate-density parity check (QC-MDPC) code-
based encryption schemes under iterative decoders offer highly-competitive
performance in quantum-resistant cryptography, but their IND-CCA2 se-
curity is an open question because the decoding failure rate (DFR) of
these algorithms is not well-understood. The DFR decreases extremely
rapidly as the blocklength increases, then decreases much more slowly
in regimes known as the waterfall and error floor, respectively. The wa-
terfall behavior is rather well predicted by a Markov model introduced
by Sendrier and Vasseur [SV19b] but it does not capture the error floor
behavior. Assessing precisely for which blocklength this error floor begins
is crucial for the low DFRs sought in the context of cryptography.
By enriching the Markov model [SV19b] with information about near
codewords we are able to capture this error-floor behavior for a step-by-
step decoder. This decoder displays worse decoding performance than the
parallel decoders used in practice but is more amenable to a Markov chain
analysis. We already capture the error floor with a simplified model. A
refined model taking into account certain structural features of the secret
key is even able to give accurate key dependent predictions both in the
waterfall and error floor regimes. We show that error floor behavior is
governed by convergence to a near codeword when decoding fails.
We ran this model for the BIKE cryptosystem with this simpler step-
by-step decoder to better ascertain whether the DFR is low enough to
achieve IND-CCA2 security. Our model gives a DFR below $2^{-131.2}$, using
a block length $r = 13477$ instead of the BIKE parameter $r = 12323$. This
paper gives some strong evidence that the IND-CCA2 requirement can
be met at the cost of a modest increase of less than 10% in the key size.

# 1 Introduction

## 1.1 Motivation

**The NIST PQC standardization process.** The U.S. National Institute of
Standards and Technology (NIST) Post-Quantum Cryptography (PQC) stan-
dardization process, which began with 82 submissions, has selected two key en-
capsulation algorithms for standardization: CRYSTALS-Kyber and HQC. The
BIKE cryptosystem was a candidate considered in round 4, a cryptosystem based on quasi-cyclic moderate-density parity check (QC-MDPC) codes which are decoded by an iterative Black-Grey-Flip (BGF) decoder [ABB+21,DGK20]. The BIKE cryptosystem offers competitive performance but lacks a formal security claim in the static-key setting.

**Estimating the DFR of BIKE.** Cryptosystems with a non-zero probability of decryption failures require careful analysis when proving IND-CCA2 security. In particular, the standard security proof [HHK17] requires the average failure probability to be below $2^{-\lambda}$ where $\lambda$ is the security parameter. BIKE is one such cryptosystem. A low DFR for BIKE is not just a theoretical concern, since a DFR sufficiently higher than $2^{-\lambda}$ enables the GJS key-recovery attack [GJS16], which exploits decoding failures in an IND-CCA security model.

The target DFR of $2^{-\lambda}$ is too small to measure directly, so another approach is needed to prove that the DFR of BIKE is below $2^{-\lambda}$. Previous work [SV19b,SV19a,DGK20] approximates the DFR by (i) directly measuring the average DFR for smaller code sizes by running the decoder (which is doable since the DFR is high enough to observe decoding failures) then (ii) extrapolating the behavior to estimate the DFR for larger parameters that are out of reach of experiments. However, the DFR falls into two regimes, making such extrapolations unreliable. The first regime is the *waterfall region*, where the DFR decays more than exponentially in the block size *n* of the scheme (with other parameters fixed). The second regime is the *error floor* which kicks in when the block size is sufficiently large and where the decay is much slower (Fig. 1). The issue is that the experiments are done in the waterfall region and extrapolation is made under the hypothesis that for the BIKE parameters we are still in this region. This could lead to underestimation of the DFR and consequently, an underestimation of the block size needed to achieve a particular security parameter $\lambda$.

It remains an open problem to predict for which value of *n* the error floor begins for BIKE. It is really a problem of predicting the iterative decoding performance of a QC-MDPC code. For LDPC codes (which have rows and columns of weight $O(1)$ compared to $O(\sqrt{n})$ for MDPC codes), with the same kind of decoder, the error floor phenomenon is better understood. For LDPC codes, the error floor is either due to the existence of low-weight codewords which would fool any decoder, or of small *near codewords*. They are also called trapping sets and are errors of small weight with a syndrome also of small weight [Ric03,HB18,VCN14].

Error vectors which have a large enough intersection with those codewords or near codewords are known to cause the error floor behavior in LDPC codes.

<figure><img src="image_2.png" /><figcaption>Fig. 1: Waterfall and error floor regions for decoding failure rate.</figcaption></figure>
On the other hand, MDPC codes typically have no low-weight codewords or near codewords. However, BIKE is based on QC-MDPC codes, and this gives BIKE more structure than a random MDPC code. BIKE admits a parity-check matrix $H$ formed by two circulant blocks. Such codes have codewords of weight equal to the row weight $w$ of $H$ (which is of order $O(\sqrt{n})$) [SV19a,BBC$^{+}$21]. There are near codewords of half the row weight which, due to the block-circulant structure, is also equal to the column weight $d$ of $H$. In particular, the set of near codewords consists of error vectors where either the first or second half of bits is precisely a row of $H$ and the rest of the bits are 0 [Vas21]. The lower bound$^6$ on the DFR based on those moderate-weight codewords is too low to be of concern for the BIKE parameters [BBC$^{+}$21].

However, a clear explanation of the error floor for QC-MDPC has not been found to date even if the near codewords of [Vas21] could be a factor: the DFR conditioned on an error vector with large intersection with one of the near codewords was shown in [Vas21] to be non-negligible. Even if the contribution to the DFR of such events is bigger than the contribution to the DFR coming from the moderate-weight codewords, it is not enough to be of concern for BIKE parameters. Moreover [ABH$^{+}$22] shows that for scaled-down BIKE parameters where the error floor can be observed experimentally, the errors that contribute to the DFR do not have large intersection with the near codewords of [Vas21].

Remarkably, the waterfall region is much better understood [SV19b,Vas21] by analyzing with a Markov chain approach a step-by-step decoder flipping bits one at a time. At each step a random position is considered and flipped according to whether the number of unsatisfied parity-checks involving this position (called the *counter* of the position) is greater than some threshold. To understand the rationale of this rule, denote by $\pi_0$ the probability that a parity-check involving an error free bit is not satisfied and denote by $\pi_1$ the probability that a parity-check involving a bit in error is not satisfied. The crucial observation is that

$$ \pi_0 < \pi_1. \qquad (1) $$

Due to the regular structure of $H$ all bits are involved in the same number $d$ of parity checks. We therefore expect that the *counter* of an error free position behaves as a binomial random variable $Bin(d, \pi_0)^7$, whereas the *counter* of a position in error behaves as $Bin(d, \pi_1)$. Therefore a bit in error tends to be involved in more unsatisfied parity checks than a correct bit. In standard iterative decoding, all positions are considered at once and flipped or not according to the same rule. The fact that the decoder is step-by-step makes it much more amenable to a Markov-chain modeling whose states are the pairs $(s, t)$, $t$ being the number of errors and $s$ the syndrome weight of the error. This Markov-chain model closely predicts the DFR in the waterfall region but does not capture the error floor region. Roughly speaking, the DFR is predicted here by computing the resulting probability distributions of the pairs $(s, t)$. The predicted DFR is the probability to attain a state where $t$ is not zero at the end.

<footnote>$^6$ It is the probability that the error covers at least half one of those codewords.</footnote>

<footnote>$^7$ $Bin(n, p)$ is the sum of $n$ i.i.d. Bernoulli variables $X_i$ of parameter $p$, that is $P(X_i = 1) = p$ for all $i$ in $\{1, \dots, n\}$.</footnote>
## 1.2 Our approach

**Intuition: convergence to near codewords in the error floor regime.**

Our work started with a fundamental observation, namely that in the toy examples for which we could observe the error floor phenomenon experimentally, the remaining error at the end of the iterative decoding process when decoding failed covered in many cases one of the near codewords put forward in [Vas21]. Interestingly enough, [ABH$^{+}$22, Fig 3,4 and 5] shows that in the error floor regime, errors which result in a decoding failure tend to have a bigger intersection with at least one of those near codewords than a random error of the same size. There is a good justification for this behavior in §2.4.

[BBC$^{+}$21] noted that there exist bad counters which can lead to decoding failures. We provide a full classification of such bad counters. The point is that we actually do not have two kinds of behaviors for the counters as explained before, but rather four different behaviors of the counters. At each decoding iteration, consider the near codeword $\nu$ that is the closest to the actual error and denote by $u$ the size of its intersection with the actual error $e$. As explained in §2.4, we expect the following four kinds of behavior:

1. The counters of the $u$ bits belonging to the support of $\nu$ and $e$ behave like the sum of two independent binomial variables $\text{Bin}(u-1, \pi_0) + \text{Bin}(d-u+1, \pi_1)$

2. The counters of the $d-u$ bits not in error but in the support of $\nu$ behave as the sum of two binomial variables $\text{Bin}(u, \pi_1) + \text{Bin}(d-u, \pi_0)$.

3. The counters of the rest of the $t-u$ bits in error behave “as usual” as a binomial variable $\text{Bin}(d, \pi_1)$.

4. The counters of the rest of the $n-d-t+u$ bits that are not in error also behave as expected, namely as a binomial variable $\text{Bin}(d, \pi_0)$.

In other words, since $\pi_0 < \pi_1$, we expect an abnormal behavior from the $d$ bits which belong to the closest near codeword. Indeed, those that are in error are less likely to be corrected by the iterative decoding process than the others which are in error: their counter is somewhat in between a counter of a bit which is in error and a counter of a bit which is not in error. Similarly, the $d-u$ bits of the near codeword that are not in error have a greater chance to be wrongly flipped by the iterative decoding process than the other bits in error. This is even worse, because the more bits are in error in the near codeword, the more the bits involved in this near codeword behave as their opposite: those that are still not in error tend to look even more like bits which are in error. This leads to a snowball effect. As soon as enough bits are in error in the near codeword, there is a non negligible chance to end up at the end of the iterative decoding process with the whole near codeword being in error. Due to the peculiar structure of near codewords, the iterative decoding process gets stuck there.

This discussion suggests that errors which give rise to a decoding failure in the error floor region should be somewhat closer to one of those near codewords at the beginning, and the intersection size only increases during the decoding process. This is why we adapted the Markov model of [SV19b,Vas21] to also keep track of this parameter $u$ which is the biggest intersection of a near codeword with the residual error vector in the decoding process.
**Two new Markov models.** We have followed two different but related approaches for keeping track of the size of the intersection of the error vector with the near codewords in a Markov model.

- The first approach uses the simple model for the counters described before together with a simplified model of the parity-check matrix. This simple model keeps track of the size $u$ of the intersection of the error with a single, randomly selected near codeword $\nu$. We estimate the contribution to the DFR coming from $\nu$. This is then used to account for the contributions coming from all near codewords. See §5.

- The second approach is much more involved. It computes the transition probabilities much more accurately. It takes into account the secret key structure by using the specific structure of the near codewords corresponding to a given key. The only simplifying assumption which is made is that in the error floor regime the decoding failure is dominated by errors which are close to a single near codeword, and that this does not change during the decoding process. In this case, the Markov model keeps track of the size $u$ of the intersection of the error with the closest near codeword. We capture the DFR in the error floor regime with high accuracy within this model. See §6.

**The simple Markov model.** The first approach has been tested with scaled-down BIKE parameters and by taking a random key $\mathcal{H}$. To simplify the computation of $\pi_0$ and $\pi_1$ we made the assumption that the columns of $\mathcal{H}$ are drawn uniformly at random up to fixed column weight $d$. This new Markov model captures the error floor region and provides a much more conservative estimate than the DFR estimate based on the Markov model of [SV19b,Vas21] which is too optimistic in the error floor regime. It turns out that the new DFR estimate is larger than the true estimate in both the waterfall and error floor regions (and not only in the waterfall regime as was the case for the Markov model of [SV19b,Vas21]). This is quite encouraging since even with this simple model there is a tool for choosing the parameters of BIKE in a conservative manner.

**A key dependent Markov model.** One drawback of this simple Markov model is that it does not take into account the structure of the key. There are indeed weak keys [DGK20,Vas21,NSP+23,WWW23] where decoding behaves really badly. Moreover, there is a difference between the DFR of the best and worst key of the DFR in the few thousand of instances of the toy example we considered. This led us to refine the Markov model which allowed us to compute the transition probabilities more accurately.

One of the difficulties of having a Markov model working for all sorts of keys is that the near codewords split into two classes, those that have their support either in the first half of the code positions or in the second half. These two classes might affect the DFR in a very different way. To circumvent this problem, we added a bit to the Markov state, getting a state $(s, t, u, b)$ where $b=0$ indicates that the closest near codeword has all its support in the first half of positions and 1 otherwise. At the expense of increasing the state space size and
adding more involved transition probability formulas, we get a Markov model which captures now all possible keys. Remarkably, in the toy examples this model is still accurate for predicting the error floor for the step-by-step decoder and other variants: the majority decoder (the threshold for flipping being half the total number of equations involving a bit), the BGF decoder, or a decoder with a new custom threshold rule which improves the DFR by a significant amount.

Moreover, we can also use our model to examine what causes the DFR. We split the contribution of the DFR into two parts. The first one is the contribution DFR<sub>e</sub> to the DFR where decoding failed because it ended up covering a near codeword: The final state where we got blocked in the Markov chain was a state (s, t, u, b) for which u = d. It can be viewed in some sense as the error-floor term in the DFR. The second one is the total DFR minus DFR<sub>e</sub>: DFR<sub>w</sub> = DFR - DFR<sub>e</sub>, which can be viewed as the waterfall part of the DFR. Not only did our Markov model accurately predict the DFR, but did also predict well each term separately. Indeed, even in the error floor region where DFR<sub>e</sub> is really bigger than DFR<sub>w</sub>, the DFR<sub>w</sub> term predicted by our model matches the DFR<sub>w</sub> term computed in the experiments. This is a further indication that the model predicts accurately the error floor and the waterfall behaviors. All in all, in this work, we conclude that the dominant contribution to the error floor for QC-MDPC codes under iterative decoders is due to convergence to a near codeword.

1.3 Summary of the main results

The simple Markov model we present here already captures the error floor regime
and gives a conservative estimate of the DFR. On the other hand, the refined
model which is key dependent is used to

- give an extremely close approximation of experimental data in the waterfall
  and error floor regimes, further improving upon the first model and [SV19b],

- estimate for the BIKE 1 parameters and with the previous BIKE 1 decoder using a single threshold function a DFR of about $2^{-91}$,

- show that for this decoding rule, there is an error floor behavior which ap-
  pears already for slightly larger values of the block length than the one which
  was chosen and depending on the gap parameter $\delta$ of the decoder gives a
  contribution to the DFR which is between $2^{-100}$ and $2^{-120}$,

- improve this decoding rule by raising the minimum allowed threshold from 36 to 39 to show that for a slightly larger block length ($r = 13477$ instead of $r = 12323$), we obtain a DFR which is below $2^{-131.2}$ for a typical key.

These models predict and experiments confirm that the dominating cause of
failures in the error floor regime in a wide range of parameters is due to con-
vergence to near codewords. All models use the step-by-step decoder which is
experimentally shown to produce more decoding failures than parallel decoders.
The most impactful model is the refined model which matches the experimental
data, also using a step-by-step decoder, remarkably well throughout both the
error floor and waterfall regimes. This model is applied to the BIKE cryptosys-
tem parameter sets to give a DFR approximation; it is expected that the DFR
for the same parameter sets using a parallel bit-flipping decoder as specified in
[ABB+21] and decoding rule based on iteration dependent threshold functions
would result in a lower DFR than what is approximated by the model.

All in all, this paper solves a major issue for the fourth round candidate BIKE
of the NIST PQC competition, namely to give a convincing prediction for the
DFR of this cryptosystem. Being able to show that this quantity is below $2^{-\lambda}$
is a major concern for BIKE to prove its IND-CCA2 security. This paper gives
some strong evidence that this requirement can be met at the cost of a modest
increase of less than 10% in the key size, by raising a little bit the minimum
threshold, and filtering out atypical keys during key generation.

2 Background

2.1 Notation

**Basic notation.** Vectors and matrices are respectively denoted in bold letters and bold capital letters such as **a** and **A**. Vectors are assumed to be row vectors and **x**$^\top$ denotes the column vector which is the transpose of the row vector **x**. For a matrix **A**, the vector that is the transpose of the j-th column of **A** is denoted by **A**_j. The entry at index i of the vector **x** is denoted by x_i or x(i). The Schur (component-wise) product (x_i y_i)_{1≤i≤n} of two vectors **x** = (x_i)_{1≤i≤n} and **y** = (y_i)_{1≤i≤n} of the same length is denoted by **x**★**y**. The Hamming weight |**x**| of a vector **x** is its number of nonzero entries.

**Probabilistic notation.** Bin(n, p) denotes a random variable following a bino-
mial distribution with parameters n and p, that is the sum Σn i=1 X_i of n i.i.d.
Bernoulli variables with parameter p. Expressions like Bin(n₁, p₁) + Bin(n₂, p₂)
stand for the sum of the two independent binomial random variables Bin(n₁, p₁)
and Bin(n₂, p₂). By abuse of notation, we write X ~ Y when two random vari-
ables X and Y follow the same distribution. For a finite set S, x $\leftarrow$ S means
that x is an element of S sampled uniformly at random in S.

**Binary linear codes.** All codes considered here are binary and linear, which means that they are vector spaces over $\mathbb{F}_2$. A code $\mathcal{C}$ of length $n$ and dimension $k$ is a $k$-dimensional subspace of $\mathbb{F}_2^n$. We say that such a code is an $[n, k]$ code. It is specified by a parity-check matrix which is a matrix whose kernel is $\mathcal{C}$, i.e. $\mathcal{C} = \{c \in \mathbb{F}_2^n : Hc^\top = 0\}$.

**Quasi-cyclic codes and polynomial notation.** On top of being binary and linear, all codes considered here are quasi-cyclic, i.e. their parity-check matrix is formed by blocks of circulant matrices. More precisely, they are double circulant codes, meaning that the parity-check matrix has the form $\mathbf{H} = (\mathbf{C}_0 \ \mathbf{C}_1)$ where both $\mathbf{C}_0$ and $\mathbf{C}_1$ are circulant matrices. From now on, $r$ will denote the size of $\mathbf{C}_0$ and $\mathbf{C}_1$ and the length $n$ of the code will be $n = 2r$. $\mathbf{C}_0$ and $\mathbf{C}_1$ are also supposed to have the same column weight. This weight is denoted by $d$. The row
weight $w$ of $\mathbf{H}$ is also constant and satisfies $w = 2d$. Such codes are conveniently represented by polynomials since $r \times r$ binary circulant matrices form a ring $\mathcal{R}$ isomorphic to $\mathbb{F}_2[x]/(x^r - 1)$, the isomorphism $\Psi$ being given by

$$ \left( \begin{array}{ccccc} c_0 & c_{r-1} & \cdots & c_2 & c_1 \\ c_1 & c_0 & c_{r-1} & c_2 & \\ \vdots & c_1 & c_0 & \ddots & \vdots \\ c_{r-2} & \vdots & \ddots & \ddots & c_{r-1} \\ c_{r-1} & c_{r-2} & \cdots & c_1 & c_0 \end{array} \right) \mapsto c_0 + c_1 x + \cdots + c_{r-1} x^{r-1}. $$

We use this isomorphism to view $\mathbf{H} = (C_0 C_1)$ as the pair $(h_0(x), h_1(x))$ where $h_0(x) = \Psi(C_0)$ and $h_1(x) = \Psi(C_1)$. We overload the notation from now on:

**Notation 1.** We denote the parity-check matrix $\mathbf{H} \stackrel{\text{def}}{=} (h_0, h_1)$. We also write $h_0(x) = \sum_{j=1}^d x^{l_j}$ and $h_1(x) = \sum_{j=1}^d x^{r_j}$, where $l_j$ and $r_j$ run over the nonzero coefficients of $h_0$ and $h_1$, respectively.

We likewise represent error vectors $\mathbf{e} = (e_0, \cdots, e_{n-1}) \in \mathbb{F}_2^n$ with polynomials

$$ \mathbf{e} \rightsquigarrow \mathbf{e}(x) = e_0(x) \oplus e_1(x) = \sum_{j=0}^{r-1} e_j x^j \oplus \sum_{j=0}^{r-1} e_{r+j} x^j \in (\mathbb{F}_2[x]/(x^r - 1))^2 $$

We use here “$\oplus$” to denote a formal sum, and “$+$” to denote addition in the ring $\mathbb{F}_2[x]/(x^r - 1)$. The syndrome $\mathbf{s} = (s_0, \cdots, s_{r-1})$ of an error $\mathbf{e} = (e_0, \cdots, e_{n-1})$, i.e. $\mathbf{s}^\mathrm{T} = \mathbf{H}\mathbf{e}^\mathrm{T}$ is also represented as a polynomial $\mathbf{s}(x) = \sum_{j=0}^{r-1} s_j x^j$ and

$$ s(x) = e_0(x)h_0(x) + e_1(x)h_1(x). \qquad (2) $$

Note that all polynomial operations are performed in the ring $\mathbb{F}_2[x]/(x^r - 1)$.

## 2.2 Iterative Decoders

The problem we will be interested to solve efficiently during the deciphering process is the syndrome decoding problem.

**Problem 2.1 (syndrome decoding problem (SDP)).** Given an $r \times n$ parity-check matrix $\mathbf{H} \in \mathbb{F}_2^{r \times n}$ and an error vector $\mathbf{e}$ sampled uniformly at random of weight $t$ with syndrome $\mathbf{s}^\mathrm{T} = \mathbf{H}\mathbf{e}^\mathrm{T}$, find a vector $\mathbf{e}'$ such that $\mathbf{H}\mathbf{e}'^\mathrm{T} = \mathbf{s}^\mathrm{T}$ and $|\mathbf{e}'| = t$.

Iterative, bit-flipping syndrome decoders generally solve the SDP by guessing that columns of $\mathbf{H}$ with many bits in common with $\mathbf{s}$ are likely affected by errors. Recall that $\mathbf{H}_i$ denotes the transpose of the $i$-th column of matrix $\mathbf{H}$, and define $\sigma_i(\mathbf{H}, \mathbf{s}) = |\mathbf{H}_i \star \mathbf{s}|$, the number of unsatisfied parity-check equations involving $i$. We will denote this quantity simply by $\sigma_i$ in what follows and say that it is the *counter* corresponding to bit $i$. The bit-flipping decoders initialize $\mathbf{e}' = \mathbf{0}$, compute $\sigma_j$ for all or some $j \in \{0, \dots, n-1\}$, then flip the $j$-th bit
$e'_j$ whenever $\sigma_j \ge T$, where $T$ is a given threshold function. We say a decoding failure has occurred whenever the output $e'$ satisfies: $He'^T \ne s^T$ or $e' \ne e$.

The accuracy of bit-flipping decoders greatly depends on $T$. If the threshold is too high, the decoder ceases to flip bits before arriving at the correct vector $e'$. If the threshold is too low, more bits are flipped than should be, again resulting in an incorrect vector $e'$. $T$ is always chosen such that $T \ge \frac{d+1}{2}$. This ensures that the weight of $\Delta s^T \stackrel{\text{def}}{=} s^T + He'^T$ is strictly decreasing, so that we may expect it to reach 0 so that $He'^T = s^T$ at the end.

It is most common for iterative decoders to consider each column of $\mathbf{H}$ in comparison with $\mathbf{s}$ during each round of decoding. This can result in multiple bits of the guess $e'$ being flipped in one round of decoding. The BIKE cryptosystem round 4 specification uses the Black-Grey-Flip (BGF) iterative decoder [DGK20]. A closed form analysis of the DFR of the BGF decoder remains an open problem.

In this work we analyze the step-by-step decoder - an iterative decoder which randomly selects one column of $\mathbf{H}$ for comparison with $\mathbf{s}$ during each decoding round: At most one bit is flipped per round. This simplifies the computation of the Markov chain transition probabilities by restricting the number of possible states in the next step. It is detailed in Algorithm 1.

<caption>**Algorithm 1** step-by-step decoder.</caption>

**Input:** $\mathbf{H} \in \mathbb{F}_2^{r \times n}$, $\mathbf{s} \in \mathbb{F}_2^r$, $t \in \{1, \dots, n\}$
**Output:** $\mathbf{e} \in \mathbb{F}_2^r$ such that $\mathbf{He}^T = \mathbf{s}^T$ and $|\mathbf{e}| = t$ or $\perp$ (decoding failure)
**Require:** a threshold function $T$ such that $T \ge \frac{d+1}{2}$
**Ensure:** the weight of $\Delta \mathbf{s}^T = \mathbf{s}^T + \mathbf{He}'^T$ decreases strictly in the algorithm below
    $\mathbf{e}' \leftarrow 0$, $\Delta \mathbf{s} \leftarrow \mathbf{s}$
    **while** $\Delta \mathbf{s} \ne 0$ **do**
        $\mathcal{E} \leftarrow \{\{0, \dots, n-1\} : |\mathbf{H}_j \star \Delta \mathbf{s}| \ge T\}$
        $\triangleright |\mathbf{H}_j \star \Delta \mathbf{s}|$ is the counter $\sigma_j$
        **if** $\mathcal{E} \ne \emptyset$ **then**
            $j \leftarrow \mathcal{E}$
            $e'_j \leftarrow 1 - e'_j$, $\Delta \mathbf{s} \leftarrow \Delta \mathbf{s} + \mathbf{H}_j$
            $\triangleright |\Delta \mathbf{s}|$ has decreased by $d - 2\sigma_j$
        **else** **return** ($\perp$)
        **if** $|e'| = t$ **then** **return** ($e'$)
        **else** **return** ($\perp$)

The step-by-step decoder has been studied in detail and experimental evidence [Vas21, Chap 7, Fig. 7.1] shows that for the classical bit flipping strategy, the step-by-step decoder performs significantly worse than the parallel version.

## 2.3 Near codewords

Near codewords were introduced in the literature of iterative decoding as a way to formalize a collection of error vectors with lower-weight, nonzero syndrome than expected, which are therefore difficult to decode.
**Definition 2.2 (near codeword of type (s,t)).** An error vector $e \in \mathbb{F}_2^n$ is a near codeword of type (s,t) if $|e| = t$ and $|He^T| = s$.

MDPC codes are known to have minimum distance which is typically linear in the code-length $n$ and are unlikely to have small near codewords. This is not the case for QC-MDPC codes: the minimum distance is of order $O(\sqrt{n})$. This is because $h_1(x) \oplus h_0(x)$ belongs to the code of parity-check matrix $H = (h_0, h_1)$. This leads one to suspect that such codes also have small-weight near codewords. This is indeed the case and that this is most likely the main issue for decoding as identified in [Vas21]. To define them, fix a parity-check matrix $H = (h_0, h_1)$.

**Definition 2.3 (The set $\mathcal{N}$ of near codewords).** The set $\mathcal{N}$ of near codewords is the union of all $n$-bit vectors with polynomial representations of the form $x^i h_0(x) \oplus 0$ and $0 \oplus x^i h_1(x)$, for all $i \in \{0, ..., r-1\}$.

In this work, when we refer to a near codeword, we mean an element of $\mathcal{N}$.

**Unusually low syndrome weight.** Elements of $\mathcal{N}$ are $(d, d)$-near codewords as per Def. 2.2: they are of weight $d$ and have syndrome weight $d$. Moreover, even errors $e$ which have an overlap of size $u$ with a near codeword $\nu$ of this kind (meaning that $|e \star \nu| = u$) have an unusually low weight syndrome. If $|e| = t$, the syndrome weight can be as large as $d \cdot t$ and is always $\le d \cdot t - u(u-1)$.

This can be read off directly from the polynomial representation of the syndrome. To verify the first claim, the near codeword $e(x) = x^i h_0(x) \oplus 0 \in \mathcal{N}$, for example, has syndrome $s(x) = (x^i h_0(x)) h_0(x) = x^i h_0^2(x)$, which is of weight $d$ as $h_0(x)$ has precisely $d$ nonzero coefficients, and in $\mathbb{F}_2[x]/(x^r-1)$ squaring and multiplication by $x$ preserve the number of nonzero coefficients. To verify the second claim suppose that the near codeword $\nu$ is say of the form $x^i h_0(x) \oplus 0$, the error $e$ can be written as a polynomial as $e(x) = e_0(x) \oplus e_1(x)$, $x^i h_0(x) = a(x) + b(x)$ and $e_0(x) = a(x) + c(x)$ where $a(x)$ is the polynomial for the common part $e \star \nu$. The syndrome of $e$ is

$$ 
\begin{aligned}
s(x) &= e_0(x)h_0(x) + e_1(x)h_1(x) \\
&= x^{r-i}(a(x) + b(x))(a(x) + c(x)) + e_1(x)h_1(x) \\
&= x^{r-i}(a(x)^2 + a(x)b(x) + a(x)c(x) + b(x)c(x)) + e_1(x)h_1(x).
\end{aligned}
$$

Recall here that we perform the polynomial computation over $\mathbb{F}_2[x]/(x^r-1)$ and that $x^{r-i}x^i = 1$ in this ring. Let us denote by $|P|$ the weight of a polynomial $P$, namely the number of its non-zero coefficients. The weight satisfies $|P \cdot Q| \le |P| \cdot |Q|$ and $|P+Q| \le |P| + |Q|$ for all polynomials $P$ and $Q$. Notice that $d \cdot t$ is exactly $|e_0| \cdot |h_0| + |e_1| \cdot |h_1| = |a|^2 + |a| \cdot |b| + |a| \cdot |c| + |b| \cdot |c| + |e_1| \cdot |h_1|$. The point is that $|a^2| = |a|$ because of the forced cancellations in the product $a(x)^2$. Indeed, as in the previous point, squaring preserves the number of nonzero coefficients. This implies that we have at least a drop of $|a|^2 - |a| = u(u-1)$ in the syndrome weight as claimed above.
## 2.4 Tanner graphs

We use the language of *Tanner graphs* to fully explain the role of *bad counters*, first considered in [BBC+21, §4.1].

**Definition.** A Tanner graph is a very handy tool for analyzing iterative decoding of LDPC or MDPC codes. For LDPC codes, this notion dates back to Gallager who explained and studied his iterative decoding algorithms [Gal63] by using them. In a more general form, they have been defined in [Tan81]. It is a bipartite graph which represents the parity-check matrix $\mathbf{H} = (H_{i,j})_{0 \le i < r \atop 0 \le j < n}$ of a code. It has two types of vertices, the *variable nodes* which are in bijection with the code positions $\{0, \dots, n-1\}$, and the *check nodes* which are in bijection with the parity checks, i.e. the rows of $\mathbf{H}$. There is an edge between a variable node $j$ and the check node $i$ if and only if $H_{i,j} = 1$.

In our case, where $n = 2r$ and the parity-check matrix is formed by two circulant blocks, we can relate this to the polynomial notation established in §2.1 and index the variable nodes and check nodes a little bit differently. More specifically, the variable node associated to the $i$-th position is indexed by $x^i \oplus 0$ if $i < r$ and by $0 \oplus x^{i-r}$ if $i \ge r$. Polynomial notation is also used to index the check nodes. The check node associated to the $i$-th row of $\mathbf{H}$ is indexed by $x^i$. When $\mathbf{H} = (h_0, h_1)$, the set of check nodes adjacent to the variable node $x^i \oplus 0$ is the set of monomials in $x^i h_0(x)$ and the set of check nodes adjacent to the variable node $0 \oplus x^i$ is the set of monomials appearing in $x^i h_1(x)$. Note that the syndrome weight $|\mathbf{H}^\mathrm{T}|$ of an error $\mathbf{e}$ can be read off from the Tanner graph:

**Fact 1.** Consider the subgraph of the Tanner graph induced by an error $\mathbf{e}$: It is formed by the variable nodes belonging to $\mathbf{e}$ and all the check nodes adjacent to it. The number of check nodes of odd degree in this graph is $|\mathbf{H}^\mathrm{T}|$. The counter of a bit is the number of check nodes in this subgraph that are of odd degree and that are adjacent to it in the complete Tanner graph.

**Subgraph induced by a near codeword.** The subgraph $\mathcal{G}$ of the Tanner graph induced by a near codeword $\mathbf{v}$ in $\mathcal{N}$ has a special structure. It has a unusually small number of check nodes for subgraphs induced by $d$ variable nodes. We detail below the structure when $\mathbf{v}$ is $h_0(x) \oplus 0$ and recall that $h_0(x) = \sum_{i=1}^d x^{l_i}$, but the general case can be deduced from this one, by a shift of the positions and/or replacing $l_i$ by $r_i$ in the case of a near codeword $0 \oplus x^m h_1(x)$.

**Fact 2.** Consider the subgraph $\mathcal{G}$ of the Tanner graph induced by $\mathbf{v} = h_0(x) \oplus 0$. The variables nodes are the $d$ variable nodes labeled $x^{l_i} \oplus 0$ for $i \in \{1, \dots, d\}$. The check nodes are all the $x^{l_i+l_j}$. There are at most $\binom{d+1}{2}$ of them. Each pair of variable nodes ($x^{l_i} \oplus 0, x^{l_j} \oplus 0$) in $\mathcal{G}$ has at least one check node in common, namely $x^{l_i+l_j}$.

This simple fact has a number of consequences concerning the influence that near codewords have on the counters. It will be helpful here to distinguish four kind of bits.
**Definition 2.4.** Given a near codeword $\nu$ and a error vector e intersecting $\nu$
in $u$ positions, we classify the $n$ error vector bits into the four categories:

- $u$ bad bits: the $u$ bits belonging to the supports of both $e$ and $\nu$;

- $d-u$ suspicious bits: the other $d-u$ bits of $\nu$ (not in the support of $e$);

- $t-u$ normal bits in error: the other $t-u$ bits of $e$ (not in the support of $\nu$);

- $n-d-t+u$ good bits: neither in $\nu$ nor $e$.

Bad bits and suspicious bits really display an abnormal behavior concerning
the counters due to Fact 2 which explains why they are a nuisance for iterative
decoding. Indeed we expect that the counters $\sigma_j$ behave like (to simplify the
discussion we assume that $\nu = h_0(x) \oplus 0$)

bad bit: $\sigma_j \sim \text{Bin}(u-1, \pi_0) + \text{Bin}(d-u+1, \pi_1)$. The bad bit which is some $x^{l_i} \oplus 0$ is adjacent to $u-1$ check nodes of the form $x^{l_i+l_j}$ where $x^{l_j} \oplus 0$ is another bad bit. The contributions of these two bits for this parity-check cancel out, and this parity-check behaves in first approximation as a parity adjacent to a bit which is not in error. Its probability for not being satisfied is therefore $\pi_0$. Similarly the bad bit is adjacent to the check node $x^{2l_i}$ and $d-u$ check nodes of the form $x^{l_i+l_j}$ where $x^{l_j} \oplus 0$ is now a suspicious bit. In both cases, the contribution of those bits to the parity-check is 1 and these $d-u+1$ parity-checks should behave as parity-checks adjacent to a bit which is in error, in which case the probability of not being satisfied is $\pi_1$.

sus. bit: $\sigma_j \sim \text{Bin}(u, \pi_1) + \text{Bin}(d-u, \pi_0)$. This comes from the fact that the suspicious bit which is some $x^{l_i} \oplus 0$ is adjacent to $u$ check nodes of the form $x^{l_i+l_j}$ where $x^{l_j} \oplus 0$ is a bad bit (they contribute together to 1 in the parity-check) and to $d-u$ check nodes of the form $x^{l_i+l_j}$ where $x^{l_j} \oplus 0$ is another suspicious bit (they contribute together to 0 in the parity-check).

An illustration of this principle is given in the full version of the paper [ALM+25, App. D]. Notice that the greater $u$ is, the greater the chances are to flip a suspicious bit which further increases $u$. This is what we call the snowball effect leading to a potential convergence to a near codeword. This error is readily seen to uncorrectable by further steps of iterative decoding.

3 Convergence to a near codeword in $\mathcal{N}$ in the error floor

To verify the convergence to a near codeword in the error floor region we have
tested parameters for which we can experimentally observe the error floor be-
havior. We have chosen a random QC-MDPC code with $r = 1723$, $d = 17$ and
tested two decoding algorithms:

1. The majority step-by-step decoder: $T = \frac{d+1}{2} = 9$. It flips a bit every time it decreases the syndrome weight. For this decoder, we expect to hit the error floor faster than for other decoders because it has the most chance to flip suspicious bits, thus getting the snowball effect described in § 2.4.
2. An improved step-by-step decoder which uses a better (more conservative) decoding threshold. It starts with a high threshold value $T_0$ which favors to flip bits which are more likely to be in error. It is only when no bit can be flipped that a threshold $T_1 \le T_0$ is used. For a syndrome weight $s$, $T_0$ and $T_1$ are given by: $T_0 = \min\{\max(\lfloor\alpha \cdot s + \beta\rfloor, \frac{d+1}{2})\}$, where $\alpha \stackrel{\text{def}}{=} 0.006016213884791455$, $\beta \stackrel{\text{def}}{=} 8.797325112097532$, $T_1 = \frac{d+1}{2}$.

Fig. 2 shows the experimental results obtained for both decoders. It is a striking illustration of the phenomenon of convergence to a near codeword in the error floor regime for both decoders. The curves corresponding to the “better threshold” decoder correspond to a threshold pair $(T_0, T_1)$ given above. Together with the experimental curve we have drawn two other curves: “Contrib. of ncw” is the contribution to the DFR coming solely from the convergence to a near codeword. This contribution dominates in the error floor regime since the DFR is almost identical to this curve in this region. This can also be seen by removing from the DFR the contribution from the near codewords. These are the curves referred to as “Contr. of other”. These curves show both a waterfall phenomenon and that, as we move further in the error floor region, the DFR contribution coming from convergence to a near codeword dominates the DFR.

<figure><img src="image_3.png" /><figcaption>Fig. 2: DFR vs. error weight ($r = 1723$, $d = 17$), experimental curves.</figcaption></figure>

# 4 Modeling step-by-step Decoding with a Markov Chain

## 4.1 The Markov Model

The Markov model introduced in [SV19b] kept track of the pair $(s, t)$ where $s$ and $t$ are respectively the syndrome weight and the error weight during the step-
by-step decoding process. Here by error we mean the difference $e - e'$ between
the true error $e$ and the estimated error $e'$ in Algorithm 1 and by syndrome we
mean the syndrome of this difference, namely $\mathbf{H}(e - e')^{\top} = \mathbf{s}^{\top} - \mathbf{H} \mathbf{e}'^{\top}$ which
is nothing but the vector $\Delta \mathbf{s}$ in Algorithm 1. This syndrome weight is therefore
always decreasing during the decoding process and we hope to get an error weight
of 0 at the end. The decoding process picks at random a certain error bit $j$ and
checks if $\sigma_j \ge T(s)$. If it is the case, it flips it and the resulting syndrome has
weight equal to $s+d-2\sigma$. $t$ is either decreased or increased by 1 if the bit that is
flipped was in error or not. It may also happen that all counters of the $n$ error
bits are less than $T(s)$. In this case, we go to the blocked state and decoding has
failed. If we get to the $(0,0)$ state, decoding has succeeded.

This model does not take into account the crucial role of near codewords in
the decoding process. Indeed, when the error has a large intersection with one
of such near codewords, then it has also an influence on the syndrome weight
which is smaller. For the two Markov models that we are considering, we are
going to take near codewords into account in two ways: a first method consists
in choosing a particular near codeword $\nu$ and defines a quantity $u$ which is
the size of the intersection of this near codeword with the residual error during
iterative decoding. A second method defines $u$ as the size of the intersection of
the error with the closest near codeword. In all cases, the Markov chain is defined
in a similar way by letting the state be the triple $(s, t, u)$ (actually there is an
additional bit $b$ in the definition of the state in the second method, but this is
unessential for now). There are five transition cases:

- all bits have a counter which is too low to flip them. This we call the blocked state, denoted $\perp$. This corresponds to a decoding failure. This is an absorbing state of the Markov chain: once we are in this state, we stay in it. We denote by $p_{\perp}$ the probability that we are in this state.

- If there exists a bit which can be flipped, we choose one of such bits at random. We flip it and go to the state $(s+d-2\sigma, t', u')$, where if it was a bad bit $t'=t-1$ and $u'=u-1$, a suspicious bit $t'=t+1$ and $u'=u+1$, a normal bit in error $t'=t-1$ and $u'=u$, and a good bit $t'=t+1$ and $u'=u$. Depending on whether the bit was respectively a bad bit, a normal bit in error, a suspicious bit or a good bit, we denote by $q_{\text{bad}}(\sigma)$, $q_{\text{err}}(\sigma)$, $q_{\text{sus}}(\sigma)$, $q_{\text{good}}(\sigma)$ the respective probabilities to flip the corresponding bit conditioned on the fact that there is at least one bit that we can flip. The corresponding transition probabilities are then $(1-p_{\perp})q(\sigma)$ where $\sigma \in \{\text{bad, err, sus, good}\}$.

The transitions are depicted in Fig. 3. All these probabilities can be computed easily once we have the counter probabilities $p_{\text{bad}}(\sigma)$, $p_{\text{err}}(\sigma)$, $p_{\text{sus}}(\sigma)$ and $p_{\text{good}}(\sigma)$ that a bit chosen uniformly at random among respectively the bad bits, the normal bits in error, the suspicious bits and the good bits, has a counter equal to $\sigma$. If we let $p'_{\text{bad}}(\sigma)$, $p'_{\text{err}}(\sigma)$, $p'_{\text{sus}}(\sigma)$ and $p'_{\text{good}}(\sigma)$ the probabilities that a bit chosen uniformly at random has a counter equal to $\sigma$ and belongs respectively to the group **bad**, **norm**, **sus** and **good**, then clearly $p'_{\text{bad}}(\sigma) = \frac{u}{n}p_{\text{bad}}(\sigma)$, $p'_{\text{err}}(\sigma) = \frac{t-u}{n}p_{\text{err}}(\sigma)$, $p'_{\text{sus}}(\sigma) = \frac{d-u}{n(1-p)}p_{\text{sus}}(\sigma)$, $p'_{\text{good}}(\sigma) = \frac{(n-t)-(d-u)}{n(1-p)}p_{\text{good}}(\sigma)$.
<figure><img src="image_4.png" /><figcaption>Fig. 3: Transition diagram starting with syndrome weight $s$, error weight $t$, and intersection $u$ with a $(d, d)$-near codeword $\nu$.</figcaption></figure>

If we let $p \stackrel{\text{def}}{=} \sum_{\sigma<T} (p'_{\text{bad}}(\sigma) + p'_{\text{err}}(\sigma) + p'_{\text{sus}}(\sigma) + p'_{\text{good}}(\sigma))$, then the transition probabilities of Fig. 3 are given by

$$p_{\perp} = \left( \sum_{\sigma<T} p_{\text{bad}}(\sigma) \right)^{u} \left( \sum_{\sigma<T} p_{\text{err}}(\sigma) \right)^{t-u} \left( \sum_{\sigma<T} p'_{\text{sus}}(\sigma) \right)^{d-u} \left( \sum_{\sigma<T} p_{\text{good}}(\sigma) \right)^{n-t-d+u},$$

$$q_{\text{bad}}(\sigma) = \frac{p'_{\text{bad}}(\sigma)}{1-p}, \quad q_{\text{err}}(\sigma) = \frac{p'_{\text{err}}(\sigma)}{1-p}, \quad q_{\text{sus}}(\sigma) = \frac{p'_{\text{sus}}(\sigma)}{1-p}, \quad q_{\text{good}}(\sigma) = \frac{p'_{\text{good}}(\sigma)}{1-p}.$$

The probabilities of the counters $p_{\text{bad}}(\sigma)$, $p_{\text{err}}(\sigma)$, $p_{\text{sus}}(\sigma)$ and $p_{\text{good}}(\sigma)$ depend on the model and will be dealt with later in the paper.

## 4.2 Computing the DFR with the help of the Markov chain

Let us show now how to efficiently compute the stationary probability distribution $\mathbf{P}_{\infty}(\perp|s, t, u)$ which is the probability that, after an infinite number of iterations, we end up in the blocked state (where decoding fails). We let $\mathbf{P}(s', t', u'|s, t, u)$ be the probability of transitioning to state $(s', t', u')$ given that we were previously in state $(s, t, u)$. We make use of the following equality

$$\mathbf{P}_{\infty}(\perp|s, t, u) = \mathbf{P}(\perp|s, t, u) + \sum_{s', t', u'} \mathbf{P}_{\infty}(\perp|s', t', u') \cdot \mathbf{P}(s', t', u'|s, t, u) \quad (3)$$

along with the simple but crucial remark that the only transition probabilities $\mathbf{P}(s', t', u'|s, t, u)$ which are non zero have $s' < s$. This suggests to compute the probabilities $\mathbf{P}_{\infty}(\perp|s, t, u)$ by starting from $s = 0$ and increasing $s$ by 1 each time and the recursion formula (3) to compute the remaining ones. For $s = 0$ we set $\mathbf{P}_{\infty}(\perp|0, t, u) = 0$ if $t < 2d$ and $\mathbf{P}_{\infty}(\perp|0, t, u) = 1$ otherwise. The first rule accounts for the fact that there should be no codeword of weight less than $w = 2d$. We also set $\mathbf{P}_{\infty}(\perp|s, t, u) = 0$ if $s < t(d - t + 1)$ and $t \le d$ to account for the fact that we make the assumption that there is no near-codeword of size $t < d$ which has a smaller syndrome than a subset of size $t$ of a near codeword of $\mathcal{N}$. This leads to Algorithm 2. Computing the initial state distribution $\mathbf{P}(s, t, u)$
<caption>**Algorithm 2** Algorithm for computing the DFR</caption>

```
for all t, u do
    if t < 2d then
        P_∞(⊥|0, t, u) ← 0
    else
        P_∞(⊥|0, t, u) ← 1

for all s, t, u s.t. s < t(d - t + 1) and t ≤ d do
    P_∞(⊥|0, t, u) ← 0

for s = 1 to s_max do
    for all t, u do
        P_∞(⊥|s, t, u) ← Σ_{s' < s, t', u'} P_∞(⊥|s', t', u') · P(s', t', u'|s, t, u) + P(⊥|s, t, u)
    DFR ← Σ_{s, t, u} P_∞(⊥|s, t, u) P(s, t, u).
```
▷ initialization

▷ main loop

is detailed in the full version of the paper [ALM+25, App. A]. Note that once this initial probability distribution is computed, the complexity for computing the DFR is just of order $O(E + S)$ where $E$ is the number of possible transitions in the Markov chain and $S$ the number of states.

## 5 A Simple Markovian Model

Since convergence to a near codeword dominates the error floor, it must be accounted for in a Markov state modeling the decoding process. Such states are triples $(s, t, u)$, where $s$ is the syndrome weight, $t$ is the error weight, and $u$ is the size of the intersection of the support of the error with a fixed, random near codeword $\nu$. To amplify this effect by the size of the set of near codewords, we post-process the DFR obtained by this model together with a DFR obtained from a variant model which does not take into account the effect of near codewords. The equation used to combine these DFRs is given in §5.2. This is in contrast to the models used in §6), where only the effect of the closest near codeword is taken into account, and this remains the only near codeword which is assumed to have an effect on the decoding process.

**Model 1 (M).** Let $e$ be an error of weight $t$ with syndrome of weight $s$, and let $\nu$ be a fixed random near codeword. Let $u \stackrel{\text{def}}{=} |e \star \nu|$. This model follows the values $(s, t, u)$ through the decoding process using a step-by-step decoder.

**Model 2 (M0).** Let $e$ be an error of weight $t$ with syndrome of weight $s$. This model follows the same values as Model 1, but the value $u$ is set to 0 in the initial vector, so this model does not take into account the effect of a near codeword.

Our model combining Models 1 and 2 according to the formula given in §5.2, is bound to see an error floor behavior: when the number of overlaps between an error vector and the near codeword becomes as large as possible (i.e., as $u$ approaches $d$), decoding fails, and the probability that $u = d$ at the beginning
of decoding is lower bounded by $\frac{t^d}{n^d}$ where $t$ is the initial error weight. In the waterfall region, the DFR decays more than exponentially in $n$ with other parameters fixed and therefore this $\frac{t^d}{n^d}$ term is going to dominate and provoke an error floor phenomenon.

In summary: we distinguish bad, suspicious, normal, and good bits (Def. 2.4). We estimate the probabilities $\pi_0$ and $\pi_1$ to take into account $s$, $t$ and $u$. Recall $\pi_0$ is the probability that a parity-check adjacent to a given bit which is a good bit is not satisfied, and $\pi_1$ is the probability that a parity-check adjacent to a given bit which is a normal bit in error is not satisfied. The transition probabilities are obtained under the assumptions described in the following section.

## 5.1 Assumptions

The forced cancellations are a result of the quasi-cyclic structure of $\mathbf{H}$. For the remainder of Section 5, we make the heuristic assumption that the columns of $\mathbf{H}$ are drawn uniformly at random up to fixed column weight $d$.

For convenience of counting arguments, the error vector $\mathbf{e}$ may be permuted so that the bad, suspicious, normal, and good bits are collected. Let $\mathbf{Q}$ denote this permutation matrix. Likewise, the bits of the syndrome $\mathbf{s}$ may be permuted to collect the 1's and 0's. Let $\mathbf{P}$ denote this permutation matrix. Applying these permutations to the parity check matrix $\mathbf{H}$ and flipping the canceling pairs yields a matrix $\mathbf{H}'_{\text{eff}} := \mathbf{PHQ}$. Details may be found in the full version of the paper [ALM$^+$25, App. C]. We use random variables to describe the columns of $\mathbf{H}'_{\text{eff}}$. Let $X_{\text{eff}} := \sum_{j \in \text{supp}(\mathbf{e})} \sigma_j - |\mathbf{s}|$. $X_{\text{eff}}$ measures the deviation from the ideal case where exactly one error is involved in each unsatisfied parity-check equation.

**Proposition 5.1.** Assuming that the random variables that indicate the number of errors $|\mathbf{H}_i \star \mathbf{e}|$ for a given equation $i$ are independent and if $|\mathbf{e}| = t$, the expectation of $X_{\text{eff}}$ knowing $s$, $t$, and $u = |\mathbf{e} \star \mathbf{v}|$ is

$$E[X_{\text{eff}}|s, t, u] = s \cdot \frac{\sum_l 2l\rho_{2l+1}}{\sum_l \rho_{2l+1}}, \quad \text{where} \quad (4)$$

$$\rho_l = \sum_{j=0}^{l} \binom{t-u}{j} \binom{u}{l-j} \left(\frac{d}{r}\right)^j \left(\frac{r-d}{r}\right)^{t-u-j} \left(\frac{d+1-u}{r}\right)^{l-j} \left(\frac{r-d-1+u}{r}\right)^{u-l+j} \quad (5)$$

is the probability that any row in $\mathbf{H}'_{\text{eff}}$ restricted to the support of $\mathbf{e}$ has weight $l$.

*Proof.* For any row $i \in \{0, \dots, r-1\}$ in $\mathbf{H}'_{\text{eff}}$, consider the $t$ columns corresponding to the support of $\mathbf{e}$. There are $t-u$ columns corresponding to bits in $\text{supp}(\mathbf{e}) \setminus \text{supp}(\mathbf{v})$ and $u$ columns corresponding to bits in $\text{supp}(\mathbf{e}) \cap \text{supp}(\mathbf{v})$. All columns in $\text{supp}(\mathbf{e}) \setminus \text{supp}(\mathbf{v})$ have weight $d$ and all columns in $\text{supp}(\mathbf{e}) \cap \text{supp}(\mathbf{v})$ have weight $d+1-u$ due to forced cancellations. Any entry in row $i$ on $\text{supp}(\mathbf{e}) \setminus \text{supp}(\mathbf{v})$ has probability $\frac{d}{r}$ of being nonzero and probability $\frac{r-d}{r}$ of being zero. Any entry in row $i$ on $\text{supp}(\mathbf{e}) \cap \text{supp}(\mathbf{v})$ has probability $\frac{d+1-u}{r}$ of being nonzero and probability $\frac{r-d-1+u}{r}$ of being zero.
**Assumption 1.** The counters $\sigma_j$ follow binomial distributions:

$$ \sigma_j \sim \begin{cases} \text{Bin}(d, \pi_0) & \text{if } j \text{ is a good bit} \\ \text{Bin}(d, \pi_1) & \text{if } j \text{ is a normal bit} \\ \text{Bin}(d-u, \pi_0) + \text{Bin}(u, \pi_1) & \text{if } j \text{ is a suspicious bit} \\ \text{Bin}(d-u+1, \pi_1) + \text{Bin}(u-1, \pi_0) & \text{if } j \text{ is a bad bit} \end{cases} \quad (6) $$

where

$$ \pi_0 = \frac{s}{r}, \quad \pi_1 = \frac{s + \xi E[X_{eff}|s, t, u]}{s_{max}}, \quad s_{max} = d \cdot t - 2 \binom{u}{2} $$

for some constant $\xi$.

**Remark 5.2.** The probability estimate $\pi_0$ in Assumption 1 is particularly pessimistic. Indeed, it is the probability that a random parity check is not satisfied, which is certainly an upper bound for the probability that a parity check corresponding to a bit which is not in error is unsatisfied. The model in Section 6 uses a more refined estimate of the probability $\pi_0$.

**Remark 5.3.** The constant $\xi$ in Assumption 1 is inherited from a refinement given in [Vas21] of the previous Markov model [SV19b]. Reducing the value of $\xi$ from 1 was intended to compensate for Non-Markovian effects relative to the state information $(s, t)$ used in that model, which would otherwise produce an overly optimistic DFR. The experimental data in Figure 4 assumes the same value $\xi = 0.955$ used by [Vas21], which further contributes to the pessimism of Assumption 1 as reflected in our experimental data. There is no analogous factor to $\xi$ used in Section 6.

**Assumption 2.** The step-by-step bit flipping decoder is a time homogeneous Markov chain, meaning that the transition probabilities are time invariant.

**Markov end states.** There are two possible Markov end states that dominate the experiment findings: $(0, 0, 0)$ when we have successful decoding or $(d, d, d)$ when the state converges to a $(d, d)$-near codeword.

## 5.2 Markov Model Estimation of the DFR

Our simple Markov model experiments yield the decoding failure rate under the assumptions of models 2 and 1. Model 2 assumes no effect of the near codewords $N$ on the decoding failure rate and Model 1 records the effect of a single near codeword on the decoding failure rate. Model 2 uses the same code but initializes the value of $u$ to 0 in the initial vector.

Let DFR(M) and DFR(M0) denote the respective decoding failure rates of Model 1 and 2. The true decoding failure rate denoted by DFR, is estimated by taking into account the existence of $|N| = r$ near codewords. The difference DFR(M) - DFR(M0) accounts for the number of decoding failures due to the
existence of one near codeword, so $|\mathcal{N}|(\text{DFR}(M) - \text{DFR}(M_0))$ gives the increase in DFR due to the existence of $|\mathcal{N}|$ near codewords. This gives the formula:

$$ \text{DFR} = \text{DFR}(M_0) + |\mathcal{N}|(\text{DFR}(M) - \text{DFR}(M_0)). \quad (7) $$

This assumes an additive effect of the elements of $\mathcal{N}$ on DFR, and we refer to Equation (7) as the *linear model* (see Fig. 4). We compare our data with experimental data obtained using [Vas24], as well as a previous Markov model [SV19b] which does not take into account the effect of the error having a large number of overlaps with a near codeword. The Simple Markov model gives a more conservative estimate for the DFR, in instances where models not taking into account the effect of near codewords underestimate the DFR.

<figure><img src="image_5.png" /><figcaption>Fig. 4: Plot of experimental DFR data, Simple Markov model DFR, and the DFR of the Markov model described in [SV19b].</figcaption></figure>

# 6 A Key Dependent Markov Model

The simplified model does not depend on the secret key. However, experimental evidence shows that the DFR is definitely key dependent: Even if it does not vary much for typical keys, there are rare keys for which this DFR behaves better and weak keys which behave significantly worse. In this section, we give a way to predict the iterative decoding performance which is key dependent. It makes use of the degree distribution of the subgraph $\mathcal{G}$ of the Tanner graph associated to the near codeword closest to $e' + e$ denoted in the whole section by $\nu$.

## 6.1 Derivation of the Markov chain model

**The state space.** The state space is the set of $(s, t, u, b)$ where $s = |\Delta s|$ and $t = |e + e'|$ as before, $u = |(e + e') \star \nu|$ and $b \in \{0, 1\}$ encodes whether or not
$\nu$ is $x^a h_0(x) \oplus 0$ (a left near codeword) or $0 \oplus x^b h_1(x)$ (a right near codeword). The structure of $\mathcal{G}$ depends on $b$. Its degree structure is given by the following proposition which follows immediately from Fact 2

**Proposition 6.1.** The parity checks of even degree $2m$ in the subgraph $\mathcal{G}$ corresponding to a left near codeword are associated to sets of $m$ different pairs $\{l_{a_1}, l_{b_1}\}, \dots, \{l_{a_m}, l_{b_m}\}$ such that $l_{a_1} + l_{b_1} = \dots = l_{a_m} + l_{b_m}$, where the $a_i$'s and the $b_i$'s all belong to $\{0, \dots, d-1\}$ and $a_i \neq b_i$ for all $i \in \{1, \dots, m\}$. The parity checks of odd degree $2m+1$ in $\mathcal{G}$ are associated to an $a \in \{0, \dots, d-1\}$ and sets of $m$ different pairs $\{l_{a_1}, l_{b_1}\}, \dots, \{l_{a_m}, l_{b_m}\}$ such that $2l_a = l_{a_1} + l_{b_1} = \dots = l_{a_m} + l_{b_m}$, where $a_i, b_i \in \{0, \dots, d-1\}$ and $a_i \neq b_i$ for all $i \in \{1, \dots, m\}$.

A similar proposition holds for right near codewords where the $r_i$'s replace the $l_i$'s. We can partition the set of code positions in four sets, the bad bits, the suspicious bits, the normal bits in error and the good bits. We will simplify notation in what follows and label a parity check $x^a$ simply by $a$. We assume from now on that the closest near-codeword $\nu$ to the error intersects it in exactly $u$ positions and that the error has weight $t$. We also assume that $\nu = h_0(x) \oplus 0$. The case $\nu = 0 \oplus h_1(x)$ is similar. The label $x^a \oplus 0$ of a variable node is also simplified to $a$. In this section, we explain how we model the counters for each kind of bits. This will lead to Model 3 which is then used as explained in §4.

**The case of bad bits.** We have three kinds of parity checks adjacent to a bad bit. If the label of the bad bit is $a_1$, the labels of the other bad bits are $a_2, \dots, a_u$, and the labels of the suspicious bits are $a_{u+1}, \dots, a_d$, then we can group the parity check nodes adjacent to $a_1$. The first group consists of a single parity check node of odd degree in $\mathcal{G}$ labeled $2a_1$. The second group consists of $(u-1)$ parity check nodes labeled $a_1 + a_2, \dots, a_1 + a_u$. The third group consists of $(d-u)$ parity check nodes labeled $a_1 + a_{u+1}, \dots, a_1 + a_d$.

We do not know the label $a_1, \dots, a_u$, and we model the probability that the corresponding parity checks are unsatisfied by using the following lemma.

**Lemma 6.2.** Let a be a bad bit and let

- $\rho_{\Delta, \ell}^{b,1}$ be the probability that the parity check labeled $2a$ is adjacent to $\ell$ bits in error given that it is of degree $\Delta$ in $\mathcal{G}$;

- $\rho_{\Delta, \ell}^{b,2}$ be the probability that a parity check labeled $a+b$ of degree $\Delta$ in $\mathcal{G}$ is adjacent to $\ell$ bits in error given that it $b$ is another bad bit;

- $\rho_{\Delta, \ell}^{b,3}$ be the probability that a parity check labeled $a+b$ is adjacent to $\ell$ bits in error given that it is of degree $\Delta$ in $\mathcal{G}$, that $b$ is a suspicious bit;

$$ \text{Then} \quad \rho_{\Delta, \ell}^{b,1} = \frac{\sum_{j=1}^{\min(\Delta, \ell)} \binom{\Delta-1}{j-1} \binom{d-\Delta}{u-j} \binom{w-\Delta}{\ell-j} \binom{n-d-w+\Delta}{t-u-\ell+j}}{\binom{d-1}{u-1} \binom{n-d}{t-u}} $$

$$ \rho_{\Delta, \ell}^{b,2} = \frac{\sum_{j=2}^{\min(\Delta, \ell)} \binom{\Delta-2}{j-2} \binom{d-\Delta}{u-j} \binom{w-\Delta}{\ell-j} \binom{n-d-w+\Delta}{t-u-\ell+j}}{\binom{d-2}{u-2} \binom{n-d}{t-u}} $$

$$ \rho_{\Delta, \ell}^{b,3} = \frac{\sum_{j=1}^{\min(\Delta, \ell)} \binom{\Delta-2}{j-1} \binom{d-\Delta}{u-j} \binom{w-\Delta}{\ell-j} \binom{n-d-w+\Delta}{t-u-\ell+j}}{\binom{d-2}{u-1} \binom{n-d}{t-u}} $$
*Proof.* The reasoning is similar in all three cases.

<figure><img src="image_6.png" /><figcaption>Fig. 5: The configuration of the error and the parity check. The black and pink are the positions of the parity check. The numbers on top are the block sizes. The numbers below are the number of errors in each block. The first block of size 1 is the bad bit $a$. The second block consists of the other positions involved in the parity check and the support of $\nu$. The third block consists of the positions in the support of $\nu$ not involved in the parity check equation. The fourth block consists of the positions of the parity check which are not in the support of $\nu$. The last block contains the remaining positions.</figcaption></figure>

The formula for $\rho_{\Delta, \ell}^{b,1}$. We compute the probability that an error of weight $t$ which has weight $u$ on the $d$ bits of the near-codeword $\nu$ and $t-u$ on the complement of the support of $\nu$ intersects a given parity check of weight $w$ in exactly $\ell$ positions. The parity check $2a$ involves the bad bit $a$ we are interested in, plus $\Delta-1$ other bits of $\nu$. If we denote by $\rho_{\Delta, \ell, j}^{b,1}$ the probability that this error is also of weight $j$ on the $\Delta$ bits which belong at the same time to the support of the parity check labeled $2a$ and the support of $\nu$, then we have

$$ \rho_{\Delta, \ell, j}^{b,1} = \frac{\binom{\Delta-1}{j-1} \binom{d-\Delta}{u-j} \binom{w-\Delta}{\ell-j} \binom{n-d-w+\Delta}{t-u-\ell+j}}{\binom{d-1}{u-1} \binom{n-d}{t-u}} $$

This can be verified by counting the number of ways the $\binom{d-1}{u-1} \binom{n-d}{t-u}$ configurations of $t-1$ errors where there are $u-1$ errors among the $d-1$ bits of $\nu$ other than the bad bit $a$ we are interested in satisfy all the needed constraints. Figure 5 gives a picture of the configuration we are interested in. This yields the formula for $\rho_{\Delta, \ell}^{b,1}$ by summing over all possible values of $j$.

The formula for $\rho_{\Delta, \ell}^{b,2}$. We introduce $\rho_{\Delta, \ell, j}^{b,2}$, the probability that the error is also of weight $j$ on the $\Delta$ bits which belong to the support of the parity check labeled $a+b$ and the support of $\nu$. Then,

$$ \rho_{\Delta, \ell, j}^{b,2} = \frac{\binom{\Delta-2}{j-2} \binom{d-\Delta}{u-j} \binom{w-\Delta}{\ell-j} \binom{n-d-w+\Delta}{t-u-\ell+j}}{\binom{d-2}{u-2} \binom{n-d}{t-u}} $$

Fig. 6 displays the corresponding configuration. The difference is that now the parity check labeled $a+b$ contains two bits which are in error, namely $a$ and $b$. The formula for $\rho_{\Delta, \ell}^{b,3}$. This uses a similar reasoning, with the only difference that the parity check labeled $a+b$ contains by definition a bit which is in error, namely $a$ and a bit which is not in error, namely $b$. $\square$
<figure><img src="image_7.png" /><figcaption>Fig. 6: The configuration of the error and the parity check, as in Figure 5. The first block of size 2 corresponds to bad bits a and b. The second block consists of the other positions involved in the parity check which are in the support of the near codeword $\nu$. The last three blocks are as in Figure 5.</figcaption></figure>

**Proposition 6.3.** For $g \in \{1, 2, 3\}$, let $\pi^{b,g}$ be the average probability that a parity check of group $g$ associated to a bad bit is unsatisfied. Then

$$ \overline{\pi^{b,1}} = \frac{1}{d} \sum_{a \in \nu} \sum_{\ell} \rho_{\deg(2a), 2\ell+1}^{b,1}, \\ \overline{\pi^{b,g}} = \frac{1}{d(d-1)} \sum_{a \in \nu} \sum_{b \in \nu, b \neq a} \rho_{\deg(a+b), 2\ell+1}^{b,g}, \text{ for } g \ge 2, $$

where $\deg(c)$ is the degree of the parity check node $c$ in $\mathcal{G}$.

*Proof.* The probability that the parity check labeled $2a$ associated to a bad bit $a$ is unsatisfied is $\sum_{\ell} \rho_{\deg(2a), 2\ell+1}^{b,1}$. The average is taken over all possible bits of the near codeword $\nu$. The reasoning is the same for $\pi^{b,g}$, the only difference is that we take the average over all possible edges leaving a variable node labeled $a$ to a check node labeled $a+b$ for all possible $b$'s different from $a$. $\square$

**The case of suspicious bits.** The case of a suspicious bit is similar to the case of a bad bit. We partition the parity checks associated to it in three groups, as we did for a bad bit. There is a single parity check in the first group associated to a suspicious bit $a$, namely the parity check labeled $2a$. The second group contains $d-u-1$ other parity checks labeled $a+b$ where $b$ is another suspicious bit. The last group contains $u$ parity check bits labeled $a+b$ where $b$ is a bad bit.

**Lemma 6.4.** Let $a$ be a suspicious bit and let

- $\rho_{\Delta, \ell}^{s,1}$ be the probability that the parity check labeled $2a$ in $\mathcal{G}$ is adjacent to $\ell$ bits in error given that it is of degree $\Delta$ in $\mathcal{G}$;

- $\rho_{\Delta, \ell}^{s,2}$ be the probability that a parity check labeled $a+b$ is adjacent to $\ell$ bits in error given that it is of degree $\Delta$ in $\mathcal{G}$ and $b$ is another suspicious bit;

- $\rho_{\Delta, \ell}^{s,3}$ be the probability that a parity check labeled $a+b$ is adjacent to $\ell$ bits in error given that it is of degree $\Delta$ in $\mathcal{G}$, that $b$ is a bad bit.
$$
\begin{align*}
\rho_{\Delta, \ell}^{s,1} &= \frac{\sum_{j=0}^{\min(\Delta, \ell)} \binom{\Delta-1}{j} \binom{d-\Delta}{u-j} \binom{w-\Delta}{\ell-j} \binom{n-d-w+\Delta}{t-u-\ell+j}}{\binom{d-1}{u} \binom{n-d}{t-u}} \\
\rho_{\Delta, \ell}^{s,2} &= \frac{\sum_{j=0}^{\min(\Delta, \ell)} \binom{\Delta-2}{j} \binom{d-\Delta}{u-j} \binom{w-\Delta}{\ell-j} \binom{n-d-w+\Delta}{t-u-\ell+j}}{\binom{d-2}{u} \binom{n-d}{t-u}} \\
\rho_{\Delta, \ell}^{s,3} &= \frac{\sum_{j=1}^{\min(\Delta, \ell)} \binom{\Delta-2}{j-1} \binom{d-\Delta}{u-j} \binom{w-\Delta}{\ell-j} \binom{n-d-w+\Delta}{t-u-\ell+j}}{\binom{d-2}{u-1} \binom{n-d}{t-u}}.
\end{align*}
$$

**Proposition 6.5.** For $g \in \{1, 2, 3\}$, let $\pi^{s,g}$ be the average probability that a parity check of group $g$ associated to a suspicious bit is unsatisfied. Then

$$
\begin{align*}
\overline{\pi}^{s,1} &= \frac{1}{d} \sum_{a \in \nu} \sum_{\ell} \rho_{\deg(2a), 2\ell+1}^{s,1} \\
\overline{\pi}^{s,g} &= \frac{1}{d(d-1)} \sum_{a \in \nu} \sum_{b \in \nu, b \neq a} \rho_{\deg(a+b), 2\ell+1}^{s,g}, \quad \text{for } g \ge 2.
\end{align*}
$$

Here deg(c) refers to the degree of the parity check node c in $\mathcal{G}$.

**The case of normal bits in error.** We do not need to distinguish several groups of parity checks in this case.

**Proposition 6.6.** Let $\rho_{\Delta, \ell}^e$ be the probability that a parity check node of degree $\Delta$ in the subgraph $\mathcal{G}$ of the Tanner graph induced by $\nu$ and adjacent to a normal bit in error contains exactly $\ell$ erroneous bits. A parity check not in $\mathcal{G}$ is said to be degree of 0. We also let $\pi^e$ be the average of these probabilities over all edges of the Tanner graph leaving the bits which are not in $\nu$.

$$
\rho_{\Delta, \ell}^{e} = \frac{\sum_{j=0}^{\min(\Delta, \ell-1)} \binom{\Delta}{j} \binom{d-\Delta}{u-j} \binom{w-\Delta-1}{\ell-j-1} \binom{n-d-w+\Delta}{t-u-\ell+j}}{\binom{d}{u} \binom{n-d-1}{t-u-1}} \quad (8)
$$

$$
\overline{\pi}^e = \frac{1}{d(n-d)} \sum_{\Delta} (w - \Delta) n_{\Delta} \sum_{\ell} \rho_{\Delta, 2\ell+1}^e, \quad (9)
$$

where $n_{\Delta}$ is the number of check nodes in the subgraph $\mathcal{G}$ of the Tanner graph induced by $\nu$ which are of degree $\Delta$.

*Proof.* The reasoning for (8) is similar to what is done for Lemma 6.2 and is omitted. For computing the average of (8), observe that there are $d(n-d)$ edges in the Tanner graph leaving the $n-d$ positions which are not in $\nu$. $\rho_{\Delta, \ell}^e$ is nothing but the average probability over all edges that such an edge is adjacent to a check node which is not satisfied. If such a check node is of degree $\Delta$ in $\mathcal{G}$, then the probability that it is in error is exactly $\sum_{\ell} \rho_{\Delta, 2\ell+1}^e$. There are exactly $(w-\Delta)n_{\Delta}$ edges of this kind that are adjacent to a check node of degree $\Delta$ in $\mathcal{G}$. This explains (9).
**The case of good bits.** This case is similar to the case of normal bits in error.

**Proposition 6.7.** Let $\rho_{\Delta, \ell}^g$ be the probability that a parity check node of $\mathcal{G}$ of degree $\Delta$ adjacent to a good bit contains exactly $\ell$ erroneous bits. We also let $\pi^g$ be the average of these probabilities over all edges of the Tanner graph leaving the bits which are not in $\nu$. We have

$$ \rho_{\Delta, \ell}^g = \frac{\sum_{j=0}^{\min(\Delta, \ell)} \binom{\Delta}{j} \binom{d-\Delta}{u-j} \binom{w-\Delta-1}{\ell-j} \binom{n-d-w+\Delta}{t-u-\ell+j}}{\binom{d}{u} \binom{n-d-1}{t-u}} \quad (10) $$

$$ \overline{\pi}^g = \frac{1}{d(n-d)} \sum_{\Delta} (w-\Delta)n_{\Delta} \sum_{\ell} \rho_{\Delta, 2\ell+1}^g, \quad (11) $$

This analysis of bad, suspicious, normal, and good bits yields the following model:

**Model 3.** We model the counters $\sigma_i$ according to the type of bit:

$$ - \text{bad bit: } \sigma_i \sim \text{Bin}(1, \frac{s\pi^{b,1}}{\mathbb{E}(s|t,u)}) + \text{Bin}(u-1, \frac{s\pi^{b,2}}{\mathbb{E}(s|t,u)}) + \text{Bin}(d-u, \frac{s\pi^{b,3}}{\mathbb{E}(s|t,u)}) $$

$$ - \text{suspicious bit: } \sigma_i \sim \text{Bin}(1, \frac{s\pi^{s,1}}{\mathbb{E}(s|t,u)}) + \text{Bin}(d-u-1, \frac{s\pi^{s,2}}{\mathbb{E}(s|t,u)}) + \text{Bin}(u, \frac{s\pi^{s,3}}{\mathbb{E}(s|t,u)}) $$

$$ - \text{normal bit in error: } \sigma_i \sim \text{Bin}(d, \frac{s\pi^e}{\mathbb{E}(s|t,u)}) $$

$$ - \text{good bit: } \sigma_i \sim \text{Bin}(d, \frac{s\pi^g}{\mathbb{E}(s|t,u)}) $$

where $\mathbb{E}(s|t, u)$ is given by:

$$ \mathbb{E}(s|t, u) = \frac{1}{w} \left( u\overline{\pi}^{b,1} + u(u-1)\overline{\pi}^{b,2} + u(d-u)\overline{\pi}^{b,3} + (d-u)\overline{\pi}^{s,1} \right. \\ \left. + (d-u)(d-u-1)\overline{\pi}^{s,2} + (d-u)u\overline{\pi}^{s,3} + (t-u)d\overline{\pi}^{e} + (n+u-t-d)d\overline{\pi}^{g} \right) $$

## 6.2 Results

First, we checked this new model on the same toy example of §5 with a random key (see Fig. 7). It gives a much better behavior in the waterfall region than the previous model. We partition decoding failures both in the experiments and in the model in two parts: the decodings that failed because they converged to a near codeword ("Contr. of ncw") and the rest of the decoding failures (called "Contr. of other"). The models and the experiments agree remarkably well.

We also tested two different step-by-step decoders on the same code: one which uses the majority rule for the threshold, and another one which uses the decoder with two thresholds $T_0$ and $T_1$, see Figure 2. There is a first conservative threshold to flip the bits initially, and a second threshold (actually the majority rule) to flip the bits when there are no more bit flips to perform with the first rule. This decoder is much better than the majority decoder.

In [Vas21] which compared parallel decoders to similar step-by-step decoders, the performance of the parallel decoders was much better than those of the step-by-step decoders. However, the step-by-step decoder with two thresholds used
<figure><img src="image_8.png" /><figcaption>Fig. 7: DFR vs. error weight ($r = 1723$, $d = 17$), experiments vs. model.</figcaption></figure>

to draw Figure 7 is rather competitive with the parallel BGF decoder of BIKE, see Figure 8. This seems to confirm that there is a significant gain in choosing conservative thresholds in the early iterations, as observed in [Sen24]. The BGF decoder is slightly superior to the step-by-step decoder, with a somewhat steeper waterfall and a better error floor.

<figure><img src="image_9.png" /><figcaption>Fig. 8: DFR vs. error weight ($r = 1723$, $d = 17$), BGF vs. step-by-step.</figcaption></figure>

After all this experimental evidence, we ran the model of this section on a key chosen at random for the step-by-step decoder by choosing several different thresholds for various block sizes for $d = 71$ and $t = 134$. See Figure 9.

We checked the influence of the gap parameter $\delta$ used for decoding. Here the threshold $T$ depends only on the syndrome weight $s$, the block length $r$, the
<figure><img src="image_10.png" /><figcaption>Fig. 9: DFR vs. block size ($d = 71, t = 134$).</figcaption></figure>

error weight $t$ and the gap parameter $\delta$ as follows

$$T = \min \left( d, \max \left( \lfloor A_{r,t}(s) + \delta \rfloor, \frac{d+1}{2} \right) \right), \quad (12)$$

where $A_{r,t}(s)$ is an affine function $\alpha \cdot s + \beta$ of $s$ depending on $r$ and $t$ which is computed with the same method as for BIKE. For $t = 134$ and various values of $r$, the coefficients are given in the full version of the paper [ALM+25, App. B].

Using the same gap parameter $\delta = 3$ as the one used in the latest BIKE decoder seems in the model to be optimal for the actual BIKE 1 parameter: $r = 12323$. It results in a DFR of about $2^{-91.7}$, unfortunately above $2^{-\lambda}$. Moreover, even if we increase the block length $r$ we do not improve the DFR by much, because the error floor kicks in right after this value of $r$. We attain a DFR of $2^{-114.1}$ with this gap for $r = 13109$, but need to go to $r = 18427$ to go below $2^{-\lambda}$. Using a gap $\delta$ equal to 4 allows to an error floor which appears a little bit later and allows to obtain a DFR which is about $2^{-119.6}$ for $r = 13477$. This $r$-value is less than 10 percent more than the actual BIKE parameter.

**Experimental evidence for cryptographic parameters in the waterfall region.** However there is a caveat here. It appears that taking a larger threshold function affects the accuracy of the waterfall prediction. Indeed, we have performed two kinds of experiments for values of $r$ close to the BIKE 1 parameters and the same $d$ and $t$ as BIKE 1 so as to be able to observe experimentally the DFR. We are here at the beginning of the waterfall. Figure 10 shows that the model predicts accurately the waterfall behavior when $\delta = 1$, but the predictions become clearly optimistic when $\delta$ increases (here we show the value $\delta = 3$. More experimental evidence can be found in the full version of the paper [ALM+25].
<figure><img src="image_11.png" /><figcaption>Fig. 10: Waterfall behavior ($d = 71, t = 134$), gap $\delta \in \{1, 3\}$.</figcaption></figure>

**Evidence that the error floor behavior is always captured accurately.**

To have a better understanding of the influence of $\delta$, we have performed a systematic study on the toy parameters $(r, d) = (1723, 17)$. First we have chosen $t = 65$ to be in the waterfall region. The results are displayed in Fig. 11a. There are several interesting features. The DFR is split in two parts as $\text{DFR} = \text{DFR}_e + \text{DFR}_w$, where $\text{DFR}_e$ corresponds to the convergence to a near codeword. It can be computed experimentally when $\text{DFR}_e$ is large enough. The Markov model can also give the corresponding contribution. The term $\text{DFR}_w$ (as “waterfall” contribution and “other” in legend of the figure) can be viewed as the waterfall contribution and is defined simply as $\text{DFR} - \text{DFR}_e$. In Fig. 11a we are in the waterfall region since $\text{DFR} \approx \text{DFR}_w$ or what amounts to the same $\text{DFR}_e \ll \text{DFR}_w$. The Markov chain predictions are slightly pessimistic when $\delta$ is in the interval $[0, 1]$ but become optimistic in the case $\delta \in [1, 3]$. However, what is remarkable is that the predictions for the error floor term $\text{DFR}_e$ are in general really accurate for a gap bigger than 0.5. This strongly suggests that the Markov model predicts accurately the error floor behavior irrespective of the gap parameter.

This has been further tested in Fig. 11b with $(r, d, t) = (1723, 17, 35)$. This time we are in the error floor since $\text{DFR}_w \ll \text{DFR}_e$. The predictions for the DFR are here rather accurate (even if a little bit pessimistic). The experimental DFR and predicted DFR agree this time for all values of the gap parameter between 0 and 3. This shows the accuracy of the error floor prediction for our model.

We can extend experiments much beyond the toy parameters by noticing that we can decompose the DFR as $\text{DFR} = \sum_{u=1}^{d} \text{DFR}(u)p(u)$, where $\text{DFR}(u)$ is the DFR conditioned on the event that the closest near-codword intersects the error in exactly $u$ positions and $p(u)$ is the probability that this event occurs. We can tweak the initial distribution of the Markov chain so as to compute exactly $\text{DFR}(u)$. In the case where the dominating terms in this sum correspond to $u$'s for which $p(u)$ is small and the corresponding $\text{DFR}(u)$ are large enough, we can run experiments conditioned that the error intersects the closest near-codword in
<figure><img src="image_12.png" /><figcaption>Fig. 11</figcaption></figure>

exactly *u* positions and check if DFR(*u*) is indeed predicted correctly. This allows
to make such verification way beyond DFR’s that we can measure experimentally.
This approach has permitted to expand significantly the regime of parameters
that we can verify experimentally. We were able to increase the value of *d* from 17
to 27, *t* from 35 to 46 and *r* from 1723 to 17053. All our parameters that have been
found are such that we can verify the contribution of the *f*(*u*) def= DFR(*u*)*p*(*u*)
around the value of *u* for which this contribution attains its maximum. In all
cases we get a remarkable prediction of *f*(*u*) = DFR(*u*)*p*(*u*) for large values of
*u* and a good prediction around the maximum of *f*(*u*) which is just a little bit
pessimistic in this case. All in all, these experiments permit to verify values of
DFR that are as low as 2<sup>-80</sup>.

We have also performed experiments for the cryptographic parameters. The
Markov model predictions agree well for the DFR(u) that we were able to check
as Figure 13 shows.

**Changing the threshold function.** A closer inspection of the affine function $A_{r,t}$ used in BIKE specification shows that for a large set of values of *s* (roughly between 0 and more than 70 per cent of the typical initial syndrome value) the threshold takes the value $\frac{d+1}{2}$. This seems to be a bad choice: the majority threshold rule maximizes the probability of flipping a suspicious bit. This leads to the convergence to a near-codeword and thus to the error floor phenomenon. Instead of (12), it is tempting to conjecture that the modified threshold function $T = \min(d, \max(A_{r,t}(s) + \delta, T_{\min}))$ might perform better, where $T_{\min} > \frac{d+1}{2}$. For the BIKE 1 parameters, $d = 71$ and $\frac{d+1}{2} = 36$. For this reason, we tried to
<figure><img src="image_13.png" /><figcaption>Fig. 12</figcaption></figure>

optimize the threshold function in order to lower the DFR. The full version of the paper [ALM+25] explains how this optimization was performed (and gives in §B.2 a full description of the threshold function). It gave a threshold function where $T_{min} = 39$ where DFR $\approx 2^{-126.736}$ for $r = 13109$. For $r = 13477$, with $T_{min} = 39$ and $\delta = 3.4$ we obtain DFR $\approx 2^{-131.259}$.

The code used to compute the DFR according to this model is available at https://github.com/vvasseur/qcmdpc_markov_ncw.

# 7 Concluding Remarks

A new accurate Markov model. This work highlights the central role that the near codewords put forward in [Vas21] play in the error floor regime. We enrich the Markov model of [SV19b,Vas21] with the size of the intersection of the error with a near codeword. Using a model which is key-dependent, we obtain an accurate prediction of the DFR in the error-floor regime, matching experimental data for various decoders and keys.
<figure><img src="image_14.png" /><figcaption>Fig. 13: $(d, t, \delta) = (71, 134, 3)$</figcaption></figure>

Attaining a DFR below $2^{-\lambda}$. If we run this Markov model on BIKE 1 parameters with the former threshold function, we fall short of reaching a DFR of about $2^{-91}$, which is below $2^{-\lambda}$. This problem cannot simply be addressed by taking slightly larger parameters, because the error floor kicks in just after the block size $r = 12323$ chosen for BIKE 1. However, this error floor seems to be due a threshold function taking its minimum possible value $\frac{d+1}{2}$ for a very large range of values of the syndrome weight $s$. This can be addressed adequately by increasing this minimum threshold value from 36 to 39 in the case of BIKE 1. In this case, a threshold function with an adjusted gap leads to a DFR for the step-by-step decoder which is below $2^{-131.2}$ for a block size $r = 13477$. This is slightly less than a 10% increase of the current BIKE 1 parameter.

Analyzing a parallel decoder. There are reasons to believe [Vas21] that the parallel decoders used in the actual BIKE implementation produce an even lower DFR. Whereas up to now, only the beginning of the waterfall region could be explored for cryptographic parameters, this work opens a new road for exploring the ability of various decoders to attain even more efficiently the needed $2^{-\lambda}$ DFR and for understanding the effect of various weak keys on the DFR. Concerning the first point, it could be interesting to consider the approach followed in [ABP24a] (for the full version see [ABP24b]) to analyze parallel decoders.

## Acknowledgements

A. Mesnard and J.P. Tillich acknowledge the financial support of the French Agence Nationale de la Recherche through project ANR-22-PETQ-0008PQ-TLS. J. B. Lau acknowledges the financial support in part by the European Research Council under the European Union's Horizon 2020 research and innovation programme (ISOCRYPT - No. 101020788), by the Research Council KU Leuven grant (C14/24/099) and by CyberSecurity Research Flanders (VR20192203). The authors would like to thank the anonymous reviewers and Paolo Santini for fruitful comments and discussion.
References

ABB<sup>+21</sup>. Nicolas Aragon, Paulo Barreto, Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Santosh Ghosh, Shay Gueron, Tim Güneysu, Carlos Aguilar Melchor, Rafael Misoczki, Edoardo Persichetti, Jan Richter-Brockmann, Nicolas Sendrier, Jean-Pierre Tillich, Valentin Vasseur, and Gilles Zémor. BIKE: Bit flipping key encapsulation-spec v4.2. https://bikesuite.org/files/v4.2/BIKE_Spec.2021.07.26.1.pdf, 2021.

ABH<sup>+22</sup>. Sarah Arpin, Tyler Raven Billingsley, Daniel Rayor Hast, Jun Bo Lau, Ray A. Perlner, and Angela Robinson. A study of error floor behavior in QC-MDPC codes. In Jung Hee Cheon and Thomas Johansson, editors, *Post-Quantum Cryptography - 13th International Workshop, PQCrypto 2022, Virtual Event, September 28-30, 2022, Proceedings*, volume 13512 of *Lecture Notes in Computer Science*, pages 89–103. Springer, 2022.

ABP24a. Alessandro Annechini, Alessandro Barenghi, and Gerardo Pelosi. Bit-flipping decoder failure rate estimation for (v, w)-regular codes. In *Proc. IEEE Int. Symposium Inf. Theory - ISIT*, pages 3374–3379. IEEE, 2024.

ABP24b. Alessandro Annechini, Alessandro Barenghi, and Gerardo Pelosi. Bit-flipping decoder failure rate estimation for (v, w)-regular codes. *CoRR*, abs/2401.16919, 2024.

ALM<sup>+25</sup>. Sarah Arpin, Jun Bo Lau, Antoine Mesnard, Ray Perlner, Angela Robinson, Jean-Pierre Tillich, and Valentin Vasseur. Error floor prediction with markov models for QC-MDPC codes. Cryptology ePrint Archive, Paper 2025/153, 2025.

BBC<sup>+21</sup>. Marco Baldi, Alessandro Barenghi, Franco Chiaraluce, Gerardo Pelosi, and Paolo Santini. Performance bounds for QC-MDPC codes decoders. In Antonia Wachter-Zeh, Hannes Bartz, and Gianluigi Liva, editors, *Code-Based Cryptography - 9th International Workshop, CBCrypto 2021, Munich, Germany, June 21-22, 2021 Revised Selected Papers*, volume 13150 of *Lecture Notes in Computer Science*, pages 95–122. Springer, 2021.

DGK20. Nir Drucker, Shay Gueron, and Dusan Kostic. QC-MDPC decoders with several shades of gray. In Jintai Ding and Jean-Pierre Tillich, editors, *Post-Quantum Cryptography*, pages 35–50. Springer, Cham, 2020.

Gal63. Robert G. Gallager. *Low Density Parity Check Codes*. M.I.T. Press, Cambridge, Massachusetts, 1963.

GJS16. Qian Guo, Thomas Johansson, and Paul Stankovski. A key recovery attack on MDPC with CCA security using decoding errors. In Jung Hee Cheon and Tsuyoshi Takagi, editors, *Advances in Cryptology - ASIACRYPT 2016*, volume 10031 of LNCS, pages 789–815, 2016.

HB18. Yoones Hashemi and Amir H. Banihashemi. Characterization of elementary trapping sets in irregular LDPC codes and the corresponding efficient exhaustive search algorithms. *IEEE Trans. Inf. Theory*, 64(5):3411–3430, 2018.

HHK17. 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.

NSP<sup>+23</sup>. Mohammad Reza Nosouhi, Syed W. Shah, Lei Pan, Yevhen Zolotavkin, Ashish Nanda, Praveen Gauravaram, and Robin Doss. Weak-key analysis for BIKE post-quantum key encapsulation mechanism. *IEEE Trans. Inf. Forensics Secur.*, 18:2160–2174, 2023.
Ric03. Tom Richardson. Error floors of LDPC codes. In Proc. of the 41th Annual Allerton Conf. on Communication, Control, and Computing, volume 41, pages 1426-1435, 2003.

Sen24. Nicolas Sendrier. BIKE decoding failure - weak keys & error floors. Slides of the panel discussion of the fifth PQC standardization conference, April 2024.

SV19a. Nicolas Sendrier and Valentin Vasseur. About low DFR for QC-MDPC decoding. Cryptology ePrint Archive, Paper 2019/1434, 2019. https://eprint.iacr.org/2019/1434.

SV19b. Nicolas Sendrier and Valentin Vasseur. On the decoding failure rate of QC-MDPC bit-flipping decoders. In Jintai Ding and Rainer Steinwandt, editors, Post-Quantum Cryptography 2019, volume 11505 of LNCS, pages 404-416, Chongqing, China, May 2019. Springer.

Tan81. Robert Michael Tanner. A recursive approach to low complexity codes. IEEE Trans. Inform. Theory, 27(5):533-547, 1981.

Vas21. Valentin Vasseur. Post-quantum cryptography: a study of the decoding of QC-MDPC codes. PhD thesis, Université de Paris, March 2021.

Vas24. Valentin Vasseur. qcmdpc_markov Github codebase, 2024. Accessed: 2024-08-26.

VCN14. Bane Vasić, Shashi Kiran Chilappagari, and Dung Viet Nguyen. Chapter 6 - failures and error floors of iterative decoders. In David Declerq, Marc Fossorier, and Ezio Biglieri, editors, Academic Press Library in Mobile and Wireless Communications, pages 299-341. Academic Press, Oxford, 2014.

WWW23. Tianrui Wang, Anyu Wang, and Xiaoyun Wang. Exploring decryption failures of BIKE: New class of weak keys and key recovery attacks. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology - CRYPTO 2023, volume 14083 of LNCS, pages 70-100. Springer, 2023.