# Integer Syndrome Decoding in the Presence of Noise

Vlad Dragoi, Brice Colombier, Pierre-Louis Cayrel, Vincent Grosso

► To cite this version:

Vlad Dragoi, Brice Colombier, Pierre-Louis Cayrel, Vincent Grosso. Integer Syndrome Decoding in the Presence of Noise. Cryptography and Communications - Discrete Structures, Boolean Functions and Sequences, 2024, 16 (5), pp.1103-1134. 10.1007/s12095-024-00712-3. hal-04687281

HAL Id: hal-04687281

https://hal.science/hal-04687281v1

Submitted on 5 Sep 2024

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 Attribution 4.0 International License
Integer Syndrome Decoding in the Presence of
Noise

Vlad-Florin Drăgoi¹,²*†, Brice Colombier³†, Pierre-Louis Cayrel³†, Vincent Grosso³†

¹*Faculty of Exact Sciences, Aurel Vlaicu University of Arad, Romania.

²LITIS, University of Rouen Normandy, France.

³CNRS Laboratoire Hubert Curien UMR 5516, University of Lyon,
UJM-Saint-Etienne, Saint-Etienne, France.

*Corresponding author(s). E-mail(s): vlad.dragoi@uav.ro;

Contributing authors: b.colombier@univ-st-etienne.fr;

pierre.louis.cayrel@univ-st-etienne.fr; vincent.grosso@univ-st-etienne.fr;

†These authors contributed equally to this work.

**Abstract**

Code-based cryptography received attention after the NIST started the post-
quantum cryptography standardization process in 2016. A central NP-hard
problem is the binary syndrome decoding problem, on which the security of many
code-based cryptosystems lies. The best known methods to solve this problem all
stem from the information-set decoding strategy, first introduced by Prange in
1962. A recent line of work considers augmented versions of this strategy, with
hints typically provided by side-channel information. In this work, we consider
the integer syndrome decoding problem, where the integer syndrome is available
but might be noisy. We study how the performance of the decoder is affected by
the noise. We provide experimental results on cryptographic parameters for the
BIKE and *Classic McEliece* cryptosystems, which are both candidates for the
fourth round of the NIST standardization process.

**Keywords:** Code-based cryptography, Syndrome decoding problem, Information-set decoding
# 1 Introduction

## 1.1 Post-quantum cryptography: on its way to become reality

With the practical feasibility of a quantum computer of sufficient capacity getting more and more probable by the day, the threat posed by Shor's algorithm [38] on number theory base cryptosystems grows as well. To address this threat, NIST began a standardization process in 2016 for post-quantum cryptography. The fourth round of this process started in July 2022 when, in the Key Encapsulation Mechanism category, four candidates were submitted. Among them, the *Classic McEliece* [2] and the *BIKE* [3] cryptosystems are two solutions based on error-correcting codes. Their security relies on the NP-hardness of the binary syndrome decoding problem (SDP) [6]. The SDP is the core hard problem of several cryptographic constructions, e.g., the FSB hash function [4], the SYND stream cipher [25] or the Stern identification scheme [40].

Given a parity-check matrix $H$ of a binary linear code, a binary syndrome vector $s^*$ and an integer $t$, the SDP consists in finding a binary vector $x$ of Hamming weight $t$ such that $Hx = s^*$. There are three main techniques for solving the SDP: statistical decoding [24, 28, 36, 15, 12], information set decoding (ISD) [37, 30, 39, 31, 19, 20, 10, 23, 7, 33, 5, 34, 9] and generalized inverse based decoding [18]. Information Set Decoding was originally proposed by Prange in 1962 [37], and it has been incrementally refined since by Lee and Brickell [30], Stern [39] and, more recently, by May, Meurer and Thomae [33] and by Becker, Joux, May and Meurer [5]. The complexity of the ISD method has been used to better tune the parameters of the cryptosystems [21] according to the required security levels.

## 1.2 Integer syndrome decoding

One recent line of work considers modified versions of the SDP, for which additional information is available, for instance via side-channel analysis on implementations of the aforementioned cryptosystems. In [27], authors study the case where parts of the error are known, or only their Hamming weight. The case where the *integer* syndrome $s$ is available, instead of the binary one, as if the matrix-vector multiplication had been performed in the integer ring instead of the binary finite field, is considered in [17]. One method to obtain the integer syndrome is by laser fault injection attack, as presented in [13]. The problem one has to solve in this case is the integer syndrome decoding, referred to as $\mathbb{N}-\text{SDP}$, where the input is the parity-check matrix $H$, the integer syndrome vector $s$ and the weight of the solution $t$. The same question is raised, whether $Hx = s$ admits a solution of weight $t$. This problem can be tackled down by means of Integer Linear Programming [13] or probabilistic methods [22].

Another method of obtaining an integer syndrome, much more feasible and realistic than laser fault injection, is by side-channel analysis [14]. However, due to physical factors, the integer entries of the syndrome might not be perfectly accurate. Hence, in the resulting problem, the $\mathbb{N}-\text{SDP}$ in the presence of noise, we are given a noisy integer syndrome $\tilde{s} = s + \epsilon$, where $\epsilon$ models the noise as a vector of random variables. The solution proposed in [14] uses a combination of ISD techniques and the score
decoder from [22]. However, only simulations were provided to assess the performance
of this proposal and no theoretical evidence was given.

1.3 Related work

Learning with errors and hints

Not only code-based cryptosystems are vulnerable to such attacks. Similar results
were obtained in the context of lattice-based cryptosystems by Bootle et al. [8]. The
BLISS cryptosystem was cryptanalysed by means of similar hybrid attacks, where
side-channel attacks revealed an Integer version of the Learning With Errors (ILWE).
The ILWE problem is the lattice-based equivalent of the $N$-SDP. However, ILWE was
solved with another technique that does not seem to work for $N$-SDP. Nevertheless,
it points out that such scenarios extend broader than code-based cryptography.

Quantitative Group Testing

Quantitative Group Testing (QGT) is an active field of research, lately boosted by the
COVID-19 epidemic. In the QGT we are given a large population out of which some
individuals suffer from a disease, and the goal is to identify the infected individuals.
Possible applications of QGT go from bio-informatics [11], traffic monitoring [42] and
confidential data transfer [16, 1] to machine learning [32, 43]. The $N$ - SDP can be
also seen as a QGT in presence of noise. As we shall demonstrate, the algorithm we
propose here, solves a noisy QGT instance, by adapting and improving (using coding
theory tools, such as ISD techniques) a recent solution to the classical QGT [22].

1.4 Contributions

In this article, we analyze in detail the algorithm proposed in [14], referred to as ISD-
score decoder, and provide the following contributions. First, we demonstrate that the
ISD-score decoder finds a solution to the $N$ – SDP in the presence of noise with high
probability, as long as the weight is sub-linear in $n$, more exactly, $t \le O\left(\frac{n-k}{\log(n-k)}\right)$,
where $n$ is the length of the code and $k$ the dimension. We consider two noise models,
present in several schemes/scenarios, i.e., Binomial centered in zero and Bernoulli
variables. We demonstrate that the ISD-score decoder can tolerate noise levels that
are linear in the weight of the solution $t$. For that we partially build our demonstration
on the techniques used in [22]. We incorporate the noise models into these techniques
and, by using sharper inequalities, determine a much clearer condition for having a
higher probability of success. One consequence of this new method is that when the
noise is null and the ISD part is ignored, equivalently the ISD-score decoder boils
down to the algorithm proposed in [22], the conditions we propose on the range of
$t$ for which the algorithm succeeds is larger than those from [22]. This gives a lower
bound on the number of syndrome entries, or the number of rows in the parity-check
matrix, required to find a solution, known as the information theoretic bound. A 5
page short version of this article was presented at the Information Theory Workshop
(ITW) 2022. We are extending on this short version by providing the full proofs of
our results additional comments and a complete section on experimental results.
## Outline of the article

In Section 2 we introduce the SDP and its variants, $\mathbb{N}-\text{SDP}$ and $\mathbb{N}-\text{SDP}$ in the presence of noise. We also recall the cryptographic context where these problems occur. Section 3 begins by recalling the score decoder proposed in [14]. Then, it analyzes the distribution of the discriminant function for the $\mathbb{N}-\text{SDP}$ in the presence of noise. The section ends with the description of the ISD-Score decoder. Next, we analyze the success probability of the ISD-Score decoder in Section 4. The theoretical results from this part are being compared with numerical values from our implementation of the algorithm in Section 5. The section also makes a parallel between the efficiency of the ISD-Score decoder and other methods such as ILP. Finally, we conclude the article in Section 6.

# 2 Preliminaries

## Notations

A finite field is denoted by $\mathbb{F}$, and the ring of integers by $\mathbb{Z}$. We write $\mathbb{N}_n^* = \{1, \dots, n\}$ and $\mathbb{Z}_{-n,n} = \{-n, \dots, 0, \dots, n\}$. For $p \in [0, 1]$ and $n \in \mathbb{N}^*$ a random variable $X$ that follows a distribution will be marked as $X \sim \text{Ber}(p)$ for the Bernoulli distribution and by $X \sim \mathcal{B}(n, p)$ for the Binomial distribution. We denote by $W(x)$ the Lambert W function. Matrices and vectors are written in bold capital, respectively small letters. We also use $\text{HW}(c)$ to denote the Hamming weight of the vector $c$.

## Error correcting codes

Let $n$ and $k$ be two positive integers such that $k \le n$. An $[n, k]$ linear code can be defined as a sub-vector space of dimension $k$ of the vector space $\mathbb{F}^n$. A code can be specified either by its generator matrix $G \in \mathbb{F}^{k \times n}$ (a basis for the code), or by its parity-check matrix $H \in \mathbb{F}^{(n-k) \times n}$ (a basis for the dual code). The minimum distance, or the Hamming distance of a code $C$, is the minimum of all $\text{HW}(v)$ for $v \in C, v \ne 0$.

One of the main features of linear codes is their ability to decode noisy information/data. Several general decoding strategies exist, the syndrome decoding problem being one of them.

## Some variations of the syndrome decoding problem

Let us start by formally defining the binary SDP.

### Definition 1 (SDP).

*Inputs:* $H \in \mathbb{F}_2^{(n-k) \times n}$, $s^* \in \mathbb{F}_2^{n-k}$, $t \in \mathbb{N}^*$.

*Output:* $x \in \mathbb{F}_2^n$ s.t. $Hx = s^*$, and $\text{HW}(x) = t$.

This problem is NP-Complete [6] and, as we shall quickly see, it constitutes the building block of code-based solution for post-quantum cryptography.

Now, a slightly different problem, the $\mathbb{N}-\text{SDP}$ [13, 17], considers matrix-vector multiplication over the ring of integers instead of the binary field $\mathbb{F}_2$. Formally, the problem can be stated as follows.
**Definition 2** ($\mathbb{N}$-SDP).

**Inputs:** $H \in \{0, 1\}^{(n-k) \times n}$, $s \in \mathbb{N}^{n-k}$, $t \in \mathbb{N}^*$.

**Output:** $x \in \{0, 1\}^n$, s.t. $Hx = s$, and $HW(x) = t$.

To define $\mathbb{N}$-SDP in the presence of noise as generally as possible, we model the noise $\epsilon = (\epsilon_1, \dots, \epsilon_{n-k})$ as a vector of random variables $\epsilon_i \sim D$, where $D$ is a discrete probability distribution. In the $\mathbb{N}$-SDP in the presence of noise, instead of having access to an instance of the $\mathbb{N}$-SDP, i.e., $(H, s, t)$, we are given a noisy syndrome $\tilde{s} = s + \epsilon$ and the value $s^* = s \pmod{2}$ (component-wise).

**Definition 3** ($\mathbb{N}$-SDP in the presence of noise $\epsilon$).

**Inputs:** $H \in \{0, 1\}^{(n-k) \times n}$, $\tilde{s} \in \mathbb{Z}^{n-k}$

$$s^* \in \{0, 1\}^{n-k}, t \in \mathbb{N}^*$$

**Output:** $x \in \{0, 1\}^n$, s.t. $Hx = s^*$ with $HW(x) = t$

$$s^* = s \pmod{2}, \text{ and } \tilde{s} = s + \epsilon.$$

Remark that $\mathbb{N}$-SDP in presence of noise is the SDP with additional information. Under certain conditions, we hope that, given $(H, s^*, t, \tilde{s})$, we can find $x$, solution to the SDP. Also, when the noise is zero we face the classic $\mathbb{N}$-SDP.

### The Niederreiter encryption framework

Both, *Classic McEliece* [2] and *BIKE* [3], are based on the Niederreiter encryption scheme [35]. Here, we will focus on the encryption algorithm (see Alg. 1).

<table><thead><tr><th colspan="2">Algorithm 1 Niederreiter encryption</th></tr></thead><tbody><tr><td>1:</td><td>function ENCRYPT(m, pk)</td></tr><tr><td>2:</td><td>Encode m → x with HW(x) = t</td></tr><tr><td>3:</td><td>Compute s* = H<sub>pub</sub>x</td></tr><tr><td>4:</td><td>return s*</td></tr></tbody></table>

Recent message recovery attacks are pointing the encryption step, where the cipher-text is obtained from the multiplication of the public parity-check matrix $H_{pub}$ and the secret error vector $x$. Hence, in [14, 13] the matrix-vector multiplication is targeted as leakage point (line 3 in Algorithm 1). We shall not insist here on the technical details that allow the derivation of the integer syndrome $s$ or the noisy integer syndrome $\tilde{s}$ from this matrix-vector computation. However, such an exploit is achievable, hence, enabling one to tackle the $\mathbb{N}$-SDP or the $\mathbb{N}$-SDP in presence of noise, in order to retrieve the secret message. The sets of $(n, k, t)$ parameters defined in [2] and [3] are given in Table 1.

# 3 ISD-Score decoder

## 3.1 Score decoder

The idea of assigning a score to each column was already used in for the $\mathbb{N}$-SDP in [14]. The objective is to distinguish columns of $H$ in the support of the solution vector from columns which are outside the support. We shall begin by defining a score decoder, as introduced in [22], that proved to be particularly discriminant in the
<table><caption>**Table 1:** $(n, k, t)$ parameters for *Clas-sic McEliece* and *BIKE*</caption><thead><tr><th></th><th>n</th><th>k</th><th>t</th></tr></thead><tbody><tr><td rowspan="4">Classic McEliece</td><td>3488</td><td>2720</td><td>64</td></tr><tr><td>4608</td><td>3360</td><td>96</td></tr><tr><td>6688</td><td>5024</td><td>128</td></tr><tr><td>8192</td><td>6528</td><td>128</td></tr><tr><td rowspan="3">BIKE</td><td>24646</td><td>12323</td><td>134</td></tr><tr><td>49318</td><td>24659</td><td>199</td></tr><tr><td>81946</td><td>40973</td><td>264</td></tr></tbody></table>

context of $\mathbb{N} - \text{SDP}$. For a better illustration of the nice features of the decoder in the presence of noise, we will express it in function of the noiseless decoder. As we shall see, this method allows not only to derive a particularly simple relation between those two, but also to deduce conditions on the tolerated noise level.

**Definition 4.** Let $\mathbf{H} \in \{0, 1\}^{(n-k) \times n}$, $\mathbf{s} \in \mathbb{N}^{n-k}$ and $t \in \mathbb{Z}^*$ be the input of $\mathbb{N} - \text{SDP}$. Then define the score of a column:

$$ \forall i \in \mathbb{N}_n^* \quad \psi_i(\mathbf{s}) = \sum_{\ell=1}^{n-k} (h_{\ell,i} \mathbf{s}_{\ell} + (1 - h_{\ell,i})(t - \mathbf{s}_{\ell})). \quad (1) $$

For the $\mathbb{N} - \text{SDP}$ in the presence of noise we shall use $\psi_i(\tilde{\mathbf{s}})$. The next result, rephrased from [22], expresses the capability of the score decoder to distinguish between columns in the support of the solution vector from columns which are outside the support.

**Theorem 1.** Let $\mathbf{H} \in \{0, 1\}^{(n-k) \times n}$ be a random matrix, with distribution given by $h_{j,i} \sim \text{Ber}(\frac{1}{2})$ and $\mathbf{s} \in \mathbb{N}^{n-k}$ such that $\exists \mathbf{x} \in \{0, 1\}^n$ with $\text{HW}(\mathbf{x}) = t$ satisfying $\mathbf{H}\mathbf{x} = \mathbf{s}$. Then

$$ \psi_i(\mathbf{s}) \sim \begin{cases} \mathcal{B}((n-k)t, \frac{1}{2}) & , i \notin \text{Supp}(\mathbf{x}) \\ \mathcal{B}((n-k)(t-1), \frac{1}{2}) + n - k & , i \in \text{Supp}(\mathbf{x}) \end{cases} $$

Straightforward from Theorem 1 we have $\mathbb{E}(\psi_i(\mathbf{s})) = (n-k)t/2$ for $i \notin \text{Supp}(\mathbf{x})$ and $\mathbb{E}(\psi_i(\mathbf{s})) = (n-k)t/2 + (n-k)/2$ for $i \in \text{Supp}(\mathbf{x})$. The difference in the average value points out that $\psi$ can be a distinguisher between positions in the support and outside the support of the vector $\mathbf{x}$. In addition, the variance also differs, fact that will be used in the tail bounds. Moving forward, we will consider the noisy version of this problem in the next section.

## 3.2 Score decoder in the presence of noise

As in [14], we make some assumptions on the noise considered here, i.e., $\epsilon_i$ are independent and identically distributed random variables, the noise does not depend on the distribution of the entries in $\mathbf{H}$ and the distribution $\mathcal{D}$ is symmetric.
<figure><img src="image_2.png" /><figcaption>(a) Example parameters set of BIKE</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>(b) Example parameters set of Classic McEliece</figcaption></figure>

Fig. 1: Distribution of $\psi_i$ for $\epsilon \sim -d + \mathcal{B}(2d, \frac{1}{2})$

**Proposition 2** ([14]). For $j \in \mathbb{Z}_{n-k}^*$ let $\epsilon_j$ be i.i.d. discrete random variables following a symmetric distribution over the set $\mathbb{Z}_{-d,d}$, s.t. $\epsilon_j$ and $h_{i,j}$ are independent. Then

$$ \mathrm{Prob}(\psi_i(\tilde{s}) - \psi_i(s) = \alpha) = \mathrm{Prob}\left(\sum_{j=1}^{n-k} \epsilon_j = \alpha\right). $$

*Proof.* Let $Y_{\ell,i} = (2h_{\ell,i} - 1)\epsilon_{\ell}$. Then we have,

$$ \begin{aligned} \psi_i(\tilde{s}) &= \sum_{\ell=1}^{n-k} (h_{\ell,i}(\tilde{s}_{\ell} + (1-h_{\ell,i})(t-\tilde{s}_{\ell}))) \\ &= \sum_{\ell=1}^{n-k} (h_{\ell,i}(s_{\ell} + \epsilon_{\ell} + (1-h_{\ell,i})(t-s_{\ell}-\epsilon_{\ell}))) \\ \psi_i(\tilde{s}) &= \psi_i(s) + \sum_{\ell=1}^{n-k} \underbrace{(h_{\ell,i}\epsilon_{\ell} - (1-h_{\ell,i})\epsilon_{\ell})}_{Y_{\ell,i}} \end{aligned} $$

For any fixed value of $\ell \in \mathbb{Z}_{n-k}^*$ we have $\mathrm{Prob}(Y_{\ell,i} = \alpha_{\ell}) = \mathrm{Prob}(\epsilon_{\ell} = \alpha_{\ell})$ for any $\alpha_{\ell} \in \mathbb{Z}_{-d,d}$ (using the symmetry property and the independence of $h_{\ell,i}$ and $\epsilon_{\ell}$). Hence $Y_{\ell,i}$ follows the same distribution as $\epsilon_{\ell}$. Thus, $\psi_i(\tilde{s}) - \psi_i(s) \in \mathbb{Z}_{-(n-k)d,(n-k)d}$ with probability distribution $\mathrm{Prob}(\psi_i(\tilde{s}) - \psi_i(s) = \alpha) = \mathrm{Prob}\left(\sum_{j=1}^{n-k} \epsilon_j = \alpha\right)$. $\square$
Keeping the difference $\psi_i(\tilde{s}) - \psi_i(s)$ as small as possible resumes to controlling the sum of $\epsilon_j$. The variance of $\epsilon_j$ plays a crucial role in the distinguishing capacity of $\psi$. **Proposition 3.** For any $j \in \mathbb{Z}_{n-k}^*$ let $\epsilon_j$ be a discrete random variable satisfying the conditions from Proposition 2 and let $\sigma^2 = \text{Var}(\epsilon_j)$. Let $g(n, k, t)$ be a function in the parameters of $\mathbb{N} - \text{SDP}$. Then for any $\alpha > \sigma\sqrt{(n-k)g(n, k, t)}$

$$ \text{Prob}(\psi_i(\tilde{s}) - \psi_i(s) \geq \alpha) \leq \frac{1}{g(n, k, t)}. \qquad (2) $$

*Proof.* Use Chebyshev inequality for the sum of $\epsilon_j$ and the linearity of the variance. $\square$

### The case of centered binomial noise

**Corollary 4.** Let $d \in \mathbb{N}$ and $\epsilon_i \sim -d + \mathcal{B}(2d, \frac{1}{2})$. Then

* for $i \notin \text{Supp}(x)$

$$ \psi_i(\tilde{s}) \sim -d(n-k) + \mathcal{B}\left((n-k)(t+2d), \frac{1}{2}\right) $$

* for $i \in \text{Supp}(x)$

$$ \psi_i(\tilde{s}) \sim -(d-1)(n-k) + \mathcal{B}\left((n-k)(t-1+2d), \frac{1}{2}\right) $$

Moreover, $\mathbb{E}(\psi_i(\tilde{s})) = \mathbb{E}(\psi_i(s))$ and $\text{Var}(\psi_i(\tilde{s})) = \text{Var}(\psi_i(s)) + (n-k)d/2$.

To maintain the capability to distinguish between positions inside the support and positions outside the support, the noise parameter $d$ from $\mathcal{B}(2d, \frac{1}{2})$ should be restricted. **Corollary 5.** Let $\epsilon_i \sim -d + \mathcal{B}(2d, \frac{1}{2})$ and $g(n, k, t)$ a unbounded function in $t, n, k$.

Then w.h.p. we have $|\psi_i(\tilde{s}) - \psi_i(s)| \le \sqrt{\frac{d(n-k)g(n,k,t)}{2}}$. Moreover, for any $d \le \frac{n-k}{8g(n,k,t)}$, the function $\psi(\tilde{s})$ distinguishes positions in $\text{Supp}(x)$ from positions outside $\text{Supp}(x)$.

In particular, we can put $g(n, k, t) = \log \log t$ or $g(n, k, t) = \log \log n$ depending on the wanted speed of convergence.

Figure 1 shows the distribution of $\psi_i$ values for different levels of noise, ranging from $d = 0$, i.e. the noiseless setting, to a very high noise of $\mathcal{B}(2t, \frac{1}{2})$. Notice that the distinguishing capability is much higher for the BIKE parameters, as shown in Figure 1a, than for the *Classic McEliece* parameters, as shown in Figure 1b.

### Bernoulli noise

**Proposition 6.** Let $\epsilon_i \sim \text{Ber}(\{0, 1\}, 1/2)$. Then $\psi_i(\tilde{s})$ is a random variable that follows the distribution $$ \begin{cases} \mathcal{B}((n-k)(t+2), \frac{1}{2}) - (n-k), & i \notin \text{Supp}(x) \\ \mathcal{B}((n-k)(t+1), \frac{1}{2}) & , i \in \text{Supp}(x) \end{cases} $$. Moreover, $\mathbb{E}(\psi_i(\tilde{s})) = \mathbb{E}(\psi_i(s))$ and $\text{Var}(\psi_i(\tilde{s})) = \text{Var}(\psi_i(s)) + (n-k)/2$.
Notice that, in the case of a Bernoulli type of noise, the behavior is equivalent to the case of a centered binomial noise. (equivalent to $d = 1$ in Corollary 4). Indeed, the result in Proposition 6 is equivalent to the one given in Corollary 4 with $d = 1$.

### 3.3 Combining ISD and score decoder

The idea in [14] was to boost the distinguishing capability of the score decoder with ISD-like techniques. To this end, the score decoder is integrated in the “permutation” step of the ISD method. Indeed, this method starts by performing a permutation on the columns of $\mathbf{H}$ that will hopefully rearrange the solution in a useful way. More precisely, in the first ISD algorithm, the Prange decoder [37], a “good” permutation ($\mathbf{\Pi}$) is one that satisfies $\mathbf{\Pi}^{-1}\mathbf{x} = \begin{pmatrix} \mathbf{x}_1 \\ 0 \end{pmatrix}$. Hence, the initial system becomes $\mathbf{H}\mathbf{\Pi}\mathbf{\Pi}^{-1}\mathbf{x} = \mathbf{s}^*$. By Gaussian elimination on $\mathbf{H}\mathbf{\Pi}$ one can find an invertible matrix $\mathbf{A}$ s.t. $\mathbf{A}\mathbf{H}\mathbf{\Pi} = (\mathbf{I}\|\mathbf{B})$. Hence, the system becomes $(\mathbf{I}\|\mathbf{B})\begin{pmatrix} \mathbf{x}_1 \\ 0 \end{pmatrix} = \mathbf{A}\mathbf{s}^*$ which yields $\mathbf{x}_1 = \mathbf{A}\mathbf{s}^*$. In the original ISD methods, permutations are sampled randomly until a “good” one is obtained. Thanks to the extra-information provided by $\mathbf{s}$ or $\tilde{\mathbf{s}}$, the function $\psi$ allows to construct a permutation which by no means is random. Indeed, we have seen that $\psi$, by its nature, allows one to distinguish between positions in the support of $\mathbf{x}$ and positions outside. Hence, the underlying permutation, hopefully is a “good” permutation. As pointed out in [14], sorting the list of values $\psi_i(\tilde{\mathbf{s}})$ in descending order is equivalent to generating a permutation $\mathbf{\Pi}$. Algorithm 2 finds a solution to the $\mathbb{N}-\text{SDP}$ in the presence of noise as long as $\mathbf{\Pi}$ is “good” enough.

<caption>**Algorithm 2 PRANGE SCORE DECODER($\mathbf{H}$, $\mathbf{s}$, $t$)**</caption>

1. Compute $\mathbf{\Pi}$ from the list $\psi_i(\tilde{\mathbf{s}})$

2. Compute $\mathbf{A}^*, \mathbf{H}^* \leftarrow \text{rref}(\mathbf{H}\mathbf{\Pi})$

3. **if** HW($\mathbf{A}^*\mathbf{s}^*) = t$ **then**

4. return $\mathbf{x} = \mathbf{\Pi} \begin{pmatrix} \mathbf{A}^*\mathbf{s}^* \\ \mathbf{0}_{n-r} \end{pmatrix}$ ▷ $r = \text{rank}(\mathbf{A})$

The procedure rref($\mathbf{H}\mathbf{\Pi}$), which stands for “reduced row echelon form”, is equivalent to performing a partial Gaussian elimination over $\mathbb{F}_2$. Indeed, there is an $(n-k) \times (n-k)$ non-singular matrix $\mathbf{A}^*$ such that, $\mathbf{A}^*\mathbf{H}\mathbf{\Pi} = \begin{bmatrix} \mathbf{I}_r & \|\mathbf{B}^* \\ \mathbf{0}_{n-k-r,r} & \|\mathbf{B}^* \end{bmatrix}$ where $\mathbf{H}\mathbf{\Pi} = [\mathbf{A} \| \mathbf{B}]$ with $\mathbf{A}$ a $(n-k) \times r$ matrix satisfying $\mathbf{A}^*\mathbf{A} = \begin{bmatrix} \mathbf{I}_r \\ \mathbf{0}_{n-k-r,r} \end{bmatrix}$, and $\mathbf{B}^* = \mathbf{A}^*\mathbf{B}$. In the case of a full rank matrix $\mathbf{A}$ we have $\mathbf{A}^*\mathbf{A} = \mathbf{I}_{n-k}$. From the description of the algorithm above, the following result can be deduced.

**Proposition 7** ([14]). PRANGE SCORE DECODER outputs a valid solution as long as there exists at least one set $L \subset \mathbb{N}_n^* \setminus \text{Supp}(\mathbf{x})$ with $\#L \ge n-r$ such that $\min\{\psi_i(\tilde{\mathbf{s}}), i \in \text{Supp}(\mathbf{x})\} > \max\{\psi_i(\tilde{\mathbf{x}}), i \in L\}$.
The overall time complexity of PRANGE SCORE DECODER is $O((n-k)^3)$, since it is dominated by the partial Gaussian elimination, i.e. the computation of $A^*$.

Since the permutation $\Pi$ might not move all the positions in the support of $x$ in the first $n-k$ positions, more powerful ISD methods may be used, e.g. Lee-Brickell [30], Stern [39] or Dumer [19]. The idea is to allow a number of $\delta$ positions from $\text{Supp}(x)$ outside the first $n-k$ positions. This is equivalent to extending PRANGE SCORE DECODER so that it covers error vectors with a more general pattern. The Lee-Brickell score decoder, where $\delta$ positions are searched exhaustively, is thus proposed in [14] as a possible solution.

<caption>**Algorithm 3** Lee-Brickell Score Decoder ([14])</caption>

1: **function** LEE-BRICKELL SCORE DECODER($H, \tilde{s}, s^*, t$)
2: Compute $\Pi \leftarrow \text{SORT}(H, \tilde{s}, t)$
3: Set $H\Pi = [A \parallel B]$
4: Compute $A^*, H^* \leftarrow \text{rref}(H\Pi)$ and $B^* = A^*B$
5: Compute $s' = A^*s^*$
6: **if** HW($s'$) == $t$ **then**
7: **return** $x = \Pi(s' \parallel 0_k)^t$
8: **else**
9: **for** $i \leftarrow 1, \delta$ **do**
10: &nbsp;&nbsp;&nbsp;&nbsp; $S = \text{Gener-Subsets}\{\{1, \dots, k\}, i\}$
11: &nbsp;&nbsp;&nbsp;&nbsp; **for** $E$ in $S$ **do**
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $x'' \leftarrow \text{Vector}(\{0, 1\}, k, E)$
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $x' \leftarrow s' - B^*x''$
14: &nbsp;&nbsp;&nbsp;&nbsp; **if** HW($x'$) == $t-i$ **then**
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **return** $(\Pi(x' \parallel x'')^t, \Pi)$

When the Lee-Brickell variant is used and $\delta = O(1)$, $k = O(n)$, the work factor of the resulting algorithm becomes polynomial in $n$.

**Proposition 8.** The $\delta$-ISD-score decoder outputs a valid solution as long as there are at most $\delta$ indices $i \in \text{Supp}(x)$ with values $\psi_i(\tilde{s}) < \psi_j(\tilde{s})$ with $j$ in a set $J \subset \mathbb{N}_n$ of cardinality $n-k$.

# 4 Success probability of the ISD-Score decoder

## 4.1 Main results

The following result gives a condition on the parameters for having a high probability of success for the ISD score decoder on the $\mathbb{N} - \text{SDP}$ in presence of noise.

**Theorem 9.** Let $\epsilon_i \sim -d + \mathcal{B}(2d, \frac{1}{2})$. If the interval $[\sqrt{\frac{t+2d}{n-k}} W(\frac{n-t}{n-k-t+\delta+1} \frac{e\sqrt{2}}{\pi})^2, 1 - \sqrt{\frac{t+2d-1}{n-k}} W(\frac{t}{\delta+1} \frac{2e}{\pi})^2]$ is non-empty, then w.h.p. the ISD-score decoder succeeds in finding a valid solution.
To prove this theorem we shall use 3 steps. More precisely, we first give an estimation on the tails of the distributions $\psi_i(\tilde{s})$, then we insert these results into a generic upper bound on the probability of success of the ISD-score decoder, and finally we study the range of parameters for which our conditions are valid.

### 4.1.1 Tail bounds on the distribution

Firstly we have the following result on the distribution of $\psi$ in the noiseless scenario.

**Theorem 10.** Let $\beta \in (0, 1)$ and $B_{\beta} = \frac{(n-k)t}{2} + \frac{\beta(n-k)}{2}$. Then we have for $i \notin \text{Supp}(\boldsymbol{x})$

$$ \text{Prob}(\psi_i(\boldsymbol{s}) \ge B_{\beta}) \le \frac{e}{\sqrt{2\pi}\beta} \sqrt{\frac{t}{n-k}} e^{-\frac{n-k}{2t}\beta^2}, \quad (3) $$

for $i \in \text{Supp}(\boldsymbol{x})$

$$ \text{Prob}(\psi_i(\boldsymbol{s}) \le B_{\beta}) \le \frac{e}{\pi(1-\beta)} \sqrt{\frac{t-1}{n-k}} e^{-\frac{n-k}{2(t-1)}(1-\beta)^2}. \quad (4) $$

Moving forward, in the case of a binomial noise we have

**Theorem 11.** Let $\epsilon_i \sim -d + B(2d, \frac{1}{2})$, $\beta \in (0, 1)$ and $B_{\beta}$ as previously defined. Then we have for $i \notin \text{Supp}(\boldsymbol{x})$

$$ \text{Prob}(\psi_i(\tilde{s}) \ge B_{\beta}) \le \frac{e}{\sqrt{2\pi}\beta} \sqrt{\frac{t+2d}{n-k}} e^{-\frac{(n-k)\beta^2}{2(t+2d)}}, \quad (5) $$

for $i \in \text{Supp}(\boldsymbol{x})$

$$ \text{Prob}(\psi_i(\tilde{s}) \le B_{\beta}) \le \frac{e}{\pi(1-\beta)} \sqrt{\frac{t+2d-1}{n-k}} e^{-\frac{(n-k)(1-\beta)^2}{2(t+2d-1)}}. \quad (6) $$

The proof of these theorems is given in Appendix. Let us denote the two upper bounds in Theorem 11 by $\text{Ub}_{\text{Supp}(\boldsymbol{x})}(n, k, t, \beta)$ and $\text{Ub}_{\text{Supp}(\boldsymbol{x})}^c(n, k, t, \beta)$.

### 4.1.2 A general bound on the success probability using tail estimations

A general theorem regarding the success probability of ISD-score decoder can be stated. For that we suppose that the distribution $\psi_i(\tilde{s})$ when $i \in \text{Supp}(\boldsymbol{x})$ has to be different from $\psi_i(\tilde{s})$ when $i \notin \text{Supp}(\boldsymbol{x})$, e.g., it is at least shifted. If not it is obvious that ISD-score decoder can not retrieve a valid solution with high probability.

**Theorem 12.** Let $\psi_i(\tilde{s})$ be random variables and $f(n, k, t, d, B)$, $g(n, k, t, d, B)$ be two functions s.t.

$$ \text{Prob}(\psi_i(\tilde{s}) \le B) \le e^{-f(n,k,t,d,B)}, \quad i \in \text{Supp}(\boldsymbol{x}) \quad (7) $$
$$ \mathrm{Prob}(\psi_i(\tilde{s}) \ge B) \le e^{-g(n,k,t,d,B)}, \quad i \notin \mathrm{Supp}(\boldsymbol{x}) \qquad (8) $$

The ISD-score decoder finds the solution if $\exists B^*$ s.t.

* $0 \le 1 - \frac{t}{\delta+1}e^{-f(n,k,t,d,B^*)} \le 1,$

* $0 \le 1 - \frac{n-t}{n-k-t+\delta+1}e^{-g(n,k,t,d,B^*)} \le 1,$

* $\frac{t}{\delta+1}e^{-f(n,k,t,d,B^*)} + \frac{n-t}{n-k-t+\delta+1}e^{-g(n,k,t,d,B^*)}$ is close to zero,

Typically, the theorem gives a sufficient condition for having a high probability of success. Indeed, if one finds a value $B_\beta$ for which the lower bound tends to 1 then the Score function achieves its goal, namely to distinguish positions in the support of $\boldsymbol{x}$ from those outside it. The proof of this result is given in the Appendix.

Combining the tail bounds on the distribution of $\psi_i(\tilde{s})$ with the condition on $\beta^*$ for having a high probability of success enables the following result. Denote

$$ \mathrm{Lb}_{\mathrm{Supp}(\boldsymbol{x})}^c = 1 - \frac{e(n-t)}{\sqrt{2\pi\beta(n-k-t+\delta+1)}} \sqrt{\frac{t+2d}{n-k}} e^{-\frac{(n-k)\beta^2}{2(t+2d)}}, \quad \mathrm{Lb}_{\mathrm{Supp}(\boldsymbol{x})} = 1 - \frac{e.t}{\pi(1-\beta)(\delta+1)} \sqrt{\frac{t+2d-1}{n-k}} e^{-\frac{(n-k)(1-\beta)^2}{2(t+2d-1)}}. $$

**Proposition 13.** Let $\epsilon_i \sim -d + \mathcal{B}(2d, \frac{1}{2})$. If $\exists \beta^* \in (0, 1)$ s.t. $\mathrm{Lb}_{\mathrm{Supp}(\boldsymbol{x})}$, $\mathrm{Lb}_{\mathrm{Supp}(\boldsymbol{x})}^c \in [0, 1]$ and $\mathrm{Lb}_{\mathrm{Supp}(\boldsymbol{x})}\mathrm{Lb}_{\mathrm{Supp}(\boldsymbol{x})}^c$ is close to 1, then w.h.p. ISD-score decoder succeeds in finding a valid solution.

**Corollary 14.** When $d=0$ and $\delta=0$ the condition on $\beta^*$ simplifies to

* $0 \le \frac{et}{\pi(1-\beta)}\sqrt{\frac{t}{n-k}}e^{-\frac{(n-k)(1-\beta)^2}{2t}} \le 1,$

* $0 \le \frac{e(n-t)}{(\sqrt{2\pi\beta})(n-k-t)}\sqrt{\frac{t}{n-k}}e^{-\frac{(n-k)\beta^2}{2t}} \le 1,$

* $\frac{et}{\pi(1-\beta)}\sqrt{\frac{t}{n-k}}e^{-\frac{(n-k)(1-\beta)^2}{2t}} + \frac{e(n-t)}{(\sqrt{2\pi\beta})(n-k-t)}\sqrt{\frac{t}{n-k}}e^{-\frac{(n-k)\beta^2}{2t}}$ is close to zero,

To fairly compare with state-of-the-art techniques such as the algorithm in [22], which is only valid for the noiseless scenario, we adapted the conditions from [22] to the noise model considered here. This gives two similar functions in $\beta$, namely $1 - \frac{n-t}{n-k-t}\sqrt{\frac{t+2d}{n-k}}e^{-\frac{(n-k)\beta^2}{2(t+2d)}}$, and $1 - t\sqrt{\frac{t+2d-1}{n-k}}e^{-\frac{(n-k)(1-\beta)^2}{2(t+2d-1)}}$. In Figure 2, we plot the modified functions from [22] (dashed lines) and $\mathrm{Lb}_{\mathrm{Supp}(\boldsymbol{x})}$, $\mathrm{Lb}_{\mathrm{Supp}(\boldsymbol{x})}^c$ (solid lines).

In dark green and light green, the valid interval/region for the adapted functions from [22], and our functions, respectively, are represented. Notice that for all parameter sets and all noise levels considered here, our function offers a larger interval. Hence, this implies that for some sets of parameters, e.g., in Figure 2d, the interval is empty w.r.t. conditions in [22], while w.r.t. our conditions the interval exists.

### 4.1.3 Range of valid parameters

Here, we shall determine the conditions on the parameters such that the conditions in Proposition 13 are satisfied. We will begin by determining the existence of $\beta^*$. We will need to denote by $W(\boldsymbol{x})$ the Lambert W function.
<figure><img src="image_4.png" /><figcaption>(a) $n = 24646, d = 0, \delta = 0$</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(b) $n = 24646, d = t, \delta = 0$</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(c) $n = 24646, d = t, \delta = 3$</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(d) $n = 3488, d = t, \delta = 3$</figcaption></figure>

<caption>**Fig. 2:** Valid $\beta$ interval from the bounds in [22] (dashed lines) and the proposed ones (solid lines)</caption>

**Proposition 15.** For any $\beta \ge \sqrt{\frac{t+2d}{n-k}}W\left(\frac{n-t}{n-k-t+\delta+1}\frac{e}{\sqrt{2\pi}}\right)^2$ we have that $\frac{n-t}{n-k-t+\delta+1}\text{Ub}_{\text{Supp}(x)}(n,k,t,d,\beta) \le 1$, and for any $\beta \le 1 - \sqrt{\frac{t+2d-1}{n-k}}W\left(\frac{t}{\delta+1}\frac{e}{\pi}\right)^2$ we have that $\frac{t}{\delta+1}\text{Ub}_{\text{Supp}(x)}(n,k,t,d,\beta) \le 1$.

Having both functions positive and strictly smaller than 1, at the same time, can be achieved as long the interval defined by the two extreme points, in the previous Proposition is non-empty, i.e.,

$$ \sqrt{\frac{t+2d}{n-k}}W\left(\frac{n-t}{n-k-t+\delta+1}\frac{e}{\sqrt{2\pi}}\right)^2 \le 1 - \sqrt{\frac{t+2d-1}{n-k}}W\left(\frac{t}{\delta+1}\frac{e}{\pi}\right)^2 $$

To give a more sensitive meaning of our result, we could approximate the value of the Lambert $W$ function by $W(m) = \log m - \log \log m + \frac{\log \log m}{\log m}$ as $m$ tends to infinity. Using only the first term we define $I_{\beta} = \left[ \sqrt{\frac{2(t+2d)}{n-k}} \log \frac{n-t}{n-k-t+\delta+1}, 1 - \sqrt{\frac{2(t+2d-1)}{n-k}} \log \frac{t}{\delta+1} \right]$. Hence, we deduce the following result.
**Proposition 16.** If $I_β \neq \emptyset$ then the probability of success of the ISD-score decoder is at least

$$ \left( 1 - \frac{e}{2\pi} \frac{1}{\sqrt{\log \frac{n-t}{n-k-t+\delta+1}}} \right) \left( 1 - \frac{e}{\sqrt{2\pi}} \frac{1}{\sqrt{\log \frac{t}{\delta+1}}} \right). $$

Typically, our result gives a sub-interval where the conditions are safely satisfied. When simulations are to be performed, one could solve the inequalities in order to determine a more accurate interval. However, in using the Taylor series of the LambertW function we can deduce the following.

**Corollary 17.** Let $f_{n,k,t,\delta} = \frac{n-t}{n-k-t+\delta+1}$ and $f_{t,\delta}^* = \frac{t}{\delta+1}$. The extreme points of the interval where the first two conditions in Theorem 13 are satisfied, converges to $\sqrt{\frac{t+2d}{n-k}} (2 \log f_{n,k,t,\delta} - \log 2 \log f_{n,k,t,\delta} + \frac{\log 2 \log f_{n,k,t,\delta}}{2 \log f_{n,k,t,\delta}})$, and $1 - \sqrt{\frac{t+2d-1}{n-k}} (2 \log f_{t,\delta}^* - \log 2 \log f_{t,\delta}^* + \frac{\log 2 \log f_{t,\delta}^*}{2 \log f_{t,\delta}^*})$.

<figure><img src="image_8.png" /><figcaption>**Fig. 3:** Number of ones in the first $n-k$ positions for some of the Classic McEliece and BIKE sets of parameters and different levels of a centered binomial noise.</figcaption></figure>

## 4.2 Information-theoretic bounds

### 4.2.1 Bounding the value of t

To see how large the weight of the error $t$ must be to have a non-empty interval, the following rough estimate can be used.

**Theorem 18 (Upper bound on $t$).** Let $k \le n-t+\delta+1-(n-t)(\delta+1)/t$ and $d = ct/2$. Then $I_β \neq \emptyset$ as long as we have

$$ t \le \frac{n-k}{8(1+c)W\left(\frac{n-k}{8(1+c)(\delta+1)}\right)} \qquad (9) $$
Moreover, when $n \to \infty$, we have that $t \le O(\frac{n-k}{\log(n-k)})$.

Using a first term approximation for the Lambert W function near infinity, we obtain a threshold on $t$. More exactly this value can be approximated by $\frac{n-k}{8(1+c)\log\frac{n-k}{8(1+c)(\delta+1)}}$.

Now, recall that we have determined a preliminary condition on $d$, such that the $\psi$ function can distinguish between positions in the support of the solution and outside it. This condition was $d \le \frac{n-k}{8\log\log(n-k)}$. Taking a slightly smaller noise level, e.g. $d = \frac{n-k}{8\log(n-k)} \le \frac{n-k}{8\log\log(n-k)}$ validates the choice in the hypothesis $d = ct/2$, as per Theorem 18 $t \le O(\frac{n-k}{\log(n-k)})$. Taking into account this condition and the hypothesis of Theorem 18, i.e. $d = ct/2$, we deduce the following upper bound on $t$

$$d = \frac{ct}{2} \le \frac{n-k}{8\log t} \Rightarrow t \log t \le \frac{n-k}{4c} \quad (10)$$

This improves the constant term by $t \le \frac{n-k}{4cW(\frac{n-k}{4c})}$.

### 4.2.2 Bounding the required ratio of syndrome entries

The existence of a value such that the ISD-score decoder succeeds in finding a solution using fewer syndrome entries could be deduced. It suffices to replace $(n-k)$ with $\gamma(n-k)$, where $\gamma \in (0, 1]$ represents the percentage of syndrome entries required to achieve a high probability. This value can be deduced from Theorem 18. Typically, given a number of rows $n-k$, the maximum value of $t$ for which the success probability is close enough to 1 also determines the minimum number of required rows. More exactly, for a fixed value of $t$ and $n-k$, we can compute $\gamma(n-k)$, the value for which $t$ satisfies $8t(1+c)\log \frac{t}{\delta+1} = \gamma(n-k)$. By Theorem 18, with only $\gamma(n-k)$ rows, one can recover a solution of weight at most $t$ with high probability. Formally, the following holds.

**Corollary 19.** Let $d = ct/2$ where $c$ is a constant. Then the minimum quantity of information required by the ISD-score decoder to find a valid solution is $4(1+c)t\log \frac{t}{\delta+1}$. Moreover, in the noiseless scenario, the minimum quantity of information becomes $4t\log \frac{t}{\delta+1}$.

Consequently, we deduce that one could improve the constant term, however, not lower than $2(1+c)\log \frac{t}{\delta+1}$.

## 5 Experimental results

The following experiments have been carried out on a standard laptop embedding an 8-core processor running at 1.6 GHz and 32 GB of RAM. The ILP solver we used is provided by the Scipy Python package [41] under the `scipy.optimize.linprog` function. The score decoder is implemented using the Numpy Python package [26] to perform matrix computations.
## 5.1 Success probability and ratio of syndrome entries

For the results presented below, we set the (n, k, t) parameters according to the specifications of the *Classic McEliece* [2] and *BIKE* [3] cryptosystems.

The following experiments look at the number of syndrome entries required to bring $t - \delta$ ones in the first $n-k$ positions, as dictated by the ISD method. Results are shown in Figure 3, for both the *Classic McEliece* and the *BIKE* cryptosystems. Let us explain the meaning of the plots, when these are read horizontally. One way this could be read is as the weight of solutions retrieved by the ISD-Score decoder with probability 1. The green stripe represents the region corresponding to possible values of $\delta$. The value of $\delta$ for the $[t - \delta; t]$ interval is lower for the *BIKE* cryptosystem since it comes with much larger values of $n$, making the exhaustive search for the correct permutation much more costly. Conversely, we allow for $\delta = 3$ in the case of *Classic McEliece* since the $n$ values are smaller. For example, when $n = 8192$ and noise level equal to $t$ we can hope to retrieve solutions of weight at most 122 (which is smaller than the proposed parameters), while for the same length and noise smaller than $t/2$ we can retrieve any solution of weight at most 128 using the ISD-score decoder using $\delta = 3$, or equivalently solutions of weight 125 using the Prange-score decoder. To summarize, except for the case $n = 8192$ with noise levels strictly greater than $t/2$, all the plots suggest that the ISD-score decoder is able to retrieve with high probability a valid solution of weight $t$ in presence of noise.

We can also read the plots vertically. This gives us the ratio of syndrome entries required to find a solution of given weight with high probability. The abscissa of the points of intersection between the curves and the green stripe gives minimum percentage of syndrome entries required in the ISD-score decoder to successfully retrieve a valid solution of weight $t$. For the *BIKE* cryptosystem, the ratio of syndrome entries required to bring at least $t-1$ ones in the first $n-k$ positions ranges from 4.75% to 6.5%. For the *Classic McEliece* cryptosystem, the ratio of syndrome entries required to bring at least $t-3$ ones in the first $n-k$ positions ranges from 48% to 62%. We have also computed the best theoretical lower bound we could hope for, i.e., the percentage of syndrome entries should be at least $\frac{2(1+c)t}{n-k} \log \frac{t}{\delta+1}$. When comparing the experimental results shown in Figure 3 and Table 2, we observe that theoretical values are around 10% smaller than the experimental values.

## 5.2 ILP solver and ISD-score decoder

### Percentage of required entries

To compare the ILP solver with the ISD-score decoder we used the parameters for the *Classic McEliece* proposal. We decided to consider only the *Classic McEliece* because the execution time of the ILP solver for the smallest parameters of *BIKE* exceeded tens of minutes for a single instance of the $N$-SDP. Obtaining in a reasonable time a solid statistical evidence of the performance of the ILP solver for *BIKE*, would assume a much more optimized implementation of the solver, which is not the main purpose of this article. The results for the ILP solver in the noiseless scenario are given in Figure 4. The success rate is computed for ten evenly spaced ratios ranging from 1 to 100%.
<table><caption>**Table 2:** Theoretical lower bound on the ratio of syndrome entries necessary for the ISD-score decoder</caption><thead><tr><th>n</th><th>noiseless</th><th>B(t/2)</th><th>B(t/2)</th><th>B(3t/4)</th><th>B(t/2)</th></tr></thead><tbody><tr><td colspan="6" style="text-align: center; font-style: italic;">Classic McEliece</td></tr><tr><td>3488</td><td>0.46</td><td>0.58</td><td>0.69</td><td>0.81</td><td>0.92</td></tr><tr><td>4608</td><td>0.49</td><td>0.61</td><td>0.73</td><td>0.86</td><td>0.98</td></tr><tr><td>6688</td><td>0.53</td><td>0.67</td><td>0.80</td><td>0.93</td><td>1.00</td></tr><tr><td>8192</td><td>0.53</td><td>0.67</td><td>0.80</td><td>0.93</td><td>1.00</td></tr><tr><td colspan="6" style="text-align: center; font-style: italic;">BIKE</td></tr><tr><td>24646</td><td>0.09</td><td>0.11</td><td>0.14</td><td>0.16</td><td>0.18</td></tr><tr><td>49318</td><td>0.07</td><td>0.09</td><td>0.11</td><td>0.13</td><td>0.15</td></tr><tr><td>81946</td><td>0.06</td><td>0.08</td><td>0.09</td><td>0.11</td><td>0.13</td></tr></tbody></table>

<figure><img src="image_9.png" /><figcaption>**Fig. 4:** Success rate of the ILP solver for the N-SDP for four sets of parameters and different ratios of syndrome entries considered</figcaption></figure>

We observe that the behavior is the same for all sets of parameters. When considering 30% of syndrome entries, the ILP solver failed at recovering the error vector ten times out of ten. Conversely, when considering 40% of syndrome entries, the ILP solver succeeded at recovering the error vector ten times out of ten. Hence, the main drawback of the ILP solver, when compared to the ISD-score decoder, is that the ILP cannot be used when only a small percentage of syndrome entries are known.

### Noisy setting

In a noisy setting, the differences between the ILP solver and the ISD-score decoder is even more dramatic. Indeed, the ILP solver either succeeds in finding a valid solution, with *t* ones in the first *t* positions, or it fails. Conversely, the ISD-score decoder succeeds if *t* − *δ* ones are in the first (*n* − *k*) positions, providing a much larger margin in the noisy setting.

Eventually, the permutation returned by the ISD-score decoder is always better than a random permutation. Therefore, one can always resort to exhaustive search afterwards.
<figure><img src="image_10.png" /><figcaption>Fig. 5: Computation time of the ILP solver and the Score decoder</figcaption></figure>

## Computation time

When comparing the time required by the two algorithms for retrieving a valid solution, we notice a significant gap between the two algorithms. From Figure 5 we can see that it takes less than 0.1 s for the ISD-score decoder, while for the ILP it takes at least 10 s for any of the parameters of the *Classic McEliece* scheme. Broadly speaking, the ILP solver is three orders of magnitude slower than the ISD-score decoder.

# 6 Conclusion

This article evaluated the efficiency of the score decoder for integer syndrome decoding in the presence of noise. We proved that, even in the presence of noise, this decoder is indeed able to successfully bring $t - \delta$ ones in the first $n-k$ positions, as required by the ISD-based methods. We then experimentally validate this capability considering the parameter sets of two post-quantum cryptosystems, *Classic McEliece* and *BIKE*. Future works could investigate other types of noise or improve the efficiency of the decoder, bringing it closer to the information-theoretic bound.

## Acknowledgments.

# Appendix A Proof of Theorem 1

*Proof.* By definition 4 we have that

$$ \psi_i(\mathbf{s}) = \sum_{\ell=1}^{n-k} (h_{\ell,i}s_{\ell} + (1-h_{\ell,i})(t-s_{\ell})). \quad (A1) $$

Let us denote $X_{\ell} = h_{\ell,i}s_{\ell} + (1-h_{\ell,i})(t-s_{\ell})$. As $s_{\ell} = \sum_{j \in \text{Supp}(\mathbf{x})} h_{\ell,j}$ we deduce that

$$ X_{\ell} = h_{\ell,i} \sum_{j \in \text{Supp}(\mathbf{x})} h_{\ell,j} + (1-h_{\ell,i})(t - \sum_{j \in \text{Supp}(\mathbf{x})} h_{\ell,j}). \quad (A2) $$
If $i \notin \text{Supp}(\boldsymbol{x})$ then

$$X_{\ell} = \begin{cases} \sum_{j \in \text{Supp}(\boldsymbol{x})} h_{\ell,j} = s_{\ell}, & \text{if } h_{\ell,i} = 1 \\ t - \sum_{j \in \text{Supp}(\boldsymbol{x})} h_{\ell,j} = t - s_{\ell}, & \text{if } h_{\ell,i} = 0 \end{cases}$$

As $s_{\ell} \sim \mathcal{B}(t, \frac{1}{2})$ we deduce that $X_{\ell} \sim \mathcal{B}(t, \frac{1}{2})$ for all $i \notin \text{Supp}(\boldsymbol{x})$, and by independence we obtain $\psi_i(\boldsymbol{s}) \sim \mathcal{B}((n-k)t, \frac{1}{2})$, then $\mathbb{E}(\psi_i(\boldsymbol{s})) = \frac{(n-k)t}{2}$ and $\text{Var}(\psi_i(\boldsymbol{s})) = \frac{(n-k)t}{4}$.

If $i \in \text{Supp}(\boldsymbol{x})$ we have that $s_{\ell}$ and $h_{\ell,i}$ are dependent random variables. Hence we obtain

$$X_{\ell} = \begin{cases} 1 + \sum_{j \in \text{Supp}(\boldsymbol{x}) \setminus \{i\}} h_{\ell,j}, & \text{if } h_{\ell,i} = 1 \\ 1 + (t-1) - \sum_{j \in \text{Supp}(\boldsymbol{x}) \setminus \{i\}} h_{\ell,j}, & \text{if } h_{\ell,i} = 0 \end{cases}$$

As $s_{\ell} - h_{\ell,i} \sim \mathcal{B}(t-1, \frac{1}{2})$ we deduce that $X_{\ell} \sim 1+\mathcal{B}(t-1, \frac{1}{2})$ for all $i \in \text{Supp}(\boldsymbol{x})$, and by independence of the variables $X_{\ell}$ we obtain $\psi_i(\boldsymbol{s}) \sim (n-k)+\mathcal{B}((n-k)(t-1), \frac{1}{2})$. $\square$

# Appendix B Proof of Corollary 5

*Proof.* Apply Proposition 3 and Corollary 4 to obtain the results. In order to determine the upper bound on $d$, we start by computing the intervals of confidence for $\psi_i(\tilde{\boldsymbol{s}})$ from Proposition 3. This yields an interval $I_{\tilde{\boldsymbol{s}}}(i)$ defined by the two extremal points $\mathbb{E}(\psi_i(\tilde{\boldsymbol{s}})) \pm \sqrt{\frac{d(n-k)g(n,k,t)}{2}}$, i.e.,

* $i \notin \text{Supp}(\boldsymbol{x})$ the points $\frac{(n-k)t}{2} \pm \sqrt{\frac{d(n-k)g(n,k,t)}{2}}$

* $i \in \text{Supp}(\boldsymbol{x})$ the points $\frac{(n-k)t}{2} + \frac{n-k}{2} \pm \sqrt{\frac{d(n-k)g(n,k,t)}{2}}$.

The two intervals are disjoint if we have

$$2\sqrt{\frac{d(n-k)g(n,k,t)}{2}} \le \frac{n-k}{2} \qquad (B3)$$

Hence, we obtain $d \le \frac{n-k}{8g(n,k,t)}$. $\square$

# Appendix C Proof of Theorem 10 and Theorem 11

Let us begin by a useful result.

**Lemma 20 ([29]).** Let $X \sim \mathcal{B}(n, \frac{1}{2})$ and $\frac{n}{2} \le \alpha \le n$. Then

$$\text{Prob}(X \ge \alpha) \le \frac{\alpha + 1}{2\alpha - n + 1} \text{Prob}(X = \alpha). \qquad (C4)$$
**Lemma 21** ([22]). Let $X \sim \mathcal{B}(n, \frac{1}{2})$ and $\alpha \le \frac{n}{2}$. Then

$$ \mathrm{Prob} \left( X = \frac{n}{2} + \alpha \right) \le \frac{e}{2\pi} \sqrt{\frac{n}{\frac{n^2}{4} - \alpha^2}} e^{-\frac{2\alpha^2}{n}}. \quad (C5) $$

**Proposition 22.** Let $X \sim \mathcal{B}(n, \frac{1}{2})$ and $\alpha < n$. Then

$$ \mathrm{Prob} \left( X \ge \frac{n}{2} + \frac{\alpha}{2} \right) \le \frac{e}{2\pi} \left( 1 + \frac{n+1}{\alpha+1} \right) \sqrt{\frac{n}{n^2 - \alpha^2}} e^{-\frac{\alpha^2}{2n}}. \quad (C6) $$

*Proof.* Use Lemma 20 and 21. □

We can now proceed to the proof of Theorem 10.

*Proof.* Recall that

$$ \psi_i(\boldsymbol{s}) \sim \begin{cases} \mathcal{B}((n-k)t, \frac{1}{2}) & \text{for } i \notin \mathrm{Supp}(\boldsymbol{x}) \\ n-k + \mathcal{B}((n-k)(t-1), \frac{1}{2}) & \text{for } i \in \mathrm{Supp}(\boldsymbol{x}) \end{cases} $$

By Proposition 22, for $i \notin \mathrm{Supp}(\boldsymbol{x})$ we have that

$$ \mathrm{Prob} (\psi_i(\boldsymbol{s}) \ge B_{\beta}) \le \frac{\frac{e}{2\pi} \left(1 + \frac{(n-k)t+1}{(n-k)\beta+1}\right) \sqrt{\frac{(n-k)t}{(n-k)^2 t^2 - (n-k)^2 \beta^2}}}{e^{\frac{(n-k)^2 \beta^2}{2(n-k)t}}} \quad (C7) $$

$$ \le \frac{e}{2\pi\beta} \sqrt{\frac{t+\beta}{t-\beta}} \sqrt{\frac{t}{n-k}} e^{-\frac{(n-k)\beta^2}{2t}} \quad (C8) $$

$$ \le \frac{e}{\sqrt{2\pi}\beta} \sqrt{\frac{t}{n-k}} e^{-\frac{(n-k)\beta^2}{2t}} \quad (C9) $$

For $i \in \mathrm{Supp}(\boldsymbol{x})$ we have that $E(\psi_i(\boldsymbol{s})) = \frac{(n-k)t}{2} + \frac{n-k}{2}$. Hence, by Proposition 22 we obtain that $\mathrm{Prob}(\psi_i(\boldsymbol{s}) \le \frac{(n-k)t}{2} + \frac{(n-k)\beta}{2})$ is upper bounded by

$$ \le \frac{\frac{e}{2\pi} \left(1 + \frac{(n-k)(t-1)+1}{(n-k)(1-\beta)+1}\right) \sqrt{\frac{(n-k)(t-1)}{(n-k)^2(t-1)^2 - (n-k)^2(1-\beta)^2}}}{e^{\frac{(n-k)^2(1-\beta)^2}{2(n-k)(t-1)}}} \quad (C10) $$

$$ \le \frac{e}{2\pi\beta} \sqrt{\frac{t-\beta}{t+\beta+2}} \sqrt{\frac{t-1}{n-k}} e^{-\frac{(n-k)(1-\beta)^2}{2(t-1)}} \quad (C11) $$

$$ \le \frac{e}{2\pi\beta} \sqrt{\frac{t-1}{n-k}} e^{-\frac{(n-k)\beta^2}{2(t-1)}}. \quad (C12) $$

□

As for Theorem 11 we have:
Proof. Recall that we have

• for $i \notin \text{Supp}(\boldsymbol{x})$

$$ \psi_i(\tilde{s}) \sim -d(n-k) + \mathcal{B}\left((n-k)(t+2d), \frac{1}{2}\right); $$

• for $i \in \text{Supp}(\boldsymbol{x})$

$$ \psi_i(\tilde{s}) \sim -(d-1)(n-k) + \mathcal{B}\left((n-k)(t-1+2d), \frac{1}{2}\right). $$

The proof is thus identical with that of Theorem 10 by simply putting $t' = t + 2d$ when $i \notin \text{Supp}(\boldsymbol{x})$ and $t' = t + 2d - 1$ when $i \in \text{Supp}(\boldsymbol{x})$. $\square$

## Appendix D Proof of Theorem 12

Proof. Let $X_B$ denote the number of indices $j \in \text{Supp}(\boldsymbol{x})$ for which $\psi_i(\tilde{s}) \le B$, and $Y_B$ the number of indices $j \notin \text{Supp}(\boldsymbol{x})$ for which $\psi_i(\tilde{s}) \ge B$. The probability of success of our algorithm equals

$$ \begin{aligned} & = \sum_B \text{Prob}(X_B \le \delta) \text{Prob}(Y_B \le n-k-t+\delta) \\ & = \sum_B (1 - \text{Prob}(X_B \ge \delta+1)) \cdot (1 - \text{Prob}(Y_B \ge n-k-t+\delta+1)) \\ & \ge \sum_B \left(1 - \frac{t}{\delta+1} e^{-f(n,k,t,d,B)}\right) \cdot \left(1 - \frac{n-t}{n-k-t+\delta+1} e^{-g(n,k,t,d,B)}\right). \end{aligned} $$

In the last equation we have used Markov's inequality. Also, the last sum is over those values $B$ for which the two terms in the sum are both positive and smaller than 1. Now suppose that a $B^*$ satisfying the required condition exists. Then the probability of success is

$$ \begin{aligned} & \ge \left(1 - \frac{t}{\delta+1} e^{-f(n,k,t,d,B^*)}\right) \cdot \left(1 - \frac{n-t}{n-k-t+\delta+1} e^{-g(n,k,t,d,B^*)}\right) \\ & \ge 1 - \frac{t}{\delta+1} e^{-f(n,k,t,d,B^*)} - \frac{n-t}{n-k-t+\delta+1} e^{-g(n,k,t,d,B^*)}. \end{aligned} $$

$\square$

## Appendix E Range of valid parameters: proofs and comments

The first useful results concerns the monotony of the two upper bounds.
**Lemma 23.** The functions $\frac{t}{\delta+1} \mathrm{Ub}_{\mathrm{Supp}(\boldsymbol{x})}(n, k, t, d, \beta)$ and $\frac{n-t}{n-k-t+\delta+1} \mathrm{Ub}_{\mathrm{Supp}(\boldsymbol{x})}^c(n, k, t, d, \beta)$ in $\beta \in (0, 1)$, are positive increasing, and positive decreasing, resp.

*Proof.* Let $f(n, k, t, d, \beta) = \frac{t}{\delta+1} \mathrm{Ub}_{\mathrm{Supp}(\boldsymbol{x})}(n, k, t, \beta^*)$ and $g(n, k, t, d, \beta) = \frac{n-t}{n-k-t+\delta+1} \mathrm{Ub}_{\mathrm{Supp}(\boldsymbol{x})}^c(n, k, t, d, \beta)$. We have that both functions $f, g$ are positive. We also have

$$ \frac{\partial g(n, k, t, d, \beta)}{\partial \beta} = - \frac{(n-k)\beta^2 + (t+2d)}{\beta(t+2d)} g(n, k, t, d, \beta) $$

$$ \frac{\partial f(n, k, t, d, \beta)}{\partial \beta} = \frac{(n-k)(1-\beta)^2 + (t+2d-1)}{(1-\beta)(t+2d-1)} f(n, k, t, d, \beta). $$

Using the fact that $f$ and $g$ are positive we deduce the wanted result. $\square$

Now we can demonstrate Proposition 15.

*Proof.* Let us consider the limit point $\beta$ where the two functions equal 1. As the first function is decreasing we then obtain a lower bound on $\beta$.

$$ \frac{n-t}{n-k-t+\delta+1} \mathrm{Ub}_{\mathrm{Supp}(\boldsymbol{x})}^c(n, k, t, d, \beta) = 1 \qquad (\text{E13}) $$

$$ \frac{n-t}{n-k-t+\delta+1} \frac{e}{\sqrt{2\pi\beta}} \sqrt{\frac{t+2d}{n-k}} e^{-\frac{(n-k)\beta^2}{2(t+2d)}} = 1 \qquad (\text{E14}) $$

$$ \left( \frac{n-t}{n-k-t+\delta+1} \frac{e}{\sqrt{2\pi}} \right)^2 \frac{t+2d}{(n-k)\beta^2} = e^{\frac{(n-k)\beta^2}{t+2d}} \qquad (\text{E15}) $$

By letting $y = \frac{(n-k)\beta^2}{t+2d}$ we have

$$ ye^y = \left( \frac{n-t}{n-k-t+\delta+1} \frac{e}{\sqrt{2\pi}} \right)^2, \qquad (\text{E16}) $$

admitting a real solution $y = W(\frac{n-t}{n-k-t+\delta+1}, \frac{e}{\sqrt{2\pi}})^2$, where $W$ is the Lambert W function. From this we deduce $\beta = \sqrt{\frac{t+2d}{n-k}} W(\frac{n-t}{n-k-t+\delta+1}, \frac{e}{\sqrt{2\pi}})^2$. The second function is increasing hence, it gives an upper bound on $\beta$.

$$ \frac{t}{\delta+1} \mathrm{Ub}_{\mathrm{Supp}(\boldsymbol{x})}(n, k, t, d, \beta) = 1 \qquad (\text{E17}) $$

$$ \frac{t}{\delta+1} \frac{e}{\pi(1-\beta)} \sqrt{\frac{t+2d-1}{n-k}} e^{-\frac{(n-k)(1-\beta)^2}{2(t+2d-1)}} = 1 \qquad (\text{E18}) $$

$$ \left( \frac{t}{\delta+1} \frac{e}{\pi} \right)^2 \frac{t+2d-1}{(n-k)(1-\beta)^2} = e^{\frac{(n-k)(1-\beta)^2}{t+2d-1}} \qquad (\text{E19}) $$
As in the first case we obtain $1 - \beta = \sqrt{\frac{t+2d-1}{n-k}} W\left(\frac{t}{\delta+1}, \frac{e}{\pi}\right)$. $\square$

Proposition 16 gives a slightly weaker condition, however, it helps understanding the order of magnitude of the parameters. Let us demonstrate the result.

**Proof.** Let $\beta \ge \beta_1 = \sqrt{\frac{2t+2d}{n-k} \log \frac{n-t}{n-k-t+\delta+1}}$. Then the quantity $\frac{n-t}{n-k-t+\delta+1} \mathrm{Ub}_{\mathrm{Supp}(\boldsymbol{x})}^c(n, k, t, d, \beta)$ equals

$$= \frac{n-t}{n-k-t+\delta+1} \frac{e}{\sqrt{2\pi}\beta} \sqrt{\frac{t+2d}{n-k}} e^{-\frac{(n-k)\beta^2}{2(t+2d)}} \quad (E20)$$

$$\le \frac{n-t}{n-k-t+\delta+1} \frac{e}{2\pi\sqrt{\log \frac{n-t}{n-k-t+\delta+1}}} e^{-\log \frac{n-t}{n-k-t+\delta+1}} \quad (E21)$$

$$= \frac{e}{2\pi} \frac{1}{\sqrt{\log \frac{n-t}{n-k-t+\delta+1}}} \quad (E22)$$

Let $1 - \beta \ge \beta_2 = \sqrt{\frac{2t+2d-1}{n-k} \log \frac{t}{\delta+1}}$. Then the quantity $\frac{t}{\delta+1} \mathrm{Ub}_{\mathrm{Supp}(\boldsymbol{x})}(n, k, t, d, \beta)$ equals

$$= \frac{t}{\delta+1} \frac{e}{\pi(1-\beta)} \sqrt{\frac{t+2d-1}{n-k}} e^{-\frac{(n-k)(1-\beta)^2}{2(t+2d-1)}} \quad (E23)$$

$$\le \frac{e}{\sqrt{2\pi}} \frac{1}{\sqrt{\log \frac{t}{\delta+1}}} \quad (E24)$$

From this we deduce

$$\frac{\sqrt{2(t+2d)}}{\sqrt{n-k}} \sqrt{\log \frac{n-t}{n-k-t+\delta+1}} \le \beta \quad (E25)$$

$$\beta \le 1 - \frac{\sqrt{2(t+2d-1)}}{\sqrt{n-k}} \sqrt{\log \frac{t}{\delta+1}} \quad (E26)$$

Now, suppose that $[\beta_1, \beta_2]$ is non-empty and take $\beta^* \in [\beta_1, \beta_2]$. Since $\frac{t}{\delta+1} \mathrm{Ub}_{\mathrm{Supp}(\boldsymbol{x})}(n, k, t, d, \beta)$ is increasing in $\beta$, this implies that $\frac{t}{\delta+1} \mathrm{Ub}_{\mathrm{Supp}(\boldsymbol{x})}(n, k, t, d, \beta^*)$ is upper bounded by

$$\frac{t}{\delta+1} \mathrm{Ub}_{\mathrm{Supp}(\boldsymbol{x})}(n, k, t, d, \beta_2) = \frac{e}{\sqrt{2\pi}} \frac{1}{\sqrt{\log \frac{t}{\delta+1}}} \quad (E27)$$
Also, as $\frac{n-t}{n-k-t+\delta+1} \mathrm{Ub}_{\mathrm{Supp}(\boldsymbol{x})^c}(n, k, t, d, \beta)$ is decreasing in $\beta$ we have that $\frac{n-t}{n-k-t+\delta+1} \mathrm{Ub}_{\mathrm{Supp}(\boldsymbol{x})^c}(n, k, t, d, \beta^*)$ is upper bounded by

$$ \leq \frac{n-t}{n-k-t+\delta+1} \mathrm{Ub}_{\mathrm{Supp}(\boldsymbol{x})^c}(n, k, t, d, \beta_1) \quad (E28) $$

$$ \leq \frac{e}{2\pi} \frac{1}{\sqrt{\log \frac{n-t}{n-k-t+\delta+1}}} \quad (E29) $$

Equations (E27) and (E28) implies that both function $\frac{n-t}{n-k-t+\delta+1} \mathrm{Ub}_{\mathrm{Supp}(\boldsymbol{x})^c}(n, k, t, d, \beta)$, $\frac{t}{\delta+1} \mathrm{Ub}_{\mathrm{Supp}(\boldsymbol{x})^c}(n, k, t, d, \beta)$ are smaller than 1 in $\beta^*$ and that the probability of success is at least

$$ \left( 1 - \frac{e}{2\pi} \frac{1}{\sqrt{\log \frac{n-t}{n-k-t+\delta+1}}} \right) \left( 1 - \frac{e}{\sqrt{2\pi}} \frac{1}{\sqrt{\log \frac{t}{\delta+1}}} \right) \quad (E30) $$

□

The last result to demonstrate from this section is Theorem 18

*Proof.* Taking the simplified interval for $\beta$, the existence of this interval implies

$$ \frac{\sqrt{2(t+2d)}}{\sqrt{n-k}} \sqrt{\log \frac{n-t}{n-k-t+\delta+1}} \leq 1 - \frac{\sqrt{2(t+2d-1)}}{\sqrt{n-k}} \sqrt{\log \frac{t}{\delta+1}} \quad (E31) $$

$$ \sqrt{\log \frac{n-t}{n-k-t+\delta+1}} + \sqrt{\log \frac{t}{\delta+1}} \leq \sqrt{\frac{n-k}{2(t+2d)}} \quad (E32) $$

Using the condition on $k$ we deduce

$$ \sqrt{\log \frac{n-t}{n-k-t+\delta+1}} \leq \sqrt{\log \frac{n-t}{n - (n - t + \delta + 1 - \frac{(n-t)(\delta+1)}{t}) - t + \delta + 1}} \quad (E33) $$

$$ \sqrt{\log \frac{n-t}{n-k-t+\delta+1}} \leq \sqrt{\log \frac{t}{\delta+1}} \quad (E34) $$

Hence, the following should hold

$$ 2\sqrt{\log \frac{t}{\delta+1}} \leq \sqrt{\frac{n-k}{2(1+c)t}} \quad (E35) $$

$$ \frac{t}{\delta+1} \log \frac{t}{\delta+1} \leq \frac{n-k}{8(1+c)(\delta+1)}, \quad (E36) $$
which is satisfied as long as $t \le \frac{n-k}{8(1+c)W(\frac{n-k}{8(1+c)(\delta+1)})}$. The initial condition on $k$ implies $t \le \frac{n-k+2\delta+2-\sqrt{(n-k+2\delta+2)^2-4n(\delta+1)}}{2}$ which is greater than or equal to $\frac{n-k}{8(1+c)W(\frac{n-k}{8(1+c)(\delta+1)})}$.

As for the asymptotic, use one term approximation for the LambertW function near infinity. $\square$

## References

[1] Nabil R. Adam and John C. Worthmann. Security-control methods for statistical databases: A comparative study. *ACM Comput. Surv.*, 21(4):515–556, dec 1989.

[2] Martin R. Albrecht, Daniel J. Bernstein, Tung Chou, Carlos Cid, Jan Gilcher, Tanja Lange, Varun Maram, Ingo von Maurich, Rafael Misoczki, Ruben Niederhagen, Kenneth G. Paterson, Edoardo Persichetti, Christiane Peters, Peter Schwabe, Nicolas Sendrier, Jakub Szefer, Cen Jung Tjhai, Martin Tomlinson, and Wen Wang. Classic McEliece. Technical report, National Institute of Standards and Technology, 2020. available at https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions.

[3] Nicolas Aragon, Paulo Barreto, Slim Bettaieb, Loic Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Phillipe Gaborit, Shay Gueron, Tim Guneysu, Carlos Aguilar Melchor, Rafael Misoczki, Edoardo Persichetti, Nicolas Sendrier, Jean-Pierre Tillich, Gilles Zémor, Valentin Vasseur, and Santosh Ghosh. BIKE. Technical report, National Institute of Standards and Technology, 2020. available at https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions.

[4] Daniel Augot, Matthieu Finiasz, and Nicolas Sendrier. A fast provably secure cryptographic hash function. *IACR Cryptol. ePrint Arch.*, 2003:230, 2003.

[5] Anja Becker, Antoine Joux, Alexander May, and Alexander Meurer. Decoding random binary linear codes in $2^{n/20}$: How $1+1=0$ improves information set decoding. In *Advances in Cryptology - EUROCRYPT 2012*, Lecture Notes in Comput. Sci. Springer, 2012.

[6] Elwyn Berlekamp, Robert McEliece, and Henk van Tilborg. On the inherent intractability of certain coding problems. *IEEE Trans. Inform. Theory*, 24(3):384–386, May 1978.

[7] Daniel J. Bernstein, Tanja Lange, and Christiane Peters. Smaller decoding exponents: ball-collision decoding. In *Advances in Cryptology - CRYPTO 2011*, volume 6841 of *Lecture Notes in Comput. Sci.*, pages 743–760, 2011.

[8] Jonathan Bootle, Claire Delaplace, Thomas Espitau, Pierre-Alain Fouque, and Mehdi Tibouchi. LWE without modular reduction and improved side-channel attacks against bliss. In Thomas Peyrin and Steven Galbraith, editors, *Advances in Cryptology - ASIACRYPT 2018*, pages 494–524, Cham, 2018. Springer International Publishing.

[9] Leif Both and Alexander May. Decoding linear codes with high error rate and its impact for LPN security. In Tanja Lange and Rainer Steinwandt, editors, *Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018*, Fort
Lauderdale, FL, USA, April 9-11, 2018, Proceedings, volume 10786 of Lecture Notes in Computer Science, pages 25–46. Springer, 2018.

[10] Anne Canteaut and Florent Chabaud. A new algorithm for finding minimum-weight words in a linear code: Application to mceliece's cryptosystem and to narrow-sense BCH codes of length 511. *IEEE Trans. Inform. Theory*, 44(1):367–378, 1998.

[11] Chang-Chang Cao, Cheng Li, and Xiao Sun. Quantitative group testing-based overlapping pool sequencing to identify rare variant carriers. *BMC Bioinformatics*, 15(195):1–14, 2014.

[12] Kevin Carrier, Thomas Debris-Alazard, Charles Meyer-Hilfiger, and Jean-Pierre Tillich. Statistical decoding 2.0: Reducing decoding to LPN, 2022.

[13] Pierre-Louis Cayrel, Brice Colombier, Vlad-Florin Dragoi, Alexandre Menu, and Lilian Bossuet. Message-recovery laser fault injection attack on the classic McEliece cryptosystem. In Anne Canteaut and François-Xavier Standaert, editors, *Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part II*, volume 12697 of Lecture Notes in Computer Science, pages 438–467. Springer, 2021.

[14] Brice Colombier, Vlad-Florin Dragoi, Pierre-Louis Cayrel, and Vincent Grosso. Message-recovery profiled side-channel attack on the classic McEliece cryptosystem. *Cryptology ePrint Archive, Report 2022/125*, 2022.

[15] Thomas Debris-Alazard and Jean-Pierre Tillich. Statistical decoding. In *2017 IEEE International Symposium on Information Theory (ISIT)*, pages 1798–1802, 2017.

[16] Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In *Proceedings of the Twenty-Second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems*, PODS '03, page 202–210, New York, NY, USA, 2003. Association for Computing Machinery.

[17] Vlad-Florin Dragoi, Pierre-Louis Cayrel, Brice Colombier, Dominic Bucerzan, and Sorin Hoara. Solving a modified syndrome decoding problem using integer programming. *INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS and CONTROL*, 15(5), 2020.

[18] Vlad-Florin Dragoi and Ferucio Laurentiu Tiplea. Generalized-inverse based decoding. Technical report, 2022.

[19] Il'ya Dumer. Two decoding algorithms for linear codes. *Probl. Inf. Transm.*, 25(1):17–23, 1989.

[20] Ilya Dumer. On minimum distance decoding of linear codes. In *Proc. 5th Joint Soviet-Swedish Int. Workshop Inform. Theory*, pages 50–52, Moscow, 1991.

[21] Andre Esser and Emanuele Bellini. Syndrome decoding estimator. In Goichiro Hanaoka, Junji Shikata, and Yohei Watanabe, editors, *IACR International Conference on Practice and Theory of Public-Key Cryptography*, volume 13177 of Lecture Notes in Computer Science, pages 112–141, virtual event, March 2022. Springer.

[22] Uriel Feige and Amir Lellouche. Quantitative group testing and the rank of random matrices. CoRR, abs/2006.09074, 2020.
[23] Matthieu Finiasz and Nicolas Sendrier. Security bounds for the design of code-based cryptosystems. In M. Matsui, editor, *Advances in Cryptology - ASIACRYPT 2009*, volume 5912 of *Lecture Notes in Comput. Sci.*, pages 88–105. Springer, 2009.

[24] M. P. C. Fossorier, K. Kobara, and H. Imai. Modeling bit flipping decoding based on nonorthogonal check sums with application to iterative decoding attack of mceliece cryptosystem. *IEEE Trans. Inf. Theor.*, 53(1):402–411, jan 2007.

[25] Philippe Gaborit, Cedric Lauradoux, and Nicolas Sendrier. Synd: a fast code-based stream cipher with a security reduction. In *2007 IEEE International Symposium on Information Theory*, pages 186–190, 2007.

[26] Charles R Harris, K Jarrod Millman, Stéfan J Van Der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J Smith, et al. Array programming with numpy. *Nature*, 585(7825):357–362, 2020.

[27] Anna-Lena Horlemann, Sven Puchinger, Julian Renner, Thomas Schamberger, and Antonia Wachter-Zeh. Information-set decoding with hints. In Antonia Wachter-Zeh, Hannes Bartz, and Gianluigi Liva, editors, *International Workshop on Code-Based Cryptography*, volume 13150 of *Lecture Notes in Computer Science*, pages 60–83, Munich, Germany, jun 2021. Springer.

[28] A. Al Jabri. A statistical decoding algorithm for general linear block codes. In Bahram Honary, editor, *Cryptography and Coding*, pages 1–8, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg.

[29] Bernhard Klar. Bounds on tail probabilities of discrete distributions. *Probability in the Engineering and Informational Sciences*, 14:161 – 171, 2000.

[30] Pil J. Lee and Ernest F. Brickell. An observation on the security of McEliece's public-key cryptosystem. In *Advances in Cryptology - EUROCRYPT'88*, volume 330 of *Lecture Notes in Comput. Sci.*, pages 275–280. Springer, 1988.

[31] Jeffrey Leon. A probabilistic algorithm for computing minimum weights of large error-correcting codes. *IEEE Trans. Inform. Theory*, 34(5):1354–1359, 1988.

[32] João Paulo Martins, Rui Santos, and Ricardo Sousa. *Testing the Maximum by the Mean in Quantitative Group Tests*, pages 55–63. Springer International Publishing, Cham, 2014.

[33] Alexander May, Alexander Meurer, and Enrico Thomae. Decoding random linear codes in $O(2^{0.054n})$. In Dong Hoon Lee and Xiaoyun Wang, editors, *Advances in Cryptology - ASIACRYPT 2011*, volume 7073 of *Lecture Notes in Comput. Sci.*, pages 107–124. Springer, 2011.

[34] Alexander May and Ilya Ozerov. On computing nearest neighbors with applications to decoding of binary linear codes. In E. Oswald and M. Fischlin, editors, *Advances in Cryptology - EUROCRYPT 2015*, volume 9056 of *Lecture Notes in Comput. Sci.*, pages 203–228. Springer, 2015.

[35] Harald Niederreiter. Knapsack-type cryptosystems and algebraic coding theory. *Problems of Control and Information Theory*, 15(2):159–166, 1986.

[36] R. Overbeck. Statistical decoding revisited. In Lynn Margaret Batten and Reihaneh Safavi-Naini, editors, *Information Security and Privacy*, pages 283–294, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
[37] Eugene Prange. The use of information sets in decoding cyclic codes. *IRE Transactions on Information Theory*, 8(5):5-9, 1962.

[38] P.W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In S. Goldwasser, editor, *FOCS*, pages 124–134, 1994.

[39] Jacques Stern. A method for finding codewords of small weight. In G. D. Cohen and J. Wolfmann, editors, *Coding Theory and Applications*, volume 388 of *Lecture Notes in Comput. Sci.*, pages 106–113. Springer, 1988.

[40] Jacques Stern. A new identification scheme based on syndrome decoding. In Douglas R. Stinson, editor, *Advances in Cryptology - CRYPTO '93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings*, volume 773 of *Lecture Notes in Computer Science*, pages 13–21. Springer, 1993.

[41] Pauli Virtanen, Ralf Gommers, Travis E Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, et al. Scipy 1.0: fundamental algorithms for scientific computing in python. *Nature methods*, 17(3):261–272, 2020.

[42] Chao Wang, Qing Zhao, and Chen-Nee Chuah. Group testing under sum observations for heavy hitter detection. In *2015 Information Theory and Applications Workshop (ITA)*, pages 149–153, 2015.

[43] I-Hsiang Wang, Shao-Lun Huang, Kuan-Yun Lee, and Kwang-Cheng Chen. Data extraction via histogram and arithmetic mean queries: Fundamental limits and algorithms. In *2016 IEEE International Symposium on Information Theory (ISIT)*, pages 1386–1390, 2016.