# Reduction from Sparse LPN to LPN, Dual Attack 3.0

Kévin Carrier, Thomas Debris-Alazard, Charles Meyer-Hilfiger, Jean-Pierre Tillich

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

## To cite this version:

Kévin Carrier, Thomas Debris-Alazard, Charles Meyer-Hilfiger, Jean-Pierre Tillich. Reduction from Sparse LPN to LPN, Dual Attack 3.0. 2023. hal-04328262

HAL Id: hal-04328262

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

Preprint submitted on 7 Dec 2023

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_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
REDUCTION FROM SPARSE LPN TO LPN, DUAL ATTACK 3.0

KÉVIN CARRIER<fnref n="1" />, THOMAS DEBRIS-ALAZARD<fnref n="2" />,<fnref n="3" />, CHARLES MEYER-HILFIGER<fnref n="4" />, AND JEAN-PIERRE TILLICH<fnref n="4" />

ABSTRACT. The security of code-based cryptography relies primarily on the hardness of decoding generic linear codes. Until very recently, all the best algorithms for solving the decoding problem were information set decoders (ISD). However, recently a new algorithm called RLPN-decoding which relies on a completely different approach was introduced and it has been shown that RLPN outperforms significantly ISD decoders for a rather large range of rates. This RLPN decoder relies on two ingredients, first reducing decoding to some underlying LPN problem, and then computing efficiently many parity-checks of small weight when restricted to some positions. We revisit RLPN-decoding by noticing that, in this algorithm, decoding is in fact reduced to a sparse-LPN problem, namely with a secret whose Hamming weight is small. Our new approach consists this time in making an additional reduction from sparse-LPN to plain-LPN with a coding approach inspired by coded-BKW. It outperforms significantly the ISD's and RLPN for code rates smaller than 0.42. This algorithm can be viewed as the code-based cryptography cousin of recent dual attacks in lattice-based cryptography. We depart completely from the traditional analysis of this kind of algorithm which uses a certain number of independence assumptions that have been strongly questioned recently in the latter domain. We give instead a formula for the LPN noise relying on duality which allows to analyze the behavior of the algorithm by relying only on the analysis of a certain weight distribution. By using only a minimal assumption whose validity has been verified experimentally we are able to justify the correctness of our algorithm. This key tool, namely the duality formula, can be readily adapted to the lattice setting and is shown to give a simple explanation for some phenomena observed on dual attacks in lattices in [DP23b].

# 1. INTRODUCTION

## 1.1. Background.

**Code-based Cryptography: Decoding and LPN Problems.** Code-based cryptography relies on the hardness of decoding generic linear codes or sometimes also on a closely related problem, namely the LPN problem. The first one corresponds in the binary case to

**Problem 1** (decoding a fixed error weight in a linear code). Let $C$ be a binary linear code over $\mathbb{F}_2$ of dimension $k$ and length $n$, i.e. a subspace of $\mathbb{F}_2^n$ of dimension $k$. We are given $\mathbf{y} \in \mathbb{F}_2^n$, an integer $t$ and we want to find a codeword $\mathbf{c} \in C$ and an error vector $\mathbf{e} \in \mathbb{F}_2^n$ of Hamming weight $|\mathbf{e}| = t$ for which $\mathbf{y} = \mathbf{c} + \mathbf{e}$.

Generally the linear code is specified by a *generator matrix*, namely a $k \times n$ binary matrix $G$ whose rows span the vector space $C$, in other words

$$C = \{uG : u \in \mathbb{F}_2^k\}.$$

<footnote n="1">¹ LABORATOIRE ETIS, UMR 8051, CY CERGY-PARIS UNIVERSITÉ, ENSEA, CNRS</footnote>

<footnote n="2">² PROJECT GRACE, INRIA SACLAY</footnote>

<footnote n="3">³ LABORATOIRE LIX, ÉCOLE POLYTECHNIQUE, INSTITUT POLYTECHNIQUE DE PARIS, 1 RUE HONORÉ D'ESTIENNE D'ORVES, 91120 PALAISEAU CEDEX</footnote>

<footnote n="4">⁴ PROJECT COSMIQ, INRIA DE PARIS</footnote>

<footnote>*E-mail addresses:* kevin.carrier@ensea.fr, thomas.debris@inria.fr, charles.meyer-hilfiger@inria.fr, jean-pierre.tilllich@inria.fr.</footnote>

<footnote>The work of KC, TDA and JPT was funded by the French Agence Nationale de la Recherche through ANR JCJC DECODE (ANR-22-CE39-0004-01) for KC, ANR JCJC COLA (ANR-21-CE39-0011) for TDA and ANR-22-PETQ-0008 PQ-TLS for JPT. The work of CMH was funded by the French Agence de l'innovation de défense and by Inria.</footnote>
The second one is a version of this problem where the length $n$ is basically unbounded; the code is randomly chosen and the error model is slightly modified to take into account that the length is not fixed.

**Problem 2 (LPN problem).** Let $\mathbf{s}$ be a secret chosen uniformly at random in $\mathbb{F}_2^k$. We have unbounded access to an oracle such that each query provides a pair $(\mathbf{a}, b)$ where $\mathbf{a}$ is chosen uniformly at random in $\mathbb{F}_2^k$ and $b$ is a bit obtained as

$$b = \langle \mathbf{s}, \mathbf{a} \rangle + e$$

where $e \in \mathbb{F}_2$ is chosen at random and is equal to 1 with probability $p$. Quantity $\langle \mathbf{s}, \mathbf{a} \rangle$ stands for the inner product $\sum_{i=1}^k s_i a_i$ between $\mathbf{s} = (s_i)_{1 \le i \le k}$ and $\mathbf{a} = (a_i)_{1 \le i \le k}$. The aim is to output $\mathbf{s}$ after querying a certain number of times the oracle.

Sometimes a variation of the LPN problem is considered, namely the sparse LPN problem where the only difference is the way $\mathbf{s}$ is chosen, say uniformly at random among the words of length $n$ and Hamming weight $t'$ small, or the entries like i.i.d. Bernoulli random variables of parameter $p'$ small.

**The Complexity of the Best Generic Decoding Algorithms and LPN-solvers.** It is of fundamental importance to study the complexity of these problems, the best state of the art algorithms being those that are used to determine secure parameters of code-based cryptosystems. The regime of parameters which is relevant for code-based cryptography depends on the type of primitive, but a large range of parameters is relevant here. For some code-based cryptosystems, $t$ is sublinear in $n$, [McE78, AAB+21a, AAB+21b, BCL+19, AAB+21b], for some Stern like signatures schemes [Ste93, Vér96, CVA10, AGS11, GPS22, FJR22] it is precisely decoding at the Gilbert-Varshamov distance that is relevant. It is at this distance that the decoding problem is expected to be the hardest. Recall that the Gilbert-Varshamov distance $d_{GV}(n, k)$ is given by $d_{GV}(n, k) \stackrel{\text{def}}{=} n h^{-1}(1-R)$, where $R \stackrel{\text{def}}{=} \frac{k}{n}$ is the code rate, $h$ is the binary entropy function $h(x) \stackrel{\text{def}}{=} -x \log_2 x - (1-x) \log_2(1-x)$ and $h^{-1}(x)$ its inverse ranging over $(0, \frac{1}{2})$. Above this bound, the number of solutions becomes exponential and this helps to devise more efficient decoders.

Concerning now the LPN problem, it has long been recognized that having an unbounded number of queries or codelength while having a fixed error probability $p$ per bit as in LPN makes the problem really simpler. The best algorithms for solving this problem, are BKW type algorithms [BKW03, EKM17] and are of subexponential complexity $2^{O(k/\log k)}$. However, this is not true anymore if the number of queries is fixed and the error rate $p$ is chosen such that the problem is the hardest, namely when $h(p) = 1-k/n$. In this case, the best algorithms behave exponentially in $\min(k, n-k)$ despite many efforts on this issue [Pra62, Ste88, Dum91, BLP11, MMT11, BJMM12, MO15, BM17, BM18, CDMT22].

**Reduction from Decoding to an LPN Problem.** Note that until very recently, all the best algorithms for solving the decoding problem or the LPN problem when it is the hardest have been ISD algorithms. They all rely crucially on the Prange bet, namely that we have finally found after many trials a subset of positions of size $\approx n-k$ which contains almost all the errors. This was the situation since 1962 [Pra62]. There was at some point, just one exception [Dum86] which relied instead on a collision technique and gave only a slight improvement in a very tiny rate range $R \in (0.98, 1)$, but it was soon found out how to incorporate this technique in ISD algorithms [Ste88, Dum89] to improve them. However in 2022, a new algorithm called RLPN-decoding was introduced in [CDMT22]. It relies on a completely different approach following an old idea called “statistical decoding” due to Al Jabri [Jab01]. The new approach consists in reducing decoding to LPN. For the first time in sixty years a strong competitor for ISD techniques was found: it outperforms ISD techniques in the low rate regime, say $R \in (0, 0.3)$ and the improvement is quite significant in the range $R \in (0, 0.2)$ say. To explain the idea, assume we are given an instance of the decoding problem $\mathbf{y} = \mathbf{c} + \mathbf{e}$, where $\mathbf{c} \in \mathcal{C}$ and $|\mathbf{e}| = t$. As in statistical decoding, decoding relies on low weight parity-check equations, namely vectors $\mathbf{h}$ such that $\langle \mathbf{h}, \mathbf{c} \rangle = 0$ for any $\mathbf{c} \in \mathcal{C}$ (in other words, such $\mathbf{h}$'s belong to the dual code $\mathcal{C}^\perp$). However, in the new approach these parity-check equations are required to be of low weight only on a subset $\mathcal{N}$ of positions. The rest of the
positions $\mathcal{P}$ correspond to the entries of $\mathbf{e}$ we aim to recover and is the secret in the LPN problem. The point of the whole approach is that

$$ \langle \mathbf{y}, \mathbf{h} \rangle = \langle \mathbf{e}, \mathbf{h} \rangle = \sum_{j \in \mathcal{P}} h_j e_j + \sum_{j \in \mathcal{N}} h_j e_j = \underbrace{\langle \mathbf{e}_{\mathcal{P}}, \mathbf{h}_{\mathcal{P}} \rangle}_{\text{lin. comb.}} + \underbrace{\langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle}_{\text{LPN noise}} $$

Here the notation $\mathbf{e}_{\mathcal{P}}$ means the restriction of $\mathbf{e}$ to the positions in $\mathcal{P}$: $\mathbf{e}_{\mathcal{P}} = (e_i)_{i \in \mathcal{P}}$. Vector $\mathbf{e}_{\mathcal{P}}$ is interpreted as the LPN secret $\mathbf{s}$, i.e. $\mathbf{s} \stackrel{\text{def}}{=} \mathbf{e}_{\mathcal{P}}$ and $\mathbf{h}_{\mathcal{P}}$ as the linear combination vector $\mathbf{a}$ while $\langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle$ is the LPN noise. Therefore, by computing $(\mathbf{h}, \langle \mathbf{y}, \mathbf{h} \rangle)$ we really have access to the LPN sample

$$ \underbrace{\mathbf{a}}_{\mathbf{h}_{\mathcal{P}}} \cdot \underbrace{\langle \mathbf{s}, \mathbf{a} \rangle}_{\langle \mathbf{e}_{\mathcal{P}}, \mathbf{h}_{\mathcal{P}} \rangle} + \underbrace{e}_{\langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle} $$

The point of choosing low weight vectors $\mathbf{h}$ on $\mathcal{N}$, is that it is readily verified that this translates into the fact that the binary random variable $\langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle$ is biased, say $\mathbb{P}(\langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle = 1) = \frac{1-\varepsilon}{2}$ with a bias $\varepsilon$ which gets bigger when the Hamming weight $|\mathbf{h}_{\mathcal{N}}|$ of $\mathbf{h}$ on $\mathcal{N}$ gets smaller.

Recovering $\mathbf{e}_{\mathcal{P}}$ is then performed by producing enough parity-check equations to have enough information on $\mathbf{e}_{\mathcal{P}}$ (we need about $N \approx 1/\varepsilon^2$ parity-check equations) and amounts to solve the LPN problem. This is done by the Fast Fourier Transform (FFT) and costs about $s2^s$ where $s \stackrel{\text{def}}{=} |\mathcal{P}|$. We cannot afford more sophisticated techniques like the BKW algorithm which would give a sub-exponential algorithm, because we are very far away from the constant error probability regime. Here the bias $\varepsilon$ is exponentially small in the codelength, so we are really in the extreme noise regime, where on top of that we have hardly more LPN samples than the number we need to recover the secret. In other words, we are in a situation where we can only use very basic algorithms, and the FFT which saves a factor $N$ when compared to plain exhaustive search over all possible LPN secrets comes in handy here. The low weight parity-check equations are found by using collision techniques which are borrowed from advanced ISD techniques [Dum89, BJMM12].

The improvement upon statistical decoding given by RLPN is really due to this splitting in two parts. Recall that plain statistical decoding uses parity-checks which are low weight on the whole support. In both cases, $\frac{1}{\varepsilon^2}$ of such parity-checks are needed, however in RLPN decoding the bias $\varepsilon$ is way bigger because the weight we have on $\mathcal{N}$ is way smaller for our parity-checks.

**Dual Attacks, Some Negative Results and a New Analysis.** Statistical decoding [Jab01] or its variant, namely RLPN decoding, both fall into the category of dual attacks meaning a decoding algorithm that computes in a first step low weight codewords in the dual code and then computes the inner products of the received word $\mathbf{y}$ with those parity-checks to infer some information about the error $\mathbf{e}$. These methods can be viewed as the coding theoretic analogue of the dual attacks in lattice-based cryptography [MR09]. Similarly to what happened in code-based cryptography, they were shown after a sequence of improvements [Alb17, EJK20, GJ21, MAT22, CST22] to be able of being competitive with primal attacks, and the crucial improvement came from similar techniques, namely by a splitting strategy. Like in RLPN decoding, the point is that this splitting in two parts really allows to find dual vectors that are of smaller weight/norm on the restricted subset. Note that this idea was already put forward for statistical decoding (but not exploited there) in [DT17a, §8, p.33] or [DT17b, p. 21].

However, the analysis in both settings relies on various independence assumptions, see for instance [MAT22, Ass. 4.4, Ass. 5.8] for dual attacks in lattices or [CDMT22, Ass. 3.7] for dual attacks for codes. In lattice-based cryptography, the dual attacks were strongly questioned recently in [DP23b] by showing that these independence assumptions made for analyzing dual attacks were in contradiction with some theorems in certain regimes or with well-tested heuristics in some other regimes. Note that it was already noticed in [CDMT22, §3.4] that the i.i.d. Bernoulli model implied by the LPN model for the $\langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle$'s is not always accurate, but it was conjectured there that the discrepancy between this ideal model and experiments does not impact the asymptotic analysis of the decoding based on this model. This was proved to be wrong in [MT23] where it was shown that the number of candidates passing the validity test of the RLPN decoder given in [CDMT22]
is actually exponentially large for the parameters considered there, whereas there should be only one candidate passing the test if the algorithm was correct. However, this paper gave at the same time an approach for analyzing rigorously dual attacks in coding theory by bringing in a duality equation [MT23, Prop. 1.3] which relates the fundamental quantity manipulated by the decoder and the weight distribution of translates of a shortened version of the code to be decoded. By studying this weight distribution together with an assumption whose validity has been verified experimentally, a slightly modified RLPN decoder was introduced there and shown to attain the complexity exponent claimed in [CDMT22].

## 1.2. Our Contribution.

(i) improving RLPN-decoding by a reduction from sparse LPN to plain LPN,

(ii) a rigorous analysis of the decoding algorithm based on a simple assumption verified experimentally.

**Reduction from Sparse LPN to Plain LPN.** Notice that the LPN problem we have to solve is actually a sparse LPN problem: $\mathcal{E}_{\mathcal{P}}$ is not uniformly distributed among $\mathbb{F}_2^s$ since it is of low weight. Indeed, it is the restriction to $\mathcal{P}$ of a vector which is itself of low weight. Unfortunately, the FFT algorithm used for recovering $\mathcal{E}_{\mathcal{P}}$ is unable to exploit this fact. In a sense, what we need here to improve RLPN decoding is an algorithm for solving sparse secret LPN in the very noisy regime (but with an exponential number of samples). This can be done by using a coded-BKW technique that was introduced in [GJL14]. There it was not used as a technique for solving sparse LPN but as a technique to improve the reduction steps of the BKW algorithm [BKW03] that put together pairs of vectors $\mathbf{a}$ and $\mathbf{a}'$ which are equal on a block of positions and add the corresponding LPN samples to get an LPN sample $(\mathbf{a} + \mathbf{a}', \langle \mathbf{a} + \mathbf{a}', \mathbf{s} \rangle + e + e')$ which is more noisy but with vectors $\mathbf{a}$ which become sparser and sparser as the number of blocks increases. Asking exact collisions on the block needs a lot of LPN samples and this can be relaxed by the coded-BKW technique. It basically uses a code of the same length as the block of positions we are considering during the BKW step and asks only an approximate collision on the block meaning that the closest codewords $\mathbf{c}$ and $\mathbf{c}'$ to $\mathbf{a}$ and $\mathbf{a}'$ restricted to this block should be the same.

To explain what we have in mind here, consider an LPN sample which is of the following form $(\mathbf{h}_{\mathcal{P}}, \langle \mathbf{e}_{\mathcal{P}}, \mathbf{h}_{\mathcal{P}} \rangle + e)$. Choose now a linear code $C_{\text{aux}}$ of length $s$ and dimension $k_{\text{aux}}$ (i.e. a subspace of $\mathbb{F}_2^s$) which we know how to decode for any possible entry, meaning here that we can produce for any entry $\mathbf{y} \in \mathbb{F}_2^s$ a codeword $\mathbf{c}_{\text{aux}} \in C_{\text{aux}}$ which is close enough to $\mathbf{y}$. Codes with this property are known under the name of lossy source codes in information theory. In [GJL14] it was proposed to use for instance a product of small codes. There are almost optimal codes (producing for a given dimension $k_{\text{aux}}$ almost optimal near codewords) using a low complexity decoder. Basically, the best that can be done is to produce codewords at distance $d_{\text{GV}}(s, k_{\text{aux}})$. For instance polar codes are asymptotically optimal [KU10], they attain asymptotically this Gilbert-Varshamov distance by using only a decoding algorithm of quasi-linear complexity $O(s \log s)$.

Consider now a parity-check $\mathbf{h}$ of small weight $w$ on $\mathcal{N}$ that we use for RLPN-decoding and decode $\mathbf{h}_{\mathcal{P}}$ with the lossy source code $C_{\text{aux}}$: $\mathbf{h}_{\mathcal{P}} = \mathbf{c}_{\text{aux}} + \mathbf{e}_{\text{aux}}$ where $\mathbf{c}_{\text{aux}} \in C_{\text{aux}}$ and $|\mathbf{e}_{\text{aux}}|$ is small. Consider a generator matrix $\mathbf{G}_{\text{aux}}$ of $C_{\text{aux}}$, namely a $k_{\text{aux}} \times s$ matrix such that $C_{\text{aux}} = \{\mathbf{u}\mathbf{G}_{\text{aux}} : \mathbf{u} \in \mathbb{F}_2^{k_{\text{aux}}}\}$ (i.e. the rows of $\mathbf{G}_{\text{aux}}$ generate $C_{\text{aux}}$). Notice now that

$$ \begin{aligned} \langle \mathbf{e}_{\mathcal{P}}, \mathbf{h}_{\mathcal{P}} \rangle &= \langle \mathbf{e}_{\mathcal{P}}, \mathbf{c}_{\text{aux}} + \mathbf{e}_{\text{aux}} \rangle = \langle \mathbf{e}_{\mathcal{P}}, \mathbf{c}_{\text{aux}} \rangle + \langle \mathbf{e}_{\mathcal{P}}, \mathbf{e}_{\text{aux}} \rangle \\ &= \langle \mathbf{e}_{\mathcal{P}}, \mathbf{u}\mathbf{G}_{\text{aux}} \rangle + \langle \mathbf{e}_{\mathcal{P}}, \mathbf{e}_{\text{aux}} \rangle \quad (\text{where } \mathbf{u} \in \mathbb{F}_2^{k_{\text{aux}}}) \\ &= \langle \mathbf{e}_{\mathcal{P}}\mathbf{G}_{\text{aux}}^{\top}, \mathbf{u} \rangle + \underbrace{\langle \mathbf{e}_{\mathcal{P}}, \mathbf{e}_{\text{aux}} \rangle}_{\text{biased}}. \end{aligned} $$

If we plug this expression in the original LPN sample $(\mathbf{h}_{\mathcal{P}}, \langle \mathbf{h}, \mathbf{y} \rangle = \langle \mathbf{e}_{\mathcal{P}}, \mathbf{h}_{\mathcal{P}} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle)$ we obtain

$$ \langle \mathbf{h}, \mathbf{y} \rangle = \langle \mathbf{e}_{\mathcal{P}} \mathbf{G}_{\text{aux}}^{\top}, \mathbf{u} \rangle + \underbrace{\langle \mathbf{e}, \mathbf{e}_{\text{aux}} \rangle}_{\text{noise 1}} + \underbrace{\langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle}_{\text{noise 2}}. $$
In other words, we have a new LPN problem where

$$ \underbrace{\mathbf{a}}_{\mathbf{u}}, \overbrace{\langle \mathbf{s}, \mathbf{a} \rangle_{\langle \mathbf{e}_{\mathcal{P}}, \mathbf{G}_{\text{aux}}^{\top}, \mathbf{u} \rangle}}^{\langle \mathbf{y}, \mathbf{h} \rangle} + \underbrace{e}_{\langle \mathbf{e}_{\mathcal{P}}, \mathbf{e}_{\text{aux}} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle} \quad (1) $$

The new secret is not anymore a part $e_{\mathcal{P}}$ of the error but a linear combination $e_{\mathcal{P}}\mathbf{G}_{\text{aux}}^{\top}$ of it and the LPN noise has increased somehow. However, now the secret is way smaller, it belongs to $\mathbb{F}_{2}^{k_{\text{aux}}}$. The situation is changed significantly by this. Before, basically the optimal parameters for RLPN-decoding were such that the cost of FFT decoding the LPN secret, namely $\mathcal{O}(s2^s)$ is of the same order as $1/\epsilon^2$ the number of parity-check equations we need. Here $\epsilon$ is defined by

$$ \mathbb{P}(e=1) = \frac{1-\epsilon}{2}. $$

Recall that $\epsilon$ is basically a decreasing function of the weight $w$ of the parity-check equations we are able to produce. Here since we do not pay anymore $\mathcal{O}(s2^s)$ for FFT decoding the new LPN secret but $\mathcal{O}(k_{\text{aux}}2^{k_{\text{aux}}})$ we can take larger values for $s$ which themselves give a smaller support $\mathcal{N}$ resulting in much smaller weight $w$ on $\mathcal{N}$ and thus the bias term coming from $\langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle$ is much smaller. Of course there is an additional noise term now which is $\langle \mathbf{e}_{\mathcal{P}}, \mathbf{e}_{\text{aux}} \rangle$. However, all in all, the gain we have by being able to use a much larger $s$ outweighs the additional noise term. It can also be observed that we do not recover $e_{\mathcal{P}}$ but $k_{\text{aux}}$ linear combinations of bits of $e_{\mathcal{P}}$. This is easy to fix by running a few times more this algorithm with other lossy source codes $C_{\text{aux}}$ until getting enough linear combinations to be able to recover $e_{\mathcal{P}}$.

We call this new algorithm **double-RLPN-decoding**, since it is based on two successive reductions: first we reduce the problem to sparse-LPN, then we reduce the sparse-LPN to a plain-LPN problem as explained above.

**double-RLPN-Decoding and its Analysis.** It turns out that the LPN problem given in Equation (1) is more structured than a standard LPN problem and like what happened in the RLPN algorithm [CDMT22], producing the most likely candidate for the LPN problem does not necessarily produce the right candidate $e_{\mathcal{P}}\mathbf{G}_{\text{aux}}^{\top}$ even if we have enough samples for ensuring that in the ideal i.i.d model of the LPN problem the most likely candidate would indeed be the right solution. Again, the i.i.d. model is not accurate. We have to use the whole information given by the FFT and output for $L$ big enough the $L$ most likely solutions to have a chance to have $e_{\mathcal{P}}\mathbf{G}_{\text{aux}}^{\top}$ in the list. However, verifying whether a candidate $\mathbf{s}$ for $e_{\mathcal{P}}\mathbf{G}_{\text{aux}}^{\top}$ is indeed valid is relatively straightforward:

(a) we can as in the RLPN algorithm make a bet on the weight $|e_{\mathcal{P}}|$, say $|e_{\mathcal{P}}| = t'$ (and run enough double-RLPN decoding steps until finding a partition $\mathcal{P} \cup \mathcal{N}$ for which this bet is valid),

(b) recover $e_{\mathcal{P}}$ by solving the decoding problem (in its syndrome form) $\mathbf{s} = e_{\mathcal{P}}\mathbf{G}_{\text{aux}}^{\top}$ and $|e_{\mathcal{P}}| = t'$,

(c) check whether the putative candidate $\mathbf{v}$ for $e_{\mathcal{P}}$ we get can be extended to a complete solution by solving the decoding problem $\mathbf{y} = \mathbf{c} + \mathbf{e}$, $e_{\mathcal{P}} = \mathbf{v}$, $\mathbf{c} \in \mathcal{C}$ and $|\mathbf{e}| = t$ which is much easier to solve than the original decoding problem due to the partial knowledge about $\mathbf{e}$, i.e. $e_{\mathcal{P}} = \mathbf{v}$.

The whole problem we face here for analyzing the problem is the same as the one that was faced to analyze the RLPN algorithm, the i.i.d. LPN model is not valid and we really have to get rid of the independence assumptions. Part of this work is achieved by adapting one of the fundamental tools used for analyzing RLPN decoding, namely [CDMT22, Proposition 3.1] which gives a formula of the bias $\epsilon$ in terms of Krawtchouk polynomials. We will obtain a generalization of this proposition adapted to the double-RLPN decoder, namely Proposition 2 in §3. Note that Proposition 2 does not rely on unproven assumptions contrarily to what is done in dual attacks in lattice-based cryptography where the corresponding result is achieved through independence assumptions.
Estimating the number $L$ of candidates for the LPN problem given in Equation (1) we have to keep for being sure to have $e \prec G_{\text{aux}}^L$ is even more delicate. It requires a careful adaptation to our setting of [MT23] that analyzed the RLPN decoder. Here, we will not be able to avoid completely assumptions for performing the analysis (but this was also the case in [MT23]). However, again we will not resort to independence assumptions which seem in our context not only to be wrong strictly speaking, but also to be unable to be good enough for capturing the size of $L$. We will namely develop some tools analogous to what has been achieved in [MT23]:

(i) a duality result, namely Proposition 4 of §5.3, which expresses the FFT value of a candidate as a weighted sum of the product of evaluations of Krawtchouk polynomials where the weights come from a certain weight distributions of codes related to $C$ and $C_{\text{aux}}$. This is an adaptation of [MT23, Prop. 3.2] to our setting and is the key for estimating $L$ as explained in §5.2,

(ii) an estimation of this sum with probabilistic considerations. These probabilistic considerations are rigorous for the part of the sum which is most certainly the dominating term. However for the part of the sum which is very likely to be negligible, we lack accurate tail bounds for the number of codewords of a given weight in a random linear code and in this case we just conjecture that the part of the sum which seems negligible and for which we have only partial control with the probabilistic tool at hand, is indeed negligible. This conjecture has been verified experimentally and we even used a very crude approximation of this weighted sum with the help of independent Poisson variables which captures the size of $L$ obtained in our experiments and which implies our conjecture.

All in all with the help of a conjecture that we verified experimentally, we are able to capture the size of $L$ and to obtain a formula for the complexity of double-RLPN decoding. The key tool for performing this analysis, namely the duality result, can be readily adapted to lattices (see §8). It turns out that even a crude use of this duality result gives a good explanation of the part of the experimental curve departing from the theoretical curve based on the standard independence assumption found in [DP23b, Fig. 3]. This substantiates the claim made in [MT23, §6] that the code duality result of [MT23] carries over to the lattice setting and can be used to predict dual attacks without using the independence assumption.

**The Results Obtained by this New Approach.** This new approach results in a very significant gain compared to RLPN decoding. Our most advanced version of double-RLPN-decoding algorithm performs better than the current state of the art ISD algorithm for all rates $R \le 0.42$ as shown in Figure 1.

**Concurrent/related work.** Very recently, we became aware that the prediction we have made on the score function for lattices by using our duality result and crude estimates of the relevant sum (see §8) has also been obtained by using as we do here Bessel functions and related tools in [DP23a]. This paper provides a much more in depth study as we do here.

## 2. NOTATION AND CODING THEORY BACKGROUND

**Basic Notation.** Vectors and matrices are respectively denoted in bold letters and bold capital letters such as **a** and **A**. The entry at index $i$ of the vector **x** is denoted by $x_i$ or $x(i)$. The canonical inner product $\sum_{i=1}^n x_i y_i$ between two vectors **x** and **y** of $\mathbb{F}_2^n$ is denoted by $\langle \mathbf{x}, \mathbf{y} \rangle$ where $\mathbb{F}_2$ denotes the binary field. Let $\mathcal{I}$ be a list of indexes. We denote by $\mathbf{x}_{\mathcal{I}}$ the vector $(x_i)_{i \in \mathcal{I}}$. In the same way, we denote by $\mathbf{A}_{\mathcal{I}}$ the sub-matrix made of the columns of **A** which are indexed by $\mathcal{I}$. We denote by $\mathbf{0}_n \in \mathbb{F}_2^{n \times n}$ and $\mathbf{I}\mathbf{d}_n \in \mathbb{F}_2^{n \times n}$ the null matrix and the identity matrix of size $n$ respectively. The concatenation of two vectors **x** and **y** is denoted by $\mathbf{x}||\mathbf{y}$. The Hamming weight of a vector **x** and the cardinality of a finite set $\mathcal{A}$ are denoted in the same way by $|\mathbf{x}|$ and $|\mathcal{A}|$ respectively. There will be no confusion since they apply to different objects. Notation $\llbracket a, b \rrbracket$ stands for the set of the integers between $a$ and $b$, both included. Furthermore, we let $S_w^n$ denote the Hamming sphere of $\mathbb{F}_2^n$ with radius $w$ and centered at **0**, namely

$$S_w^n \stackrel{\text{def}}{=} \{ \mathbf{x} \in \mathbb{F}_2^n : |\mathbf{x}| = w \}.$$
<figure><img src="image_3.png" /><figcaption>FIGURE 1. Asymptotic complexity exponent of some decoding algorithms: our new double-RLPN decoder, the RLPN decoder, Both and May algorithm [BM18] (with the correction of [CDMT22, Ess22]) which is the state-of-the-art of ISD decoders and the Prange decoder [Pra62].</figcaption></figure>

**Probabilistic Notation.** For a finite set $\mathcal{S}$, we write $X \stackrel{\mathcal{S}}{\leftarrow} \mathcal{S}$ when $X$ is an element of $\mathcal{S}$ drawn uniformly at random in it. For a Bernoulli random variable $X$, denote by $\text{bias}(X)$ the quantity

$$ \text{bias}(X) \stackrel{\text{def}}{=} \mathbb{P}(X = 0) - \mathbb{P}(X = 1). $$

For a Bernoulli random variable $X$ of parameter $p = \frac{1-\epsilon}{2}$, i.e. $\mathbb{P}(X = 1) = \frac{1-\epsilon}{2}$, we have $\text{bias}(X) = \epsilon$.

**Fourier Transform.** Let $f: \mathbb{F}_2^n \to \mathbb{R}$ be a function. We define its Fourier transform $\hat{f}: \mathbb{F}_2^n \to \mathbb{R}$ as

$$ \hat{f}(\mathbf{x}) = \sum_{\mathbf{u} \in \mathbb{F}_2^n} f(\mathbf{u}) (-1)^{\langle \mathbf{x}, \mathbf{u} \rangle}. \qquad (2) $$

**Soft-O Notation.** For real valued functions defined over $\mathbb{R}$ or $\mathbb{N}$ we define $o(\cdot)$, $O(\cdot)$, $\Omega(\cdot)$, $\Theta(\cdot)$, in the usual way and also use the less common notation $\tilde{O}(\cdot)$ and $\tilde{\Omega}(\cdot)$, where $f = \tilde{O}(g)$ means that $f(x) = O(g(x) \log^k g(x))$ and $f = \tilde{\Omega}(g)$ means that $f(x) = \Omega(g(x) \log^k g(x))$ for some $k$. We will use this for functions which have an exponential behavior, say $g(x) = e^{\alpha x}$, in which case $f(x) = \tilde{O}(g(x))$ means that $f(x) = O(P(x)g(x))$ where $P$ is a polynomial in $x$. We also use $f = \omega(g)$ when $f$ dominates $g$ asymptotically; that is when $\lim_{x \to \infty} \frac{|f(x)|}{g(x)} = \infty$.

**Coding Theory.** A binary linear code $\mathcal{C}$ of length $n$ and dimension $k$ is a subspace of $\mathbb{F}_2^n$ of dimension $k$. We say that it has parameters $[n, k]$ or that it is an $[n, k]$-code. Its rate $R$ is defined as $R \stackrel{\text{def}}{=} \frac{k}{n}$. A generator matrix $\mathbf{G}$ for $\mathcal{C}$ is a full rank $k \times n$ matrix over $\mathbb{F}_2$ such that

$$ \mathcal{C} = \{ \mathbf{u}\mathbf{G} : \mathbf{u} \in \mathbb{F}_2^k \}. $$

A parity-check matrix $\mathbf{H}$ for $\mathcal{C}$ is a full-rank $(n-k) \times n$ matrix over $\mathbb{F}_2$ such that

$$ \mathcal{C} = \{ \mathbf{c} \in \mathbb{F}_2^n : \mathbf{H}\mathbf{c}^{\top} = \mathbf{0} \}. $$
In other words, $\mathcal{C}$ is the null space of $\mathbf{H}$. The dimension of the code is given by $\dim(\mathcal{C}) \stackrel{\text{def}}{=} k$. The code whose generator matrix is the parity-check matrix of $\mathcal{C}$ is called the dual code of $\mathcal{C}$. It might be seen as the subspace of parity-checks of $\mathcal{C}$ and is defined equivalently as

**Definition 1 (Dual Code).** The dual code $\mathcal{C}^{\perp}$ of an $[n, k]$-code $\mathcal{C}$ is an $[n, n-k]$-code which is defined by

$$ \mathcal{C}^{\perp} \stackrel{\text{def}}{=} \{\mathbf{h} \in \mathbb{F}_2^n : \forall \mathbf{c} \in \mathcal{C}, \langle \mathbf{c}, \mathbf{h} \rangle = 0\}. $$

Sometimes it is considered in the literature the following equivalent version of the decoding problem (see Problem 3 as defined in the introduction) by using instead the parity-check matrix and syndrome point of view

**Problem 3 (Decoding a fixed error weight via syndromes).** Let $\mathcal{C}$ be an $[n, k]$-code with parity-check matrix $\mathbf{H} \in \mathbb{F}_2^{(n-k) \times n}$. We are given a syndrome $\mathbf{s} \in \mathbb{F}_2^{n-k}$, an integer $t$ and we want to find an error vector $\mathbf{e} \in \mathbb{F}_2^n$ of Hamming weight $|\mathbf{e}| = t$ for which $\mathbf{H}\mathbf{e}^{\top} = \mathbf{s}^{\top}$.

It is readily seen that both Problems 1 and 3 are equivalent: given $\mathcal{C}$ with parity-check matrix $\mathbf{H}$, then decoding $\mathbf{c}+\mathbf{e}$ with a codeword $\mathbf{c} \in \mathcal{C}$ and $\mathbf{e} \in S_t^n$ amounts to recover $\mathbf{e}$ from $\mathbf{H}\mathbf{y}^{\top} = \mathbf{H}\mathbf{e}^{\top}$ as by definition $\mathbf{H}\mathbf{c}^{\top} = \mathbf{0}$.

When $\mathcal{C}$ is an $[n, k]$-code and $\mathbf{x} \in \mathbb{F}_2^n$ we let

$$ \mathcal{C} + \mathbf{x} \stackrel{\text{def}}{=} \{\mathbf{c} + \mathbf{x}, \mathbf{c} \in \mathcal{C}\} $$

denote a coset of $\mathcal{C}$ and we denote by $N_i(\mathcal{C} + \mathbf{x})$ the number of words of hamming weight $i$ in the coset $\mathcal{C} + \mathbf{x}$, namely

$$ N_i(\mathcal{C} + \mathbf{x}) \stackrel{\text{def}}{=} |\mathcal{C} + \mathbf{x} \cap S_i^n|. $$

An important quantity is the *Gilbert-Varshamov distance* which is defined as

**Definition 2 (Gilbert-Varshamov distance).** The Gilbert-Varshamov distance $d_{\text{GV}}(n, k)$ associated to a length $n$ and dimension $k$ is defined as the largest integer $d$ such that

$$ 2^k |\mathcal{B}_d| < 2^n $$

where $\mathcal{B}_d$ is the Hamming ball centered at $\mathbf{0}$ in $\mathbb{F}_2^n$ and radius $d$, that is $\mathcal{B}_d \stackrel{\text{def}}{=} \{\mathbf{x} \in \mathbb{F}_2^n : |\mathbf{x}| \le d\}$.

This quantity has two different interpretations. On one hand, it corresponds up to a constant term to the typical minimum distance of a linear code of length $n$ and dimension $k$, but it is also related to the expected number of solutions of the decoding problem for a random linear $[n, k]$-code which is defined as follows.

**Problem 4** ((n, k, t) Decoding Problem - DP(n, k, t)).

* Given: $(\mathbf{G}, \mathbf{y} \stackrel{\text{def}}{=} \mathbf{m}\mathbf{G} + \mathbf{x})$ where $\mathbf{m}, \mathbf{G}$ and $\mathbf{x}$ are respectively picked uniformly at random over $\mathbb{F}_2^k, \mathbb{F}_2^{k \times n}$ and $S_t^n$.

* Aim: an error $\mathbf{e} \in \mathbb{F}_2^n$ of Hamming weight $t$ such that $\mathbf{y} - \mathbf{e} = \mathbf{z}\mathbf{G}$ for some $\mathbf{z} \in \mathbb{F}_2^k$.

This problem really corresponds to decoding at distance $t$ the $[n, k]$-code admitting $\mathbf{G}$ as generator matrix. The largest weight $t$ for which we might hope for having a single solution (strictly speaking when we look for solutions of weight $\le t$ and not exactly $t$, but the difference between these two notions is generally irrelevant) is given by the Gilbert-Varshamov distance $d_{\text{GV}}(n, k)$. At this distance, the expected number of solutions is readily seen to be $\Theta(1)$ whether we look at codewords at distance exactly $t$ from the received word $\mathbf{y}$ or at distance $\le t$.

It will also be very convenient to consider the operation of puncturing a code, i.e. keeping only a subset of entries in a codeword.

**Definition 3 (Punctured Code).** For a code $\mathcal{C}$ and a subset $\mathcal{I}$ of code positions, we denote by $\mathcal{C}_{\mathcal{I}}$ the punctured code obtained from $\mathcal{C}$ by keeping only the positions in $\mathcal{I}$, i.e.

$$ \mathcal{C}_{\mathcal{I}} = \{\mathbf{c}_{\mathcal{I}} : \mathbf{c} \in \mathcal{C}\}. $$
**Definition 4** (Shortened Code). For a code $\mathcal{C}$ and a subset $\mathcal{J}$ of code positions, we denote by $\mathcal{C}^{\mathcal{J}}$ the shortened code is defined by

$$ \mathcal{C}^{\mathcal{J}} = \{ \mathbf{c}_{\mathcal{J}} : \mathbf{c} \in \mathcal{C} \text{ and } \mathbf{c}_{[1,n]} \setminus \mathcal{J} = \mathbf{0} \}. $$

It is readily seen that we have

$$ (\mathcal{C}^{\mathcal{J}})^{\perp} = (\mathcal{C}^{\perp})_{\mathcal{J}}, \quad \text{and} \quad (\mathcal{C}_{\mathcal{J}})^{\perp} = (\mathcal{C}^{\perp})^{\mathcal{J}}. \qquad (3) $$

**Krawtchouk Polynomial.** We recall here some properties about Krawtchouk polynomial that will be useful in the article. Many useful properties can be found in [KS21, §2.2]

**Definition 5.** (Krawtchouk polynomial) We define the Krawtchouk polynomial $K_w^{(n)}$ of degree $w$ and of order $n$ as

$$ K_w^{(n)}(X) \stackrel{\text{def}}{=} \sum_{j=0}^{w} (-1)^j \binom{X}{j} \binom{n-X}{w-j}. $$

The following fact is well known: it gives an alternate expression of the Krawtchouk polynomial (see for instance [vL99, Lemma 5.3.1]).

**Fact 1.** For any $\mathbf{x} \in \mathbb{F}_2^n$,

$$ K_w^{(n)}(|\mathbf{x}|) = \widehat{1}_w(\mathbf{x}) = \sum_{\mathbf{y} \in \mathbb{F}_2^n : |\mathbf{y}|=w} (-1)^{\langle \mathbf{x}, \mathbf{y} \rangle}. \qquad (4) $$

where $\widehat{1}_w$ is the characteristic function of the Hamming sphere $S_w^n$ of radius $w$.

We recall here the summary of some known results about Krawtchouk polynomials made in [CDMT22].

**Proposition 1.** [CDMT22, Prop. 3.5, Prop. 3.6]

(1) **Value at 0.** For all $0 \le w \le n$, $K_w^{(n)}(0) = \binom{n}{w}$.

(2) **Reciprocity.** For all $0 \le t, w \le n$, $\binom{n}{t} K_w^{(n)}(t) = \binom{n}{w} K_t^{(n)}(w)$.

(3) **Roots.** The polynomials $K_w^{(n)}$'s have $w$ distinct roots which lie in the interval $[n/2 - \sqrt{w(n-w)}, n/2 + \sqrt{w(n-w)}]$. The distance between roots is at least 2 and at most $o(n)$.

(4) **Magnitude in and out the root region.** Let $\tau$ and $\omega$ be two reals in $[0, 1]$. Let $\omega^{\perp} \stackrel{\text{def}}{=} \frac{1}{2} - \sqrt{\omega(1-\omega)}$, and let $z \stackrel{\text{def}}{=} \frac{1-2\tau-\sqrt{D}}{2(1-\omega)}$ where $D \stackrel{\text{def}}{=} (1-2\tau)^2 - 4\omega(1-\omega)$.

$$ \text{Define } \tilde{\kappa}(\tau, \omega) \stackrel{\text{def}}{=} \begin{cases} \tau \log_2(1-z) + (1-\tau) \log_2(1+z) - \omega \log_2 z & \text{if } \tau \in [0, \omega^{\perp}], \\ \frac{1-h(\tau)+h(\omega)}{2} & \text{otherwise.} \end{cases} $$

• 4.1. If $\tau \le \frac{1}{2} - \sqrt{\omega(1-\omega)}$, then for all $t$ and $w$ such that $\lim_{n \to \infty} \frac{t}{n} = \tau$ and $\lim_{n \to \infty} \frac{w}{n} = \omega$ we have $K_w^{(n)}(t) = 2^{n(\tilde{\kappa}(\tau,\omega)+o(1))}$.

• 4.2. If $\tau > \frac{1}{2} - \sqrt{\omega(1-\omega)}$, then there exists $t(n)$ and $w(n)$ such that $\lim_{n \to \infty} \frac{t}{n} = \tau$, $\lim_{n \to \infty} \frac{w}{n} = \omega$ and $|K_w^{(n)}(t)| = 2^{n(\tilde{\kappa}(\tau,\omega)+o(1))}$.

### 3. REDUCTION FROM SPARSE TO PLAIN LPN

The purpose of this section is to explain in detail the reduction from sparse to plain LPN and to give an important result about the bias of the resulting RLPN samples. We assume from now on that we are given and $[n, k]$-code $\mathcal{C}$ and a $\mathbf{y} \in \mathbb{F}_2^n$ such that

$$ \mathbf{y} \stackrel{\text{def}}{=} \mathbf{c} + \mathbf{e}, \quad \mathbf{c} \in \mathcal{C}, \quad |\mathbf{e}| = t, $$

and we want to find $\mathbf{c}$ and $\mathbf{e}$.
3.1. **The Approach.** First, we randomly select a subset $\mathcal{P} \subseteq [1, n]$ of $s$ positions, where $s$ is a parameter that will be chosen later. Let $\mathcal{N} \stackrel{\text{def}}{=} [1, n] \setminus \mathcal{P}$ be the complementary set of $\mathcal{P}$. Here $\mathcal{P}$ corresponds to the entries of $\mathbf{e}$ we aim to recover. As explained in the introduction, the basic step of the decoding algorithm is to compute a large set $\mathcal{W}$ of parity-check equations of low weight $w$ on $\mathcal{N}$ and to compute all the $\langle \mathbf{y}, \mathbf{h} \rangle$ with $\mathbf{h}$ ranging over $\mathcal{W}$. In RLPN decoding, the approach is to exploit directly that we have a number $|\mathcal{W}|$ of LPN samples $(\mathbf{h}_{\mathcal{P}}, \langle \mathbf{h}, \mathbf{y} \rangle)$ which can be viewed as an LPN sample $(\mathbf{a}, \langle \mathbf{a}, \mathbf{s} \rangle + e)$ by letting $\mathbf{a} \stackrel{\text{def}}{=} \mathbf{h}_{\mathcal{P}}, \mathbf{s} \stackrel{\text{def}}{=} \mathbf{e}_{\mathcal{P}}, e \stackrel{\text{def}}{=} \langle \mathbf{h}_{\mathcal{N}}, \mathbf{e}_{\mathcal{N}} \rangle$. Indeed,

$$ \langle \mathbf{h}, \mathbf{y} \rangle = \langle \mathbf{h}, \mathbf{c} + \mathbf{e} \rangle = \underbrace{\langle \mathbf{h}, \mathbf{c} \rangle}_{=0} + \langle \mathbf{h}, \mathbf{e} \rangle = \underbrace{\langle \mathbf{h}_{\mathcal{P}}, \mathbf{e}_{\mathcal{P}} \rangle}_{=\langle \mathbf{a}, \mathbf{s} \rangle} + \underbrace{\langle \mathbf{h}_{\mathcal{N}}, \mathbf{e}_{\mathcal{N}} \rangle}_{\text{LPN noise } e} $$

Notice that we really have a sparse LPN problem because of the sparseness of the secret $\mathbf{e}_{\mathcal{P}}$ which is not exploited in [CDMT22] and only exploited to verify the solution in the corrected RLPN algorithm of [MT23]. The point of this article is to exploit the sparseness of $\mathbf{e}_{\mathcal{P}} \in \mathbb{F}_2^s$ right away in order to reduce the dimension $s$ of the secret. This is obtained by introducing an auxiliary code $C_{\text{aux}}$ of length $s$ and dimension $k_{\text{aux}}$ which will be instrumental for reducing the dimension $s$ of the secret down to $k_{\text{aux}}$. This is obtained as follows. We will assume that $C_{\text{aux}}$ is chosen as a code with an *efficient list-decoding procedure* at distance $t_{\text{aux}}$.

**Definition 6** (Efficiently list decodable code). A code $C$ of length $n$ is said to be efficiently decodable code at distance $t$ if it outputs for any $\mathbf{y} \in \mathbb{F}_2^n$ a non empty list of codewords of $C$ at distance $t$ in time $2^{o(n)}$.

Moreover from now on, we assume that

**Notation 1.** $C_{\text{aux}}$ is an $[s, k_{\text{aux}}]$ efficiently list decodable for some distance $t_{\text{aux}}$. We denote by $\text{Dec}(\mathbf{z})$ the set of all codewords of $C_{\text{aux}}$ at distance $t_{\text{aux}}$ from $\mathbf{z} \in \mathbb{F}_2^s$, namely

$$ \text{Dec}(\mathbf{z}) = \{ \mathbf{c}_{\text{aux}} \in C_{\text{aux}} : |\mathbf{c}_{\text{aux}} + \mathbf{z}| = t_{\text{aux}} \}. $$

**Remark 1.** In our instantiation, $t_{\text{aux}}$ is chosen such that $t_{\text{aux}} \approx d_{\text{GV}}(s, k_{\text{aux}})$, thus we typically have $|\text{Dec}(\mathbf{h}_{\mathcal{P}})| = \Theta(1)$.

Now, let us consider $\mathbf{c}_{\text{aux}} \in \text{Dec}(\mathbf{h}_{\mathcal{P}})$, a codeword of $C_{\text{aux}}$ at distance $t_{\text{aux}}$ of $\mathbf{h}_{\mathcal{P}}$. It is readily seen that $\langle \mathbf{y}, \mathbf{h} \rangle$ decomposes as:

$$ \langle \mathbf{y}, \mathbf{h} \rangle = \underbrace{\langle \mathbf{e}_{\mathcal{P}}, \mathbf{c}_{\text{aux}} \rangle}_{\text{linear comb.}} + \underbrace{\langle \mathbf{e}_{\mathcal{P}}, \mathbf{h}_{\mathcal{P}} + \mathbf{c}_{\text{aux}} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle}_{\text{"new" LPN noise}} $$

Let us start by defining $C_{\text{aux}}$ with a generator matrix $\mathbf{G}_{\text{aux}} \in \mathbb{F}_2^{s \times k_{\text{aux}}}$ . Then, knowing $\mathbf{c}_{\text{aux}} \in C_{\text{aux}}$ is equivalent to know $\mathbf{m}_{\text{aux}} \in \mathbb{F}_2^{k_{\text{aux}}}$ such that

$$ \mathbf{c}_{\text{aux}} = \mathbf{m}_{\text{aux}} \mathbf{G}_{\text{aux}}. $$

We can therefore rewrite $\langle \mathbf{e}_{\mathcal{P}}, \mathbf{c}_{\text{aux}} \rangle$ as

$$ \langle \mathbf{e}_{\mathcal{P}}, \mathbf{c}_{\text{aux}} \rangle = \langle \mathbf{e}_{\mathcal{P}}, \mathbf{m}_{\text{aux}} \mathbf{G}_{\text{aux}} \rangle = \langle \mathbf{e}_{\mathcal{P}} \mathbf{G}_{\text{aux}}^{\top}, \mathbf{m}_{\text{aux}} \rangle. $$

We have therefore for each parity-check equation $\mathbf{h}$ of weight $w$ on $\mathcal{N}$ that we have computed (i.e. for all $\mathbf{h} \in \mathcal{W}$) and each codeword $\mathbf{m}_{\text{aux}} \mathbf{G}_{\text{aux}}$ of $C_{\text{aux}}$ at distance $t_{\text{aux}}$ from $\mathbf{h}_{\mathcal{P}}$, an LPN sample $(\mathbf{m}_{\text{aux}}, \langle \mathbf{y}, \mathbf{h} \rangle)$ which can be viewed as such by noticing that it is indeed equal to

$$ (\mathbf{a}, \langle \mathbf{a}, \mathbf{s} \rangle + e) \quad \text{with} \quad \left\{ \begin{array}{l} \mathbf{a} \stackrel{\text{def}}{=} \mathbf{m}_{\text{aux}} \\ \mathbf{s} \stackrel{\text{def}}{=} \mathbf{e}_{\mathcal{P}} \mathbf{G}_{\text{aux}}^{\top} \\ e \stackrel{\text{def}}{=} \langle \mathbf{e}_{\mathcal{P}}, \mathbf{h}_{\mathcal{P}} + \mathbf{c}_{\text{aux}} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle \end{array} \right. \qquad (5) $$

Notice here that, if $\text{Dec}(\mathbf{h}_{\mathcal{P}})$ contains more than one element, we can compute such LPN samples for each different $\mathbf{c}_{\text{aux}} \in \text{Dec}(\mathbf{h}_{\mathcal{P}})$. The secret in the above LPN sample is no longer given by $\mathbf{e}_{\mathcal{P}}$ that we want to recover (contrarily to RLPN-decoding [CDMT22]), but is given by $\mathbf{e}_{\mathcal{P}} \mathbf{G}_{\text{aux}}^{\top} \in \mathbb{F}_2^{k_{\text{aux}}}$ which are $k_{\text{aux}} < s$ linear equations involving the $s = |\mathcal{P}|$ bits of the vector $\mathbf{e}$ we are looking for.
The main advantage of our new technique is that we end up with an LPN problem whose dimension of the secret has decreased from $s$ to $k_{aux}$. However, the noise has increased; let us describe how it behaves in the following paragraph.

**3.2. Estimating the New Noise.** The error $e$ in Equation (5) is biased toward zero and its bias is a function of $n, s, t$ and $u, w, t_{aux}$ which are respectively

$$u \stackrel{\text{def}}{=} |\mathbf{e}_{\mathcal{N}}|, \quad w \stackrel{\text{def}}{=} |\mathbf{h}_{\mathcal{N}}| \quad \text{and} \quad t_{aux} \stackrel{\text{def}}{=} |\mathbf{h}_{\mathcal{P}} + \mathbf{c}_{aux}|.$$

In the following statement we compute the bias of $e$ over all the possible LPN samples, that is we compute

$$\text{bias}_{(\mathbf{h}, \mathbf{c}_{aux}) \stackrel{\text{def}}{\leftarrow} \tilde{\mathcal{H}}} (\langle \mathbf{e}_{\mathcal{P}}, \mathbf{h}_{aux} + \mathbf{c}_{aux} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle) = \frac{1}{|\tilde{\mathcal{H}}|} \sum_{(\mathbf{h}, \mathbf{c}_{aux}) \in \tilde{\mathcal{H}}} (-1)^{\langle \mathbf{e}_{\mathcal{P}}, \mathbf{h}_{\mathcal{P}} + \mathbf{c}_{aux} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle}$$

where $\tilde{\mathcal{H}}$ is defined by

**Definition 7.**

$$\tilde{\mathcal{H}} \stackrel{\text{def}}{=} \{(\mathbf{h}, \mathbf{c}_{aux}) \in \mathcal{C}^{\perp} \times \mathcal{C}_{aux} : |\mathbf{h}_{\mathcal{N}}| = w \text{ and } |\mathbf{h}_{\mathcal{P}} + \mathbf{c}_{aux}| = t_{aux}\}. \quad (6)$$

It is tempting to conjecture that this bias is well approximated by the bias of a Bernoulli variable $X \stackrel{\text{def}}{=} \langle \mathbf{e}_{\mathcal{P}}, \mathbf{e}_{aux} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{w} \rangle$ where $\mathbf{e}_{aux}$ and $\mathbf{w}$ are respectively drawn uniformly at random in the Hamming spheres $S_{t_{aux}}^s$ and $S_w^{n-s}$. The sum $\langle \mathbf{e}_{\mathcal{P}}, \mathbf{e}_{aux} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{w} \rangle$ is performed over $\mathbb{F}_2$ and all the vectors are independent random variables. Because of the independence of the random variables, from the straightforward fact that $\text{bias}(X_1 + X_2) = \text{bias}(X_1)\text{bias}(X_2)$ when $X_1$ and $X_2$ are independent Bernoulli variables (and the addition is performed modulo 2). Therefore,

$$\begin{aligned} \text{bias}(X) &= \text{bias}(\langle \mathbf{e}_{\mathcal{P}}, \mathbf{e}_{aux} \rangle) \text{bias}(\langle \mathbf{e}_{\mathcal{N}}, \mathbf{w} \rangle) \\ &= \frac{K_{t_{aux}}^{(s)}(t-u) K_w^{(n-s)}(u)}{\binom{s}{t_{aux}}} \frac{K_w^{(n-s)}(u) K_{t_{aux}}^{(s)}}{\binom{n-s}{w}} \quad (\text{by Fact 1}). \end{aligned}$$

This kind of approximation was done in the early days of statistical decoding [Jab01, Ove06, DT17c], until [CDMT22, Prop. 3.1] which has shown that under certain conditions, i.e. when there are enough available parity-check equations of weight $w$ (essentially when the number is of order $\omega(1/\delta^2)$ where $\delta$ is the bias), then this approximation can indeed be shown to hold with overwhelming probability. It turns out that [CDMT22, Prop. 3.1] can be adapted to our setting with some additional technicalities and conditions. It can be shown that with overwhelming probability we indeed have

$$\text{bias}_{(\mathbf{h}, \mathbf{c}_{aux}) \stackrel{\text{def}}{\leftarrow} \tilde{\mathcal{H}}} (\langle \mathbf{e}_{\mathcal{P}}, \mathbf{h}_{\mathcal{P}} + \mathbf{c}_{aux} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle) = (1 + o(1)) \text{bias}(X).$$

This is in essence what the following proposition shows.

**Proposition 2.** Suppose that the parameters are such that for some constant $\alpha > 0$

$$\frac{\binom{n-s}{w} \binom{s}{t_{aux}}}{2^{k-k_{aux}}} = \omega\left(\frac{n^{\alpha}}{\delta^2}\right) \quad \text{where} \quad \delta \stackrel{\text{def}}{=} \frac{K_w^{(n-s)}(u) K_{t_{aux}}^{(s)}(t-u)}{\binom{n-s}{w} \binom{s}{t_{aux}}}. \quad (7)$$

Moreover suppose that

$$\frac{\binom{n-s}{w} \binom{s}{t_{aux}}}{2^k} = \mathcal{O}(n^\alpha) \quad \text{and} \quad \frac{\binom{s}{t_{aux}}}{2^{s-k_{aux}}} = \mathcal{O}(n^\alpha). \quad (8)$$

Let $\mathcal{N}$ be a set of $n-s$ positions in $\llbracket 1, n \rrbracket$ and $\mathcal{P} \stackrel{\text{def}}{=} \llbracket 1, n \rrbracket \setminus \mathcal{N}$. Let $\mathbf{e}$ be a vector of weight $u$ on $\mathcal{N}$ and $t-u$ on $\mathcal{P}$. Let $\mathcal{C}$ and $\mathcal{C}_{aux}$ be $[n, k]$ and $[s, k_{aux}]$ linear codes respectively. Let us choose $(\mathbf{c}_{aux}, \mathbf{h})$ uniformly at random in

$$\tilde{\mathcal{H}} = \{(\mathbf{h}, \mathbf{c}_{aux}) \in \mathcal{C}^{\perp} \times \mathcal{C}_{aux} : |\mathbf{h}_{\mathcal{N}}| = w \text{ and } |\mathbf{h}_{\mathcal{P}} + \mathbf{c}_{aux}| = t_{aux}\}.$$
Then for a proportion $1 - o(1)$ of codes $C_{aux}$ and $C$ we have that

$$ \text{bias}_{(h, c_{aux})} \stackrel{\$}{\leftarrow} \mathcal{H} \left( \langle \mathbf{c}_{aux} + \mathbf{h}_{\mathcal{P}}, \mathbf{e}_{\mathcal{P}} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle \right) = \delta(1 + o(1)). $$

*Proof.* See Appendix §A.

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

## 4. THE double-RLPN ALGORITHM

We first going to explain the four main ingredients of the double-RLPN algorithm:

* computing suitable LPN samples,

* FFT decoding,

* recovering $\mathbf{e}_{\mathcal{P}}$,

* the bet ensuring that there are $u$ errors on $\mathcal{N}$ at some point.

Let us detail each of these ingredients (or steps of the algorithm).

**Computing the LPN Samples.** First, our algorithm computes a certain number of LPN samples by computing a set $\mathcal{W}$ of elements of $C^{\perp}$ of weight $w$ on $\mathcal{N}$ by using a procedure ParityCheckEquations($w, \mathcal{N}, C$) that uses low-weight codewords search techniques to produce a bunch of parity-check equations of $C$ of weight $w$ on $\mathcal{N}$. Then a random code $C_{aux}$ is chosen in a family of codes over $\mathbb{F}_2^{\mathcal{P}}$ and dimension $k_{aux}$ that we know how to decode efficiently at distance $t_{aux}$. For an element $\mathbf{h}$ in $\mathcal{W}$, each $\mathbf{h}_{\mathcal{P}}$ is decoded at distance $t_{aux}$ to finally compute the set $\mathcal{H}$ containing pairs $(\mathbf{h}, c_{aux})$ in $\mathcal{W} \times C_{aux}$ satisfying $|\mathbf{h}_{\mathcal{N}}| = w$ and $|\mathbf{h}_{\mathcal{P}} + c_{aux}| = t_{aux}$. Algorithm 1 gives the pseudo-code of the procedure.

**Algorithm 1** The function computing the LPN samples associated to $\mathcal{N}$

1: **function** LPN-SAMPLES($C, \mathcal{N}$)

2: $\mathcal{P} \leftarrow [1, n] \setminus \mathcal{N}$

3: $\mathcal{W} \leftarrow \text{PARITYCHECKEQUATIONS}(w, \mathcal{N}, C) \triangleright \text{returns a set of parity-check equations of } C$ of weight $w$ on $\mathcal{N}$

4: $C_{aux} \stackrel{\$}{\leftarrow} \mathcal{F}(\mathcal{P}, k_{aux}, t_{aux}) \triangleright \text{returns a code } C_{aux} \text{ in a family of codes } \mathcal{F} \text{ over } \mathbb{F}_2^{\mathcal{P}} \text{ and dimension } k_{aux} \text{ that we know how to decode efficiently at distance } t_{aux}$

5: $\mathcal{H} \leftarrow \emptyset$

6: **for all** $\mathbf{h} \in \mathcal{H}$ **do**

7: $\mathcal{H} \leftarrow \mathcal{H} \cup \{\mathbf{h}\} \times \text{DECODE}(\mathbf{h}_{\mathcal{P}}, C_{aux}, t_{aux}) \triangleright \text{DECODE}(\mathbf{h}_{\mathcal{P}}, C_{aux}, t_{aux})$ outputs a set of codewords of $C_{aux}$ at distance $t_{aux}$ of $\mathbf{h}_{\mathcal{P}}$

8: **end for**

9: $\mathbf{G}_{aux} \leftarrow \text{generating matrix of } C_{aux}$

10: **return** $(\mathcal{H}, \mathbf{G}_{aux})$

11: **end function**

**FFT Decoding.** Computing $\mathcal{H}$ gives a number $|\mathcal{H}|$ of LPN samples, which from the interpretation given in Equation (5), leads us to think that the right choice $\mathbf{x} \in \mathbb{F}_2^{k_{aux}}$ for $\mathbf{e}_{\mathcal{P}}\mathbf{G}_{aux}^{\top}$ is the one for which

$$ \text{bias}_{(h, m_{aux}, \mathbf{G}_{aux})} \stackrel{\$}{\leftarrow} \mathcal{H} \left( \langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{m}_{aux} \rangle \right) $$

would be given by Proposition 2. It should namely be of order $\delta$ which is defined in this proposition. Natural candidates for being equal to $\mathbf{e}_{\mathcal{P}}\mathbf{G}_{aux}^{\top}$ are those for which this bias is say $\ge \delta/2$. This leads to compute all those biases. This can be done rather efficiently by factoring the common computations made for computing all those biases for $\mathbf{x} \in \mathbb{F}_2^{k_{aux}}$ by an FFT trick which is standard in the LPN context. It dates back in this context to [LF06], but it can be traced back to decoding the first-order Reed-Muller code (which is another way to view the decoding task in case of the LPN problem) which was already suggested in [Gre66]. The link between the bias of the
random variables we are interested in and the Fourier transform is based on the following simple observation that follows right away from the very definition of the Fourier transform. Before we give this observation, let us bring in a notation that will be helpful for describing it and which will be used throughout the paper from now on.

**Notation 2.** For any $\mathbf{y} \in \mathbb{F}_2^n$, $\mathcal{H} \subseteq \mathcal{C}^\perp \times \mathcal{C}_{\text{aux}}$ and a generator matrix $\mathbf{G}_{\text{aux}}$ of $\mathcal{C}_{\text{aux}}$ we define the function $f_{\mathbf{y},\mathcal{H},\mathbf{G}_{\text{aux}}}$ on $\mathbb{F}_2^{k_{\text{aux}}}$ by

$$ f_{\mathbf{y},\mathcal{H},\mathbf{G}_{\text{aux}}} : \mathbb{F}_2^{k_{\text{aux}}} \to \mathbb{R} \\ \mathbf{u} \mapsto \begin{cases} \sum_{\mathbf{h}: (\mathbf{h},\mathbf{u}\mathbf{G}_{\text{aux}}) \in \mathcal{H}} (-1)^{\langle \mathbf{y}, \mathbf{h} \rangle} & \text{if this sum is not empty,} \\ 0 & \text{otherwise.} \end{cases} \tag{9} $$

With this notation at hand, the link between the biases and the Fourier transform of this function is given by the following lemma.

**Lemma 1.** We have for any $\mathbf{u} \in \mathbb{F}_2^{k_{\text{aux}}}$ and any $\mathbf{x} \in \mathbb{F}_2^s$ such that $\mathbf{x}\mathbf{G}_{\text{aux}}^\top = \mathbf{u}$

$$ \begin{aligned} f_{\mathbf{y},\mathcal{H},\mathbf{G}_{\text{aux}}} (\mathbf{u}) &= |\mathcal{H}| \quad \underset{(\mathbf{h},\mathbf{m}_{\text{aux}}\mathbf{G}_{\text{aux}}) \stackrel{\$}{\leftarrow} \mathcal{H}}{\text{bias}} (\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{u}, \mathbf{m}_{\text{aux}} \rangle) \\ &= |\mathcal{H}| \quad \underset{(\mathbf{h},\mathbf{c}_{\text{aux}}) \stackrel{\$}{\leftarrow} \mathcal{H}}{\text{bias}} (\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{c}_{\text{aux}} \rangle). \end{aligned} $$

*Proof.* We have the following computation,

$$ \begin{aligned} f_{\mathbf{y},\mathcal{H},\mathbf{G}_{\text{aux}}} (\mathbf{u}) &= \sum_{\mathbf{v} \in \mathbb{F}_2^{k_{\text{aux}}}} (-1)^{\langle \mathbf{u}, \mathbf{v} \rangle} f_{\mathbf{y},\mathcal{H},\mathbf{G}_{\text{aux}}} (\mathbf{v}) \\ &= \sum_{(\mathbf{h},\mathbf{v}) \in \mathcal{C}^\perp \times \mathbb{F}_2^{k_{\text{aux}}}: (\mathbf{h},\mathbf{v}\mathbf{G}_{\text{aux}}) \in \mathcal{H}} (-1)^{\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{u}, \mathbf{v} \rangle} \quad \text{(Equations (2) and (9))} \\ &= \sum_{(\mathbf{h},\mathbf{v}) \in \mathcal{C}^\perp \times \mathbb{F}_2^{k_{\text{aux}}}: (\mathbf{h},\mathbf{v}\mathbf{G}_{\text{aux}}) \in \mathcal{H}} (-1)^{\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{v}\mathbf{G}_{\text{aux}} \rangle} \\ &= \sum_{(\mathbf{h},\mathbf{c}_{\text{aux}}) \in \mathcal{H}} (-1)^{\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{c}_{\text{aux}} \rangle} \\ &= \sum_{(\mathbf{h},\mathbf{c}_{\text{aux}}) \in \mathcal{H}} (-1)^{\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{c}_{\text{aux}} \rangle} \end{aligned} $$

which concludes the proof by definition of the bias. $\square$

**Remark 2.** The probabilistic notation hides the fact that computing all these Fourier coefficients and taking the maximum of them allows to decode in a certain code. Indeed let,

$$ \mathcal{D} \stackrel{\text{def}}{=} \left\{ \langle (\mathbf{u}, \mathbf{m}_{\text{aux}}) \rangle_{(\mathbf{h}, \mathbf{m}_{\text{aux}} \mathbf{G}_{\text{aux}}) \in \mathcal{H}} : \mathbf{u} \in \mathbb{F}_2^{k_{\text{aux}}} \right\} $$

which is under very mild assumptions a linear code of dimension $k_{\text{aux}}$ and length $|\mathcal{H}|$. If we let $c(\mathbf{u}) \stackrel{\text{def}}{=} (\langle \mathbf{u}, \mathbf{m}_{\text{aux}} \rangle)_{(\mathbf{h}, \mathbf{m}_{\text{aux}} \mathbf{G}_{\text{aux}}) \in \mathcal{H}}$ be the codeword associated to $\mathbf{u}$ and $\mathbf{v} = (\langle \mathbf{y}, \mathbf{h} \rangle)_{(\mathbf{h}, \mathbf{m}_{\text{aux}} \mathbf{G}_{\text{aux}}) \in \mathcal{H}}$ then since

$$ |\mathcal{H}| \quad \underset{(\mathbf{h},\mathbf{m}_{\text{aux}}\mathbf{G}_{\text{aux}}) \stackrel{\$}{\leftarrow} \mathcal{H}}{\text{bias}} (\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{u}, \mathbf{m}_{\text{aux}} \rangle) = |\mathcal{H}| - 2|\mathbf{v} + c(\mathbf{u})|, $$

it follows from Lemma 1 that $c(\mathbf{u}_0)$ is the codeword of $\mathcal{D}$ which is the closest to $\mathbf{v}$, where $\mathbf{u}_0 = \arg \max f_{\mathbf{y},\mathcal{H},\mathbf{G}_{\text{aux}}}(\mathbf{u})$. Therefore, vector $\mathbf{u}_0$ is here a likely candidate for being equal to $e_{\mathcal{H}}\mathbf{G}_{\text{aux}}^\top$ when $\mathcal{H}$ is big enough.

We give the pseudo-code of the FFT decoding algorithm producing a list $\mathcal{S}$ of putative candidates for being equal to $e_{\mathcal{H}}\mathbf{G}_{\text{aux}}^\top$ in Algorithm 2.

The point of using the FFT for computing all these biases is that its complexity is of order $O(k_{\text{aux}}2^{k_{\text{aux}}F})$ where $F$ is the complexity of computing $f_{\mathbf{y},\mathcal{H},\mathbf{G}_{\text{aux}}}$ which can be bounded by
<caption>**Algorithm 2** FFT algorithm producing a list of candidates for $e_{\mathcal{P}}G_{\text{aux}}^{\text{T}}$</caption>

**Input:** $\mathcal{H}$, $G_{\text{aux}}$
**Output:** $\mathcal{S}$ a list of candidates for $e_{\mathcal{P}}G_{\text{aux}}^{\text{T}}$
1: **function** FFT-DECODE($\mathcal{H}$, $G_{\text{aux}}$)
2: &nbsp;&nbsp;&nbsp;&nbsp;$f_{\mathbf{y},\mathcal{H},G_{\text{aux}}} \leftarrow \text{FFT}(f_{\mathbf{y},\mathcal{H},G_{\text{aux}}})$
3: &nbsp;&nbsp;&nbsp;&nbsp;$\mathcal{S} \leftarrow \{\mathbf{u} \in \mathbb{F}_2^{k_{\text{aux}}} : f_{\mathbf{y},\mathcal{H},G_{\text{aux}}}(\mathbf{u}) > \frac{\delta}{2} |\mathcal{H}|\}$
4: &nbsp;&nbsp;&nbsp;&nbsp;**return** $\mathcal{S}$
5: **end function**
$$ \delta \stackrel{\text{def}}{=} \frac{K_w^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u)}{\binom{n-s}{w} \binom{s}{t_{\text{aux}}}} $$

$\mathcal{O}(\max(1, \frac{|\mathcal{H}|}{2^{k_{\text{aux}}}}))$. On the other hand, if we had computed directly all those biases we would have a much bigger complexity of $\mathcal{O}(|\mathcal{H}|2^{k_{\text{aux}}})$ because $\mathcal{H}$ is of exponential size for the problem at hand.

**Recovering $e_{\mathcal{P}}$ and then $e$.** If we have a candidate $\mathbf{s}$ for $e_{\mathcal{P}}G_{\text{aux}}^{\text{T}}$, then since we expect $|e_{\mathcal{P}}| = t - u$, recovering $e_{\mathcal{P}}$ from the equality $\mathbf{s} = e_{\mathcal{P}}G_{\text{aux}}^{\text{T}}$ is nothing but solving a decoding problem, namely to decode $t - u$ errors in the code of parity-check matrix $G_{\text{aux}}$, i.e. $C_{\text{aux}}^{\perp}$. In other words, we have to solve DP($s, s - k_{\text{aux}}, t - u$). This approach can be generalized by taking $N_{\text{aux}}$ different sets of LPN samples associated respectively to the codes $C_{\text{aux}}^{(1)}, \dots, C_{\text{aux}}^{(N_{\text{aux}})}$. For $i$ in $\llbracket 1, N_{\text{aux}} \rrbracket$, let $G_{\text{aux}}^{(i)}$ be the generating matrix which is chosen for $C_{\text{aux}}^{(i)}$. Then each of these sets of LPN samples brings candidates for $e_{\mathcal{P}}G_{\text{aux}}^{\text{T}}$. By choosing an $N_{\text{aux}}$-tuple of candidates ($\mathbf{s}^{(1)}, \dots, \mathbf{s}^{(N_{\text{aux}})}$), where $\mathbf{s}^{(i)}$ is a candidate for $G_{\text{aux}}^{(i)}e_{\mathcal{P}}^{\text{T}}$ (we have taken the transpose to have a more readable form) given by the $i$-th LPN samples set, we get to solve the set of simultaneous equations

$$ (\mathbf{s}^{(1)})^{\text{T}} = G_{\text{aux}}^{(1)} e_{\mathcal{P}}^{\text{T}}, \dots, (\mathbf{s}^{(N_{\text{aux}})})^{\text{T}} = G_{\text{aux}}^{(N_{\text{aux}})} e_{\mathcal{P}}^{\text{T}} $$

with the constraint $|e_{\mathcal{P}}| = t - u$. In other words if we set

$$ \mathbf{H}^{\text{T}} \stackrel{\text{def}}{=} (G_{\text{aux}}^{(1)}^{\text{T}} \quad \dots \quad G_{\text{aux}}^{(N_{\text{aux}})}^{\text{T}}) \quad \text{and} \quad \mathbf{s} \stackrel{\text{def}}{=} (\mathbf{s}^{(1)} \quad \dots \quad \mathbf{s}^{(N_{\text{aux}})}) $$

then we have to solve the decoding problem $\mathbf{He}_{\mathcal{P}}^{\text{T}} = \mathbf{s}^{\text{T}}$ with $|e_{\mathcal{P}}| = t - u$, in other words we have to solve DP($s, s - N_{\text{aux}}k_{\text{aux}}, t - u$). We are going to choose a simple ISD algorithm to solve this problem, namely Dumer's algorithm [Dum89] which is a good compromise between efficiency and simple formula for its complexity. We denote by $\text{DECODE-DUMER}(\mathbf{H}, \mathbf{s}, t)$ the call to Dumer's algorithm to decode the syndrome $\mathbf{s}$ of an error of weight $t$ associated to the parity-check matrix $\mathbf{H}$. We assume here that this call produces all solutions to this decoding problem.

Once we have recovered $e_{\mathcal{P}}$, say we know that it is equal to some $\mathbf{v}$ of weight $t - u$ in $\mathbb{F}_2^s$, we face a much simpler problem. We namely have to solve the problem

$$ \mathbf{y} = \mathbf{c} + \mathbf{e}, \mathbf{c} \in \mathcal{C}, e_{\mathcal{P}} = \mathbf{v}, |e_{\mathcal{N}}| = u. $$

This is nothing but DP($n - s, k - s, u$) which is much simpler. Here we might just use algorithm $\text{DECODE-DUMER}$ on it. Let us call $\text{SOLVE-SUBPROBLEM}(\mathcal{C}, \mathcal{N}, \mathbf{y}, \mathbf{v}, u)$ the routine which performs this task and which returns a candidate for $e_{\mathcal{N}}$ and returns $\perp$ otherwise. If this problem has no solution we have of course a false candidate for $e_{\mathcal{P}}$ and if we have a solution, then we have solved our decoding problem. To verify that we have indeed such a decoding problem, suppose without loss of generality that $\mathcal{P} = \llbracket 1, s \rrbracket$ and $\mathcal{N} = \llbracket s + 1, n \rrbracket$. We can also assume that $\mathcal{C}_{\mathcal{P}}$ is of full rank dimension $s$ (this holds with overwhelming probability). We can compute $\mathbf{G}$ a generator matrix of $\mathcal{C}$ of the form $\mathbf{G} = \begin{pmatrix} \mathbf{I}_d & \mathbf{R} \\ \mathbf{0}_{k-s} & \mathbf{R}' \end{pmatrix}$ by applying partial Gaussian elimination on a generator matrix of $\mathcal{C}$. Then $\text{SOLVE-SUBPROBLEM}(\mathcal{C}, \mathcal{N}, \mathbf{y}, \mathbf{x}, u)$ decodes at distance $u$ the word $\mathbf{y}' \stackrel{\text{def}}{=} \mathbf{y}_{\mathcal{N}} - (\mathbf{y}_{\mathcal{P}} - \mathbf{x})\mathbf{R}$ onto the code $\mathcal{C}^{\mathcal{N}}$ of generator matrix $\mathbf{R}'$.

With this notation at hand, the pseudo-code describing the algorithm for recovering $e_{\mathcal{P}}$ and then returning $e$ if a suitable solution is found, is given in Algorithm 3.
<caption>**Algorithm 3** algorithm recovering $e_{\mathcal{P}}$ and then $e$</caption>

**Input:** $\mathcal{S}^{(1)}, \dots, \mathcal{S}^{(N_{aux})} \subset \mathbb{F}_2^{k_{aux}}, \mathbf{G}_{aux}^{(1)}, \dots, \mathbf{G}_{aux}^{(N_{aux})} \in \mathbb{F}_2^{k_{aux} \times s}$
1: **function** RECOVER-e($\mathcal{S}^{(1)}, \dots, \mathcal{S}^{(N_{aux})}, \mathbf{G}_{aux}^{(1)}, \dots, \mathbf{G}_{aux}^{(N_{aux})}$)
2: $\mathbf{H}^{\top} \leftarrow (\mathbf{G}_{aux}^{(1)}^{\top} \quad \dots \quad \mathbf{G}_{aux}^{(N_{aux})}^{\top})$
3: **for** $(\mathbf{s}^{(1)}, \dots, \mathbf{s}^{(N_{aux})}) \in \prod_{j=1}^{N_{aux}} \mathcal{S}^{(j)} \textbf{ do}
4: & $\mathbf{s} \leftarrow (\mathbf{s}^{(1)} \quad \dots \quad \mathbf{s}^{(N_{aux})})$
5: & **for all** $\mathbf{v} \in \text{DECODE-DUMER}(\mathbf{H}, \mathbf{s}, t) \textbf{ do}$
6: & & $\mathbf{e}' \leftarrow \text{SOLVE-SUBPROBLEM}(\mathcal{C}, \mathcal{N}, \mathbf{y}, \mathbf{v}, u)$
7: & **if** $\mathbf{e}' \neq \top$ **then**
8: & & & **return** $\mathbf{e}$ such that $\mathbf{e}_{\mathcal{P}} = \mathbf{x}$ and $\mathbf{e}_{\mathcal{N}} = \mathbf{e}'$
9: & **end if**
10: **end for**
11: **end for**
12: **end function**

**Testing Enough Candidates** $\mathcal{N}$. Now, it may also happen that when choosing $\mathcal{N}$, we might not have that $|e_{\mathcal{N}}| = u$. For this, we have to check enough candidates. The probability that a set $\mathcal{N}$ of size $n-s$ satisfies this property is given by

$$P_{\text{succ}} \stackrel{\text{def}}{=} \frac{\binom{t}{u} \binom{n-t}{n-u-s}}{\binom{n}{n-s}}.$$

Performing a number $N_{iter}$ of trials for $\mathcal{N}$ which is of order $\Theta(1/P_{succ})$ will succeed with constant probability. Putting all these ingredients together leads to the whole double-RLPN algorithm given in Algorithm 4.

<caption>**Algorithm 4** double-RLPN decoder</caption>

**Input:** $\mathbf{y}, t, \mathcal{C}$ an $[n, k]$-code
**Parameters:** $s, u, k_{aux}, t_{aux}, N, (\mathcal{C}_{aux}^{(j)})_{j \in \mathcal{F}}$
**Output:** $\mathbf{e}$ such that $|\mathbf{e}| = t$ and $\mathbf{y} - \mathbf{e} \in \mathcal{C}$.
1: **function** double-RLPN($\mathbf{y}, \mathcal{C}, t$)
2: & **for** $i$ from 1 to $N_{iter}$ **do**
3: & & $\mathcal{N} \leftarrow \{\mathcal{I} \subseteq [1, n] : |\mathcal{I}| = n-s\}$
4: & & **for** $j = 1, \dots, N_{aux}$ **do**
5: & & & $(\mathcal{H}^{(j)}, \mathbf{G}_{aux}^{(j)}) \leftarrow \text{LPN-SAMPLES}(\mathcal{C}, \mathcal{N})$
6: & & & $\mathcal{S}^{(j)} \leftarrow \text{FFT-DECODE}(\mathcal{H}^{(j)}, \mathbf{G}_{aux}^{(j)})$
7: & & **end for**
8: & **RECOVER-e**($\mathcal{S}^{(1)}, \dots, \mathcal{S}^{(N_{aux})}, \mathbf{G}_{aux}^{(1)}, \dots, \mathbf{G}_{aux}^{(N_{aux})}$)
9: & **end for**
10: **end function**

**Complexity of the Algorithm.** It is sufficient to take $N_{aux} = \mathcal{O}(1)$ for the parameters we are interested in which will correspond to a choice of $k_{aux}$ of the form $k_{aux} = \Omega(s)$. With this choice we immediately get the following complexity for the double-RLPN algorithm
**Proposition 3.** The complexity C of the double-RLPN algorithm is given by

$$
\begin{align*}
C &= \tilde{O}\left(\frac{1}{P_{\text{succ}}} \left(T_{\text{eq}} + N T_{\text{dec}} + k_{\text{aux}} \max\left(2^{k_{\text{aux}}}, |\mathcal{H}|\right) + S^{N_{\text{aux}}} T_{\text{ISD}}\right)\right) \quad \text{where} \\
P_{\text{succ}} &= \frac{\binom{t}{u} \binom{n-t}{n-u-s}}{\binom{n}{n-s}} \\
T_{\text{ISD}} &= T_{\text{Dumer}}(s, s - N_{\text{aux}} k_{\text{aux}}, t-u) + N_{\text{ISD}} T_{\text{Dumer}}(n-s, k-s, u)
\end{align*}
$$

and $T_{\text{eq}}$ is the time complexity of PARITYCHECKEQUATIONS, $N$ is the number of parity-check equations produced by this procedure, $T_{\text{dec}}$ is the complexity of decoding $C_{\text{aux}}$, i.e. it is the complexity of a call to DECODE(), $S$ is the size of a list output by FFT-DECODE(), $N_{\text{ISD}}$ is the number of solutions to the $(s, s-N_{\text{aux}}k_{\text{aux}}, t-u)$ decoding problem and $T_{\text{Dumer}}(n, k, t)$ stands for the complexity of solving the $(n, k, t)$ decoding problem with Dumer's algorithm when we want to find all solutions to the problem.

The asymptotic complexity formula for the double-RLPN algorithm, including also the con-
straints required on our parameters, is given in Appendix B Proposition 9 which was used to
generate Figure 1.

5. ESTIMATING THE NUMBER OF FALSE CANDIDATES

The goal of this section is to introduce the main tool necessary to make a rigorous analysis of Algorithm 4 and to give a formula for the number of false candidates which is proved by making a certain conjecture whose validity has then been verified experimentally.

5.1. **Main Duality Tool.** The fundamental quantity when analyzing dual attacks is the bias of $\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{c}_{\text{aux}} \rangle$ which tells us whether $\mathbf{x} \mathbf{G}_{\text{aux}}^{\top}$ has to be put in the list $\mathcal{S}$ of candidates output by Algorithm 2. While initially standard independence assumptions were made to analyze its distribution [CDMT22, Ass. 3.7] (which are very similar to analyze dual attacks in lattice based cryptography), recently [MT23] showed that these assumptions were erroneous and, gave for the first time a dual expression [MT23, Prop 1.] for this quantity which seems a key step to understand its behavior and gave with an additional assumption a rigorous analysis of the RLPN dual attack. The proposition given there to estimate the number of false candidates turns out to match accurately the experiments. The following proposition is a generalization of [MT23, Prop 1.] and gives a dual expression for the aforementioned bias.

**Proposition 4.** Let $\mathcal{P}$ and $\mathcal{N}$ be two complementary subsets of $[1, n]$ of size $s$ and $n-s$ respectively. Let $C$ be an $[n, k]$-code such that $C_{\mathcal{P}}$ is of dimension $s$ and let $C_{\text{aux}}$ be an $[s, k_{\text{aux}}]$-code. We have for any $\mathbf{x} \in \mathbb{F}_2^s$

$$
\text{bias}_{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \stackrel{\mathcal{S}}{\leftarrow} \tilde{\mathcal{H}}} (\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{c}_{\text{aux}} \rangle) = \frac{1}{2^{k-k_{\text{aux}}}} \frac{1}{|\tilde{\mathcal{H}}|} \sum_{i=0}^{n-s} \sum_{j=0}^{s} N_{i,j} K_w^{(n-s)}(i) K_{t_{\text{aux}}}^{(s)}(j) \quad (10)
$$

where

$$
\begin{align*}
N_{i,j} &\stackrel{\text{def}}{=} |\{(\mathbf{r}, \mathbf{c}^{\mathcal{N}}) \in (\mathbf{x} + \mathcal{C}_{\text{aux}}^{\perp}) \times \mathcal{C}^{\mathcal{N}} : |\mathbf{r}| = j \text{ and } |(\mathbf{r} + \mathbf{e}_{\mathcal{P}})\mathbf{R} + \mathbf{e}_{\mathcal{N}} + \mathbf{c}^{\mathcal{N}}| = i\}|, \\
\tilde{\mathcal{H}} &= \{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \in \mathcal{C}^{\perp} \times \mathcal{C}_{\text{aux}} : |\mathbf{h}_{\mathcal{N}}| = w \text{ and } |\mathbf{h}_{\mathcal{P}} + \mathbf{c}_{\text{aux}}| = t_{\text{aux}}\}
\end{align*}
$$

and where $\mathbf{R} \in \mathbb{F}_2^{s \times (n-s)}$ is such that for any $\mathbf{h} \in \mathcal{C}^{\perp}$ we have $\mathbf{h}_{\mathcal{P}} = \mathbf{h}_{\mathcal{N}} \mathbf{R}^{\top}$.

Proof. This proposition is proved in Appendix C.

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

5.2. **Intuition on How this Formula Allows to Estimate** $|\mathcal{S}|$. As a preliminary remark, notice that bias$_{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \stackrel{\mathcal{S}}{\leftarrow} \tilde{\mathcal{H}}}$ $(\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{c}_{\text{aux}} \rangle)$ is the same for all $\mathbf{x}$ belonging to a same coset of
$C_{\text{aux}}^{\perp}$ and therefore only possibly allows to distinguish the values $\mathbf{x}\mathbf{G}_{\text{aux}}^{\text{I}}$. Second, observe that the expected value of $|\tilde{\mathcal{H}}|$ is $\frac{\binom{n-s}{w}}{2^{k-s}}\frac{\binom{s}{t_{\text{aux}}}}{2^{s-k_{\text{aux}}}}$ so that we expect

$$ \frac{1}{2^{k-k_{\text{aux}}}|\tilde{\mathcal{H}}|} \approx \frac{1}{\binom{n-s}{w}\binom{s}{t_{\text{aux}}}}. $$

Third, observe that Proposition 2 means in essence that the bias corresponding to $\mathbf{e}_{\mathcal{P}}$, namely $\text{bias}_{(\mathbf{h},\mathbf{c}_{\text{aux}})\leftarrow\tilde{\mathcal{H}}}((\mathbf{y},\mathbf{h}) + \langle\mathbf{e}_{\mathcal{P}},\mathbf{c}_{\text{aux}}\rangle)$ should be $\approx \frac{K_{w}^{(n-s)}(u)K_{t_{\text{aux}}}^{(s)}(t-u)}{\binom{n-s}{w}\binom{s}{t_{\text{aux}}}}$, i.e. it corresponds roughly to the “first” pair $(i,j)$ (where we range the values according to the product $K_{w}^{(n-s)}(i)K_{t_{\text{aux}}}^{(s)}(j)$) for which $N_{i,j} \neq 0$, namely $(i,j) = (u,t-u)$ where the pair $(\mathbf{e}_{\mathcal{P}},\mathbf{0})$ is likely to be the only pair $(\mathbf{r},\mathbf{c}^{\mathcal{N}})$ in $(\mathbf{e}_{\mathcal{P}}+C_{\text{aux}}^{\perp})\times C^{\mathcal{N}}$ such that $|\mathbf{r}| = t-u$ and $|(\mathbf{r}+\mathbf{e}_{\mathcal{P}})\mathbf{R}+\mathbf{e}_{\mathcal{N}}+\mathbf{c}^{\mathcal{N}}| = u$ (and therefore we likely have $N_{u,t-u} = 1$). Therefore the behavior of the sum appearing in (10) is dominated by this first term $N_{i,j}$ which is non zero, namely $(i,j) = (u,t-u)$ since we really have in this case that the corresponding term in the sum is nothing but

$$ \frac{K_{w}^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u)}{\binom{n-s}{w}\binom{s}{t_{\text{aux}}}}. $$

This kind of phenomenon appears to be much more general than this: the $\mathbf{x} \in \mathbb{F}_2^s$ which give a high bias (and are therefore the ones we put in $\mathcal{S}$) are those for which there is an $N_{i,j}$ which is unexpectedly non zero (and therefore most likely equal to 1) in the low values of $(i,j)$ for which the term $K_{w}^{n-s}(i)K_{t_{\text{aux}}}^{(s)}(j)$ can compete or even supersede the term dominating in the expression (10) of the bias of $\mathbf{e}_{\mathcal{P}}$, namely $K_{w}^{(n-s)}(u)K_{t_{\text{aux}}}^{(s)}(t-u)$ (we have ignored the common denominator $2^{k-k_{\text{aux}}}|\tilde{\mathcal{H}}|$ appearing in both sums). Similarly we expect that the bias of those $\mathbf{x}$ is of order in this case

$$ \frac{K_{w}^{(n-s)}(i) K_{t_{\text{aux}}}^{(s)}(j)}{\binom{n-s}{w}\binom{s}{t_{\text{aux}}}}. $$

This intuition is formalized by Conjecture 1 what we make later on.

**5.3. Main Proposition.** The key step of the analysis is to estimate the number of candidates, namely the size of $\mathcal{S}$ (Instruction 3 of Algorithm 4). Provided that the bet ($|\mathbf{e}_{\mathcal{N}}| = u$) on the error is valid we expect that the secret vector $\mathbf{e}_{\mathcal{P}}\mathbf{G}_{\text{aux}}^{\text{I}}$ belongs to $\mathcal{S}$. But, as we will show in this section this set also contains some false positives, namely any element of $\mathcal{S} \setminus \{\mathbf{e}_{\mathcal{P}}\mathbf{G}_{\text{aux}}^{\text{I}}\}$. Testing if an element of $\mathcal{S}$ is a false positive (Algorithm 3) will be of exponential cost. Estimating their number is therefore crucial to predict the complexity of our algorithm. The following proposition bounds the expected number of candidates in a typical iteration of Algorithm 4.

**Proposition 5.** Using Distribution 1 for $C, C_{\text{aux}}, \mathbf{e}$ and $\mathbf{y}$ and given that our parameters verify Parameter Constraint 1, that the number of computed LPN samples is the total number of available LPN samples, i.e. $\mathcal{H} = \tilde{\mathcal{H}}$ and under Conjecture 1 we have that the expected number of candidates per iteration is bounded by

$$ \mathbb{E}_{C, C_{\text{aux}}}(|\mathcal{S}|) = \tilde{\mathcal{O}}\left(\max_{(i,j) \in \mathcal{A}} \frac{\binom{s}{j}\binom{n-s}{i}}{2^{n-k}}\right) + 1 \quad (11) $$

where

$$ \mathcal{A} \stackrel{\text{def}}{=} \left\{ (i,j) \in [0, n-s] \times [0, s], \left| \frac{K_w^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u)}{K_w^{(n-s)}(i) K_{t_{\text{aux}}}^{(s)}(j)} \right| \le n^{3.2} \right\}. \quad (12) $$

The set $\mathcal{S}$ of candidates is defined by

$$ \mathcal{S} \stackrel{\text{def}}{=} \left\{ \mathbf{s} \in \mathbb{F}_2^{k_{\text{aux}}} : f_{\mathbf{y}, \tilde{\mathcal{H}}, \mathbf{G}_{\text{aux}}} (\mathbf{s}) \ge \frac{\delta}{2} \tilde{H} \right\}, \quad (13) $$
where

$$ \tilde{H} \stackrel{\text{def}}{=} \frac{\binom{n-s}{w} \binom{s}{t_{\text{aux}}}}{2^{k-k_{\text{aux}}}} \quad \text{and} \quad \delta \stackrel{\text{def}}{=} \frac{K_w^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u)}{\binom{n-s}{w} \binom{s}{t_{\text{aux}}}}. \qquad (14) $$

**Remark 3.** The additional constraint that $\mathcal{H} = \tilde{\mathcal{H}}$ is only here to simplify the proof. One could make a similar proposition without this constraint. In our instantiation of Algorithm 4 and with our optimal parameters this constraint is de-facto verified. Note also that $\tilde{H}$ appearing in the expression of the threshold is the expected number of available LPN samples, namely $\mathbb{E}_{C, \mathcal{C}_{\text{aux}}} (|\tilde{\mathcal{H}}|)$.

**Distribution 1.**

* $\mathcal{P}$ and $\mathcal{N}$ are two fixed complementary subsets of $[1, n]$ of size $s$ and $n-s$ respectively.

* The code $C$ of generator matrix $G$ is chosen uniformly at random among $[n, k]$ linear codes which are such that $C_{\mathcal{P}}$ is of dimension $s$.

* The code $C_{\text{aux}}$ of generator matrix $G_{\text{aux}} \in \mathbb{F}_2^{k_{\text{aux}} \times s}$ is chosen uniformly at random among the $[s, k_{\text{aux}}]$-codes.

* $e \in \mathbb{F}_2^n$ is a fixed vector of $S_t^n$, $c \in C$ is a random codeword of $C$ and we define $y \stackrel{\text{def}}{=} c + e$.

Correctness of our algorithm is ensured by the following constraints.

**Parameter Constraint 1.** We suppose that the parameters $n, k, t, s, k_{\text{aux}}, t_{\text{aux}}, w, u$ are such that there exists a constant $\alpha > 0$ that is such that

$$ (i) \quad \frac{\binom{n-s}{w} \binom{s}{t_{\text{aux}}}}{2^{k-k_{\text{aux}}}} = \omega\left(\frac{n^{\alpha+8}}{\delta^2}\right), \quad (ii) \quad \frac{\binom{n-s}{w} \binom{s}{t_{\text{aux}}}}{2^k} = \mathcal{O}(n^\alpha), \quad (iii) \quad \frac{\binom{s}{t_{\text{aux}}}}{2^{s-k_{\text{aux}}}} = \mathcal{O}(n^\alpha). \qquad (15) $$

where,

$$ \delta \stackrel{\text{def}}{=} \frac{K_w^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u)}{\binom{n-s}{w} \binom{s}{t_{\text{aux}}}}. $$

**Remark 4.** Note that these constraints are in fact, up to a polynomial factor, the minimal constraints required for our algorithm to work. Indeed, there are precisely the constraints required in Proposition 2 which estimates the bias of the error of the LPN samples (5).

The difficulty of proving Proposition 5 is similar to the difficulties encountered in analyzing the RLPN algorithm in [MT23], we know too little about the tails of the distribution of $N_{i,j}$. As such, we will make the following conjecture which formalizes the discussion in §5.2.

**Conjecture 1.** Using Distribution 1, under Parameter Constraint 1,

$$ \mathbb{P} \left( \sum_{j=0}^{s} \sum_{i=0}^{n-s} K_{t_{\text{aux}}}^{(s)}(j) K_{w}^{(n-s)}(i) N_{i,j} \ge \frac{1}{2} K_{w}^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u) \right) \\ = \tilde{\mathcal{O}} \left( \max_{(i,j) \in \mathcal{A}} \mathbb{P} (N_{i,j} \ne 0) + 2^{-n} \right) $$

where $\mathcal{A}$ is given in Equation (12) and $\mathbf{x}$ is taken uniformly at random in $\mathbb{F}_2^s \setminus \{\mathcal{C}_{\text{aux}}^{\perp} + e_{\mathcal{P}}\}$.

Conjecture 1 is discussed in the following section where we give experimental evidences that our analysis holds. In Appendix F.1 we show that this conjecture is in fact a consequence of a more minimalistic conjecture.

## 6. EXPERIMENTAL EVIDENCE FOR OUR ANALYSIS

The goal of this section is to provide experimental evidence supporting Proposition 5. We will propose a convenient probabilistic model for the $N_{i,j}$'s and show that this model does not change the output distribution of our algorithm. We will essentially use the same model as in [MT23,
Appendix D] and model the weight distribution of the coset of a random linear code as a Poisson distribution of the right expected value. Recall that $N_{i,j}$ can be written as

$$N_{i,j} = \sum_{u=0}^{N_j(C_{\text{aux}}^{\perp} + \mathbf{x})} N_i \left( \left( \mathbf{r}^{(u)} + \mathbf{e}_{\mathcal{P}} \right) \mathbf{R} + \mathbf{e}_{\mathcal{N}} + \mathcal{C}^{\mathcal{N}} \right)$$

where $\mathbf{R} \in \mathbb{F}_2^{s \times (n-s)}$ is such that for any $\mathbf{h} \in \mathcal{C}^{\perp}$ we have $\mathbf{h}_{\mathcal{P}} = \mathbf{h}_{\mathcal{N}} \mathbf{R}^{\top}$, $\mathbf{r}^{(u)}$ is the $u$'th codeword of weight $j$ of $\mathcal{C}_{\text{aux}}^{\perp} + \mathbf{x}$ and $N_j(\mathcal{C}_{\text{aux}}^{\perp} + \mathbf{x})$ counts the number of elements in $\mathcal{C}_{\text{aux}}^{\perp} + \mathbf{x}$ of Hamming weight $j$. With our model, we first draw $N_j(\mathcal{C}_{\text{aux}}^{\perp} + \mathbf{x})$ according to a Poisson distribution of expected value $\frac{\binom{s}{j}}{2^{k_{\text{aux}}}}$ and then we draw each $N_i((\mathbf{r}^{(u)} + \mathbf{e}_{\mathcal{P}})\mathbf{R} + \mathbf{e}_{\mathcal{N}} + \mathcal{C}^{\mathcal{N}})$ according to independent Poisson distributions of expected values $\frac{\binom{n-s}{j}}{2^{n-k}}$ (see appendix E, Lemma 9 where we compute $\mathbb{E}(N_j(\mathcal{C}_{\text{aux}}^{\perp} + \mathbf{x}))$ and $\mathbb{E}(N_i((\mathbf{r}^{(u)} + \mathbf{e}_{\mathcal{P}})\mathbf{R} + \mathbf{e}_{\mathcal{N}} + \mathcal{C}^{\mathcal{N}}))$ under Distribution 1). Finally, we get the following model for $N_{i,j}$ by using the fact that the sum of independent Poisson random variables is a Poisson random variable:

**Model 1 (Poisson Model).** Under Distribution 1 and when $\mathbf{x}$ is taken uniformly at random in $\mathbb{F}_2^{s \setminus \{\mathcal{C}_{\text{aux}}^{\perp} + \mathbf{e}_{\mathcal{P}}\}}$ we make the model that

$$N_{i,j} \sim \text{Poisson} \left( N_j \frac{\binom{n-s}{i}}{2^{n-k}} \right), \text{ where } N_j \sim \text{Poisson} \left( \frac{\binom{s}{j}}{2^{k_{\text{aux}}}} \right).$$

Under Poisson Model 1, the following proposition proves Conjecture 1 and thus it shows that Proposition 5 holds.

**Proposition 6.** Under the Poisson Model 1, Conjecture 1 holds.

*Proof.* The proof is given Appendix F. □

In Figure 2 we computed the expected number of $\mathbf{x}$'s whose bias multiplied by $|\tilde{H}|$ is bigger than some prescribed quantity $T$ according to

* the standard independence model in dual attacks where the $\langle \mathbf{e}, \mathbf{h} \rangle$'s are supposed to be independent,

* some experiments,

* the case where we replace the right-hand term of $N_{i,j}$ (given in Equation (10)) by their Poisson model.

As it is shown by Figure 2, the Poisson model matches remarkably well with the experiments. This shows, as was the case in the analysis [MT23] of the RLPN algorithm, that the Poisson model allows to predict accurately the size of $\mathcal{S}$.

## 7. INSTANTIATING THE AUXILIARY CODE $\mathcal{C}_{\text{aux}}$ WITH AN EFFICIENT DECODER

In double-RLPN we need to choose an auxiliary code $\mathcal{C}_{\text{aux}}$ which is efficiently list-decodable (Definition 6) at the smallest as possible distance $t_{\text{aux}} = d_{\text{GV}}(s, k_{\text{aux}})$. We propose to use the following product of small random codes (other choices may be more suitable but they are harder to analyze, like polar codes [Ar109, KU10, Şas11, TV12]),

$$\mathcal{C}_{\text{aux}} \stackrel{\text{def}}{=} \mathcal{C}_1 \times \cdots \times \mathcal{C}_b$$

where the $\mathcal{C}_i$'s are random $[\frac{s}{b}, \frac{k_{\text{aux}}}{b}]$-codes. Notice that

$$\mathcal{Dec}(\mathbf{z}) \stackrel{\text{def}}{=} \{\mathbf{c}_{\text{aux}} \in \mathcal{C}_{\text{aux}} : |\mathbf{c}_{\text{aux}} + \mathbf{z}| = t_{\text{aux}}\}$$

does not look exactly like how it should with a random code for which our analysis given in Propositions 2 and 5 hold. Furthermore, we will compute

$$\mathcal{H} \subseteq \{ (\mathbf{h}, \mathbf{c}_{\text{aux}}) \in \mathcal{C}^{\perp} \times \mathcal{C}_{\text{aux}} : \forall i \in [1, b], |\mathbf{h}_{\mathcal{N}}(i)| = \frac{w}{b} \text{ and } |\mathbf{h}_{\mathcal{P}}(i) + \mathbf{c}_i| = \frac{t_{\text{aux}}}{b} \}$$
<figure><img src="image_6.png" /><figcaption>FIGURE 2. Size of the set $\{x \in \mathbb{F}_2^{k_{aux}} \setminus \{e, \mathcal{G}_{aux}\} : \hat{f}_{y, \mathcal{H}}(x) \ge T\}$ as a function of $T$ when $[w, t_{aux}, k_{aux}, s, k, n, u, t] = [5, 2, 20, 28, 30, 60, 8, 8]$, number of LPN samples $N = 65536$. Here the curve “Independence model” has been replaced when modelling the $\langle y, h \rangle$'s by i.i.d Bernoulli random variables of parameter $\frac{1}{2}$ (standard independence model in dual attacks).</figcaption></figure>

in Instruction 1 of Algorithm 1. To this aim we will perform exhausting search on the random codes. By choosing the number $b$ of blocs as,

$$b = \Theta(\log n) \qquad (16)$$

the above decoding algorithm costs for any parity-check equation $O(2^{n/\log n})$ (recall that $t_{aux} \approx d_{GV}(n, k)$). Therefore, as Algorithm 1 running time is exponential (in $n$) for our considered parameters, it won't affect it. Furthermore, there are false candidates when computing $\mathcal{H}$ and it is crucial to estimate their numbers.

Our analysis of Sections 3 and 5 has been made in the idealized-model where $C_{aux}$ is a random code equipped with genie aided decoders. But, by choosing $b$ as in Equation (16), analysis of Propositions 2 and 5 is still verified with our particular choice of $C_{aux}$ (up to negligible factors) as justified in Appendix G.

## 8. LINKS WITH DUAL ATTACKS IN LATTICE BASED CRYPTOGRAPHY

The purpose of this section is to give more details about the close connection between dual attacks in coding theory (a.k.a “statistical decoding” after the pioneering work of [Jab01]) and dual attacks in lattice based cryptography. Basically, with some slight differences highlighted in [PS23, App. A], the lattice based analogue of the dual attack presented here is the slight improvement [CST22] of the Matzov attack [MAT22]. The improvement in [CST22] is based on the fact that the modulus switching technique used in [MAT22] can be viewed as a suboptimal source distortion code for the Euclidean metric which can be replaced by an almost optimal polar code. The approach followed here should carry over to this lattice setting as well and in particular, the fundamental duality Proposition 4. Let us just observe now that a simple duality equality (together with a gross approximation based on the considerations of §5.2) can be used to explain the results observed in [DP23b, Fig. 3]. It was shown there that predictions of the score function based on standard independence assumptions made for dual attacks in lattice based cryptography seem to be off in some parameter region (what can be called the “error-floor” region due to its
similarity with the Low-Density-Parity-Check codes literature). To explain this point, we will use the same notation as in [DP23b] and will not redefine the quantities appearing here.

Let us first observe that an immediate corollary of Proposition 4 is

**Corollary 1.** Consider an $[n, k]$ linear code $C$ and consider some word $\mathbf{y} = \mathbf{c} + \mathbf{e} \in \mathbb{F}_2^n$ where $\mathbf{c}$ is in $C$. Let $\mathcal{W}$ be the set of codewords of weight $w$ in $C^\perp$ and let $f_{\mathcal{W}}(\mathbf{y}) \stackrel{\text{def}}{=} \sum_{\mathbf{w} \in \mathcal{W}} (-1)^{\langle \mathbf{y}, \mathbf{w} \rangle}$. We have

$$f_{\mathcal{W}}(\mathbf{y}) = \frac{1}{2^k} \sum_{i=0}^{n} N_i K_w^n(i)$$

where $N_i$ is the number of words of weight $i$ in $C + \mathbf{e}$.

It is insightful to view these Krawtchouk polynomials as the Fourier transform of the indicator function of a Hamming sphere, see Fact 1. Similarly, the lattice based analogue of Corollary 1 involving the lattice based analogue of $f_{\mathcal{W}}$, which is called the score function in [DP23b] will involve the Bessel function of the first kind (see for instance [DDRT23, Fact 4.9]). We namely obtain

**Proposition 7.** Consider a lattice $\Lambda \subseteq \mathbb{R}^n$ and consider some word $\mathbf{y} = \mathbf{x} + \mathbf{e} \in \mathbb{R}^n$ where $\mathbf{x}$ is in $\Lambda$. Let $\mathcal{W}$ be the set of dual lattice vectors of Euclidean weights in $(w - \varepsilon, w + \varepsilon)$ in $\Lambda^\vee$ and let $f_{\mathcal{W}}(\mathbf{y}) \stackrel{\text{def}}{=} \sum_{\mathbf{w} \in \mathcal{W}} \cos(2\pi\langle\mathbf{x}, \mathbf{y}\rangle)$. We have

$$f_{\mathcal{W}}(\mathbf{y}) = \frac{1}{|\Lambda^\vee|} \sum_{j \ge 0} \frac{N_j}{j^n (2\pi)^{n/2}} \left( (2\pi(w+\varepsilon)j)^{n/2} J_{n/2}(2\pi(w+\varepsilon)j) - (2\pi(w-\varepsilon)j)^{n/2} J_{n/2}(2\pi(w-\varepsilon)j) \right) \quad (17)$$

where $N_j$ is the number of words of Euclidean norm $j$ in $\Lambda + \mathbf{e}$ and $J_\nu$ is the Bessel function of the first kind of order<fnref n="1" /> $\nu$.

The proof is given in Appendix H. Let us take some subset $\mathcal{W}$ of $\mathcal{W}$ of size $N$ say. We make the approximation $f_{\mathcal{W}}(\mathbf{y}) \approx \frac{N}{|\mathcal{W}|} f_{\mathcal{W}}(\mathbf{y})$ and by using the Gaussian heuristic and some computations that are detailed in Appendix H:

$$f_{\mathcal{W}}(\mathbf{y}) \approx N \frac{\sqrt{n\pi}}{e} \sum_{j \ge 0} N_j \left( \frac{n}{2\pi ew_j} \right)^{n/2-1} J_{n/2-1}(2\pi w_j). \quad (18)$$

We can use now a similar heuristic as the one described in §5.2 and predict that the abnormal large values of the score function $f_{\mathcal{W}}(\mathbf{y})$ appear when $\mathbf{y}$ is abnormally close to $\Lambda$, say $N_{\le x} \ne 0$, where $N_{\le x} = |\{\mathbf{c} \in \Lambda : |\mathbf{y} - \mathbf{c}| \le x\}|$ when $\mathbb{P}(N_{\le x} \ne 0) \ll 1$. In this case, we make the crude approximation that the sum (18) is dominated by the term $j_0$ which is the smallest in it:

$$f_{\mathcal{W}}(\mathbf{y}) \approx N \frac{\sqrt{n\pi}}{e} N_{j_0} \left( \frac{n}{2\pi ew_{j_0}} \right)^{n/2-1} J_{n/2-1}(2\pi w_{j_0}). \quad (19)$$

The survival function $\mathbb{P}(f_{\mathcal{W}}(\mathbf{y}) \ge X)$ is then crudely approximated as the probability that such an event happens

$$\begin{aligned} \mathbb{P} \left( f_{\mathcal{W}}(\mathbf{y}) \ge N \frac{\sqrt{n\pi}}{e} N_x \left( \frac{n}{2\pi ew_x} \right)^{n/2-1} J_{n/2-1}(2\pi w_x) \right) &\approx \mathbb{P}(N_{\le x} \ge 1) \\ &\approx \mathbb{E}(N_{\le x}) \\ &\approx \left( \frac{x}{\sqrt{\frac{n}{2\pi e} \cdot (\pi n)^{1/n} \cdot |\Lambda|^{1/n}}} \right)^n \end{aligned}$$

<footnote n="1">¹Here the $j$'s belong to the discrete set of all possible norms in the lattice and should not be viewed as an integer value.</footnote>
where the last approximation is the Gaussian heuristic. In the context of the experiments described in [DP23b, §5], $\Lambda \stackrel{\text{def}}{=} \mathcal{L}(\mathbf{B})$ is given by<fnref n="2" />

$$ \mathbf{B} \stackrel{\text{def}}{=} \left[ \begin{array}{c|c} \mathbf{I}_{n/2} & \mathbf{A} \\ \hline \mathbf{0} & q \cdot \mathbf{I}_{n/2} \end{array} \right] \cdot \left[ \begin{array}{c|c} 2 \cdot \mathbf{I}_{k_{\text{fft}}} & \mathbf{0} \\ \hline \mathbf{0} & \mathbf{I}_{n-k_{\text{fft}}} \end{array} \right] \quad (20) $$

Then we use the same full sieve algorithm as in [DP23b] to produce short vectors $\mathcal{W} \subset \Lambda^\vee$. In what follows, we use the practical values of $N$ and $w$ that we obtained by experiments. We have reused the implementation for the experiments in [DP23b, §5]<fnref n="3" />. This very crude estimation seems to capture the error-floor behavior of the survival function as shown in Figure 3. The point is that it is precisely this part of the curve which is not predicted by the standard independence assumption and which had no explanation so far. It can also be observed that the duality result is nothing but a straightforward use of the Poisson formula which has also be used very recently in [WE23] to predict the abnormal variance of the BDD score distribution observed in [DP23b, Table 1].

<figure><img src="image_7.png" /><figcaption>FIGURE 3. Crude estimation of the survival function (red, dash-dot line) compared to the experiments in [DP23b, §5] (green, full line) and the prediction with the standard independence assumption (blue, dashed line). (left) $q = 3329$, $n = 60$, $T = 2^{45}$, $N = 5040$ and $w = 0.0320$; (right) $q = 3329$, $n = 80$, $T = 2^{48}$, $N = 89494$ and $w = 0.0376$.</figcaption></figure>

**A more precise prediction.** One can remark (see Figure 3) that i) our newly introduced approximate distribution for $f_W$ given in Equation (19) matches the experimental curves specifically in the waterfall-floor zone and ii) the distribution of $f_W$ given by the independence heuristic [DP23b, Heuristic 3] matches the experimental curves up to this waterfall-floor zone. A natural idea to predict the experimental curve on the whole support is therefore to take the convolution of these two distributions. Indeed, for any support point, there is always one distribution which exponentially dominates the other one.

**Distribution in the waterfall-floor zone.** Let us denote by $\mathbf{X}_{\text{floor}}$ the random variable given by Equation (19), namely:

$$ \mathbf{X}_{\text{floor}} \stackrel{\text{def}}{=} G(j_0) \quad (21) $$

where

$$ G(j) = N \frac{\sqrt{n\pi}}{e} \left( \frac{n}{2\pi ewj} \right)^{n/2-1} J_{n/2-1}(2\pi wj) $$

and $j_0$ is the length of the shortest vector of the lattice. We only have to compute the distribution of $j_0$ to compute the distribution of $\mathbf{X}_{\text{floor}}$. To that extend we make the following classic model.

<footnote n="2">²In [DP23b], $\Lambda$ and $\mathbf{B}$ are actually respectively $\Lambda'$ and $\mathbf{B}'$</footnote>

<footnote n="3">³https://github.com/ludopulles/DoesDualSieveWork</footnote>
**Model 2.** Model for the number of lattice points in a ball. Let $\Lambda$ be a random lattice of full rank $n$ and of volume $V$. We make the model that:

$$|\Lambda \setminus \{0\} \cap \mathcal{B}_z| \sim \text{Poisson} \left( \frac{\text{Vol}(\mathcal{B}_1) z^n}{V} \right)$$

where $\mathcal{B}_z$ denotes the Euclidean ball of center 0 and radius $z$ and $\text{Vol}(\mathcal{B}_1) = \frac{\sqrt{\pi^n}}{\Gamma(\frac{\pi}{2}+1)}$.

This model allows us to write the following fact regarding the distribution of the length of the $j$'th shortest vector:

**Fact 2.** Under Model 2, and for $k = 0 \cdots \infty$ the distribution of $j_k$, i.e. the $k$'th non-zero shortest vector of a random lattice $\Lambda$ of full rank $n$ and of volume $V$, is given by:

$$j_k^n \sim \text{Gamma} \left( k + 1, \frac{\text{Vol}(\mathcal{B}_1)}{V} \right)$$

where $\mathbf{Z} \sim \text{Gamma}(b, \theta)$ has the following survival function when $b$ is an integer:

$$\mathbb{P}(\mathbf{Z} \ge \alpha) \stackrel{\text{def}}{=} e^{-\theta\alpha} \sum_{i=0}^{b-1} \frac{(\theta\alpha)^i}{i!}.$$

*Proof.* For any $z > 0$, we have that

$$\begin{align*}
\mathbb{P}(j_k^n > z^n) &= \mathbb{P}(j_k > z) \\
&= \mathbb{P}\left(\bigcup_{i=0}^k \text{``}|\Lambda \setminus \{0\} \cap \mathcal{B}_z| = i''\right) \\
&= \sum_{i=0}^k \mathbb{P}(|\Lambda \setminus \{0\} \cap \mathcal{B}_z| = i) \tag{disjoint union} \\
&= \sum_{i=0}^k \frac{(\text{Vol}(\mathcal{B}_1) z^n / V)^i e^{-(\text{Vol}(\mathcal{B}_1) z^n / V)}}{i!} \tag{Model 2}
\end{align*}$$

which completes the proof. $\square$

**Distribution in the waterfall zone.** Let us denote by $\mathbf{X}_{\text{fall}}$ the random variable $f_{\mathcal{W}}$ under the independence heuristic. As given by [DP23b, Lemma 3] and the discussion that follows their lemma we have

**Fact 3.** $\mathbf{X}_{\text{fall}}$ follows a normal distribution of mean 0 and variance $\frac{1}{2}N$. More precisely, its probability density function $p$ is given by

$$p(x) = \frac{1}{\sqrt{\pi N}} e^{-x^2/N}.$$

We now make the refined model that $f_{\mathcal{W}}(\mathbf{y})$ follows the same distribution as $\mathbf{X}_{\text{fall}}+\mathbf{X}_{\text{floor}}$ where the distribution of $\mathbf{X}_{\text{floor}}$ is computed numerically by using Fact 2 along with Equation (21). We show in Figure 4 that the distribution of this refined model well approximates the behavior of the experimental distribution of $f_{\mathcal{W}}$ on the whole support.

**Concurrent work.** Note that very recently we have been made aware of the concurrent work [DP23a] which similarly to what we do here, uses Bessel functions to predict the score with a related approach and similar predictions (see [DP23a, §4.3]).

## REFERENCES

[AAB$^{+}$21a] Carlos Aguilar Melchor, Nicolas Aragon, Paulo Barreto, Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Shay Gueron, Tim Güneysu, Rafael Misoczki, Edoardo Persichetti, Nicolas Sendrier, Jean-Pierre Tillich, and Gilles Zémor. BIKE. Round 3 Submission to the NIST Post-Quantum Cryptography Call, v. 4.2, September 2021.
<figure><img src="image_8.png" /><figcaption>FIGURE 4. Refined estimation of the survival function (red, dash-dot line) compared to the experiments in [DP23b, §5] (green, full line) and the prediction with the standard independence assumption (blue, dashed line). (left) $q = 3329$, $n = 60$, $T = 2^{45}$, $N = 5040$ and $w = 0.0320$; (right) $q = 3329$, $n = 80$, $T = 2^{48}$, $N = 89494$ and $w = 0.0376$</figcaption></figure>

[AAB$^{+}$21b] Carlos Aguilar Melchor, Nicolas Aragon, Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Edoardo Persichetti, Gilles Zémor, and Jurjen Bos. HQC. Round 3 Submission to the NIST Post-Quantum Cryptography Call, June 2021. https://pqc-hqc.org/doc/hqc-specification_2021-06-06.pdf.

[AGS11] Carlos Aguilar, Philippe Gaborit, and Julien Schrek. A new zero-knowledge code based identification scheme with reduced communication. In Proc. IEEE Inf. Theory Workshop- ITW 2011, pages 648–652. IEEE, October 2011.

[Alb17] Martin R. Albrecht. On dual lattice attacks against small-secret LWE and parameter choices in HE-lib and SEAL. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, *Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part II*, volume 10211 of *Lecture Notes in Computer Science*, pages 103–129, 2017.

[Ar109] Erdal Arıkan. Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. *IEEE Trans. Inform. Theory*, 55(7):3051–3073, 2009.

[BCL$^{+}$19] Daniel J. Bernstein, Tung Chou, Tanja Lange, Ingo von Maurich, Rafael Mizoczki, Ruben Niederhagen, Edoardo Persichetti, Christiane Peters, Peter Schwabe, Nicolas Sendrier, Jakub Szefer, and Wang Wen. Classic McEliece: conservative code-based cryptography. https://classic.mceliece.org, March 2019. Second round submission to the NIST post-quantum cryptography call.

[BCN89] Andries E. Brouwer, Arjeh M. Cohen, and Arnold Neumaier. *Distance-Regular Graphs*. Number 18 in Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge / A Series of Modern Surveys in Mathematics. Springer Verlag Berlin Heidelberg, 1989.

[BJMM12] 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*, LNCS. Springer, 2012.

[BKW03] Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. *Journal of the ACM (JACM)*, 50(4):506–519, 2003.

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

[BM17] Leif Both and Alexander May. Optimizing BJMM with Nearest Neighbors: Full Decoding in $2^{2/21n}$ and McEliece Security. In *WCC Workshop on Coding and Cryptography*, September 2017.

[BM18] 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 2018*, volume 10786 of LNCS, pages 25–46, Fort Lauderdale, FL, USA, April 2018. Springer.

[CDMT22] Kevin Carrier, Thomas Debris-Alazard, Charles Meyer-Hilfiger, and Jean-Pierre Tillich. Statistical decoding 2.0: Reducing decoding to LPN. In *Advances in Cryptology - ASIACRYPT 2022*, LNCS. Springer, 2022.

[CST22] Kevin Carrier, Yixin Shen, and Jean-Pierre Tillich. Faster dual lattice attacks by using coding theory. Cryptology ePrint Archive, Paper 2022/1750, 2022. https://eprint.iacr.org/2022/1750.

[CVA10] Pierre-Louis Cayrel, Pascal Véron, and Sidi Mohamed El Yousfi Alaoui. A zero-knowledge identification scheme based on the *q*-ary syndrome decoding problem. In *Selected Areas in Cryptography*, pages 171–186, 2010.
[DDRT23] Thomas Debris-Alazard, Léo Ducas, Nicolas Resch, and Jean-Pierre Tillich. Smoothing codes and lattices: Systematic study and new bounds. *IEEE Trans. Inform. Theory*, 69(9):6006–6027, 2023.

[DP23a] Léo Ducas and Ludo N. Pulles. Accurate score prediction for dual attacks. preprint, November 2023. preprint.

[DP23b] Léo Ducas and Ludo N. Pulles. Does the dual-sieve attack on learning with errors even work? In Helena Handschuh and Anna Lysyanskaya, editors, *Advances in Cryptology - CRYPTO 2023*, volume 14083 of LNCS, pages 37–69, Santa Barbara, CA, USA, August 2023. Springer.

[DT17a] Thomas Debris-Alazard and Jean-Pierre Tillich. Statistical decoding. preprint, January 2017. arXiv:1701.07416.

[DT17b] Thomas Debris-Alazard and Jean-Pierre Tillich. Statistical decoding. Slides of the ISIT talk, June 2017. See https://tdalazard.io/slidesDecoStat.pdf.

[DT17c] Thomas Debris-Alazard and Jean-Pierre Tillich. Statistical decoding. In Proc. IEEE Int. Symposium Inf. Theory - ISIT 2017, pages 1798–1802, Aachen, Germany, June 2017.

[Dum86] Ilya Dumer. On syndrome decoding of linear codes. In Proceedings of the 9th All-Union Symp. on Redundancy in Information Systems, abstracts of papers (in russian), Part 2, pages 157–159, Leningrad, 1986.

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

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

[EJK20] Thomas Espitau, Antoine Joux, and Natalia Kharchenko. On a dual/hybrid approach to small secret LWE - A dual/enumeration technique for learning with errors and application to security estimates of FHE schemes. In Karthikeyan Bhargavan, Elisabeth Oswald, and Manoj Prabhakaran, editors, Progress in Cryptology - INDOCRYPT 2020 - 21st International Conference on Cryptology in India, Bangalore, India, December 13-16, 2020, Proceedings, volume 12578 of Lecture Notes in Computer Science, pages 440–462. Springer, 2020.

[EKM17] Andre Esser, Robert Kübler, and Alexander May. LPN decoded. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology - CRYPTO 2017, volume 10402 of LNCS, pages 486–514, Santa Barbara, CA, USA, August 2017. Springer.

[Ess22] Andre Esser. Revisiting nearest-neighbor-based information set decoding. Cryptology ePrint Archive, Paper 2022/1328, 2022. https://eprint.iacr.org/2022/1328.

[FJR22] Thibauld Feneuil, Antoine Joux, and Matthieu Rivain. Syndrome decoding in the head: Shorter signatures from zero-knowledge proofs. IACR Cryptol. ePrint Arch., page 188, 2022.

[GJ21] Qian Guo and Thomas Johansson. Faster dual lattice attacks for solving LWE with applications to CRYSTALS. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6-10, 2021, Proceedings, Part IV, volume 13093 of Lecture Notes in Computer Science, pages 33–62. Springer, 2021.

[GJL14] Qian Guo, Thomas Johansson, and Carl Löndahl. Solving LPN using covering codes. In Advances in Cryptology - ASIACRYPT 2014, volume 8873 of LNCS, pages 1–20. Springer, 2014.

[Gol17] Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017.

[GPS22] Shay Gueron, Edoardo Persichetti, and Paolo Santini. Designing a practical code-based signature scheme from zero-knowledge proofs with trusted setup. Cryptogr., 6(1):5, 2022.

[Gre66] Richard R. Green. A serial orthogonal decoder. JPL Space Programs Summary, 37-39-IV:247–253, 1966.

[Jab01] Abdulrahman Al Jabri. A statistical decoding algorithm for general linear block codes. In Bahram Honary, editor, Cryptography and coding. Proceedings of the 8th IMA International Conference, volume 2260 of LNCS, pages 1–8, Cirencester, UK, December 2001. Springer.

[KS21] Naomi Kirshner and Alex Samorodnitsky. A moment ratio bound for polynomials and some extremal properties of krawchouk polynomials and hamming spheres. IEEE Trans. Inform. Theory, 67(6):3509–3541, 2021.

[KU10] Satish B. Korada and Rüdiger Urbanke. Polar codes are optimal for lossy source coding. IEEE Trans. Inform. Theory, 56(4):1751–1768, 2010.

[LF06] Éric Levieil and Pierre-Alain Fouque. An improved LPN algorithm. In Proceedings of the 5th international conference on Security and Cryptography for Networks, volume 4116 of LNCS, pages 348–359. Springer, 2006.

[MAT22] MATZOV. Report on the Security of LWE: Improved Dual Lattice Attack, April 2022.

[McE78] Robert J. McEliece. A Public-Key System Based on Algebraic Coding Theory, pages 114–116. Jet Propulsion Lab, 1978. DSN Progress Report 44.

[MMT11] 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 LNCS, pages 107–124. Springer, 2011.

[MO15] 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 LNCS, pages 203–228. Springer, 2015.
[MR09] Daniele Micciancio and Oded Regev. Lattice-based cryptography. In *Post-quantum cryptography*, pages 147–191. Springer, 2009.

[MS86] Florence J. MacWilliams and Neil J. A. Sloane. *The Theory of Error-Correcting Codes*. North-Holland, Amsterdam, fifth edition, 1986.

[MT23] Charles Meyer-Hilfiger and Jean-Pierre Tillich. Rigorous foundations for dual attacks in coding theory. In *Theory of Cryptography Conference, TCC 2023*, LNCS. Springer Verlag, December 2023. to appear.

[Ove06] Raphael Overbeck. Statistical decoding revisited. In Reihaneh Safavi-Naini Lynn Batten, editor, *Information security and privacy : 11th Australasian conference, ACISP 2006*, volume 4058 of LNCS, pages 283–294. Springer, 2006.

[Pra62] Eugene Prange. The use of information sets in decoding cyclic codes. *IRE Transactions on Information Theory*, 8(5):5–9, 1962.

[PS23] Amaury Pouly and Yixin Shen. Provable dual attacks on learning with errors. Cryptology ePrint Archive, Paper 2023/1508, 2023. https://eprint.iacr.org/2023/1508.

[Şaş11] Eren Şaşoğlu. Polarization and polar codes. *Foundations and Trends in Communications and Information Theory*, 8(4):259–381, 2011.

[Ste88] 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 LNCS, pages 106–113. Springer, 1988.

[Ste93] Jacques Stern. A new identification scheme based on syndrome decoding. In D.R. Stinson, editor, *Advances in Cryptology - CRYPTO'93*, volume 773 of LNCS, pages 13–21. Springer, 1993.

[TV12] Ido Tal and Alexander Vardy. List decoding of polar codes. *CoRR*, abs/1206.0050, 2012.

[Vér96] Pascal Véron. Improved identification schemes based on error-correcting codes. *Appl. Algebra Eng. Commun. Comput.*, 8(1):57–69, 1996.

[vL99] Jacobus Hendricus van Lint. *Introduction to coding theory*. Graduate texts in mathematics. Springer, 3rd edition edition, 1999.

[WE23] Andreas Wiemers and Stephan Ehlen. A remark on the independence heuristic in the dual attack. IACR Cryptology ePrint Archive, Report2023/1238, August 2023. http://eprint.iacr.org/2023/1238.
APPENDIX A. PROOF OF PROPOSITION 2

Let us first recall this proposition

**Proposition 2.** Suppose that the parameters are such that for some constant $\alpha > 0$

$$ \frac{\binom{n-s}{w} \binom{s}{t_{\text{aux}}}}{2^{k-k_{\text{aux}}}} = \omega\left(\frac{n^{\alpha}}{\delta^2}\right) \quad \text{where} \quad \delta \stackrel{\text{def}}{=} \frac{K_w^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u)}{\binom{n-s}{w} \binom{s}{t_{\text{aux}}}}. \qquad (7) $$

Moreover suppose that

$$ \frac{\binom{n-s}{w} \binom{s}{t_{\text{aux}}}}{2^k} = \mathcal{O}(n^\alpha) \quad \text{and} \quad \frac{\binom{s}{t_{\text{aux}}}}{2^{s-k_{\text{aux}}}} = \mathcal{O}(n^\alpha). \qquad (8) $$

Let $\mathcal{N}$ be a set of $n-s$ positions in $\llbracket 1, n \rrbracket$ and $\mathcal{P} \stackrel{\text{def}}{=} \llbracket 1, n \rrbracket \setminus \mathcal{N}$. Let $\mathbf{e}$ be a vector of weight $u$ on $\mathcal{N}$ and $t-u$ on $\mathcal{P}$. Let $\mathcal{C}$ and $\mathcal{C}_{\text{aux}}$ be $[n, k]$ and $[s, k_{\text{aux}}]$ linear codes respectively. Let us choose $(\mathbf{c}_{\text{aux}}, \mathbf{h})$ uniformly at random in

$$ \tilde{\mathcal{H}} = \{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \in \mathcal{C}^{\perp} \times \mathcal{C}_{\text{aux}} : |\mathbf{h}_{\mathcal{N}}| = w \text{ and } |\mathbf{h}_{\mathcal{P}} + \mathbf{c}_{\text{aux}}| = t_{\text{aux}}\}. $$

Then for a proportion $1-o(1)$ of codes $\mathcal{C}_{\text{aux}}$ and $\mathcal{C}$ we have that

$$ \text{bias}_{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \stackrel{\$}{\leftarrow} \tilde{\mathcal{H}}} (\langle \mathbf{c}_{\text{aux}} + \mathbf{h}_{\mathcal{P}}, \mathbf{e}_{\mathcal{P}} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle) = \delta(1 + o(1)). $$

The proof of this Proposition 2 will be a consequence of the following lemma.

**Lemma 2.** Let $w, s, k, k_{\text{aux}}, t_{\text{aux}}, n \in \mathbb{N}$ be such that (for some constant $a > 0$)

$$ \frac{\binom{n-s}{w} \binom{s}{t_{\text{aux}}}}{2^k} = \mathcal{O}(n^\alpha) \quad \text{and} \quad \frac{\binom{s}{t_{\text{aux}}}}{2^{s-k_{\text{aux}}}} = \mathcal{O}(n^\alpha) \qquad (22) $$

Let $\mathcal{N}$ be a fixed set of $n-s$ positions in $\llbracket 1, n \rrbracket$ and $\mathcal{P} \stackrel{\text{def}}{=} \llbracket 1, n \rrbracket \setminus \mathcal{N}$. Let $\mathbf{e} \in \mathbb{F}_2^n$ be some error of weight $u$ on $\mathcal{N}$.

Assume that $\mathcal{C}$ is an $[n, k]$-linear code chosen by picking an $(n-k) \times n$ binary parity-check matrix $\mathbf{H}$ uniformly at random and that $\mathcal{C}_{\text{aux}}$ is chosen by picking an $(s-k_{\text{aux}}) \times s$ binary parity-check matrix $\mathbf{H}_{\text{aux}}$ uniformly at random. Let us define for $b \in \{0, 1\}$,

$$ E_b \stackrel{\text{def}}{=} |\{(\mathbf{e}', \mathbf{h}) \in \mathcal{S}_{t_{\text{aux}}}^s \times \mathcal{C}^{\perp} : |\mathbf{h}_{\mathcal{N}}| = w \text{ and } \mathbf{e}' + \mathbf{h}_{\mathcal{P}} \in \mathcal{C}_{\text{aux}}, \langle \mathbf{e}', \mathbf{e}_{\mathcal{P}} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle = b \}|, $$

$$ E'_b \stackrel{\text{def}}{=} |\{(\mathbf{e}', \mathbf{h}) \in \mathcal{S}_{t_{\text{aux}}}^s \times \mathbb{F}_2^n : |\mathbf{h}_{\mathcal{N}}| = w \text{ and } \langle \mathbf{e}', \mathbf{e}_{\mathcal{P}} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle = b \}|. $$

Then,

$$ \mathbb{E}_{\mathbf{H}, \mathbf{H}_{\text{aux}}} (E_b) = \Theta(1) \frac{E'_b}{2^{k+s-k_{\text{aux}}}} \qquad (23) $$

$$ \mathrm{Var}_{\mathbf{H}, \mathbf{H}_{\text{aux}}} (E_b) = \mathcal{O}(n^\alpha) \frac{E'_b}{2^{k+s-k_{\text{aux}}}} \qquad (24) $$

*Proof.* Let $\mathbf{1}_{\mathbf{e}', \mathbf{h}}$ be the indicator function of the event $"\mathbf{h} \in \mathcal{C}^{\perp}$ and $\mathbf{e}' + \mathbf{h}_{\mathcal{P}} \in \mathcal{C}_{\text{aux}}$". Define

$$ \mathcal{E}_b \stackrel{\text{def}}{=} \{(\mathbf{e}', \mathbf{h}) \in \mathcal{S}_{t_{\text{aux}}}^s \times \mathbb{F}_2^n : |\mathbf{h}_{\mathcal{N}}| = w \text{ and } \langle \mathbf{e}', \mathbf{e}_{\mathcal{P}} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle = b \}. $$

Notice that $E'_b = |\mathcal{E}_b|$. By definition and linearity of the expectation

$$ \begin{aligned} \mathbb{E}_{\mathbf{H}, \mathbf{H}_{\text{aux}}} (E_b) &= \mathbb{E}_{\mathbf{H}, \mathbf{H}_{\text{aux}}} \left( \sum_{(\mathbf{e}', \mathbf{h}) \in \mathcal{E}_b} \mathbf{1}_{\mathbf{e}', \mathbf{h}} \right) \\ &= \sum_{(\mathbf{e}', \mathbf{h}) \in \mathcal{E}_b} \mathbb{E}_{\mathbf{H}, \mathbf{H}_{\text{aux}}} (\mathbf{1}_{\mathbf{e}', \mathbf{h}}) \\ &= \sum_{(\mathbf{e}', \mathbf{h}) \in \mathcal{E}_b} \mathbb{P}_{\mathbf{H}, \mathbf{H}_{\text{aux}}} (\mathbf{h} \in \mathcal{C}^{\perp}, \mathbf{h}_{\mathcal{P}} + \mathbf{e}' \in \mathcal{C}_{\text{aux}}) \end{aligned} \qquad (25) $$
We have that,

$$ \mathbb{P}_{\mathbf{H},\mathbf{H}_{\text{aux}}} (\mathbf{h} \in \mathcal{C}^{\perp}, \mathbf{h}_{\mathcal{P}} + \mathbf{e}' \in \mathcal{C}_{\text{aux}}) = \left\{ \begin{array}{ll} \frac{1}{2^{k+s-k_{\text{aux}}}} & \text{if } \mathbf{h}_{\mathcal{P}} + \mathbf{e}' \neq \mathbf{0} \\ \frac{1}{2^k} & \text{otherwise.} \end{array} \right. \quad (26) $$

Indeed, notice that events “$\mathbf{h} \in \mathcal{C}^{\perp}$” and “$\mathbf{h}_{\mathcal{P}} + \mathbf{e}' \in \mathcal{C}_{\text{aux}}$” are independent. Furthermore, $\mathbf{h}$ cannot be equal to $\mathbf{0}$ as $|\mathbf{h}_{\mathcal{P}}| = w > 0$. Therefore,

$$ \begin{aligned} \mathbb{P}_{\mathbf{H},\mathbf{H}_{\text{aux}}} (\mathbf{h} \in \mathcal{C}^{\perp}, \mathbf{h}_{\mathcal{P}} + \mathbf{e}' \in \mathcal{C}_{\text{aux}}) &= \mathbb{P}_{\mathbf{H}} (\mathbf{h} \in \mathcal{C}^{\perp}) \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{P}} + \mathbf{e}' \in \mathcal{C}_{\text{aux}}) \\ &= \frac{1}{2^k} \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{P}} + \mathbf{e}' \in \mathcal{C}_{\text{aux}}) \end{aligned} $$

Now, plugging Equation (26) in (25) leads to,

$$ \begin{aligned} \mathbb{E}_{\mathbf{H},\mathbf{H}_{\text{aux}}} (E_b) &= \sum_{\substack{(\mathbf{e}',\mathbf{h}) \in \mathcal{E}_b \\ \mathbf{h}_{\mathcal{P}} \neq \mathbf{e}'}} \frac{1}{2^{k+s-k_{\text{aux}}}} + \sum_{\substack{(\mathbf{e}',\mathbf{h}) \in \mathcal{E}_b \\ \mathbf{h}_{\mathcal{P}} = \mathbf{e}'}} \frac{1}{2^k} \\ &= \sum_{\mathbf{e}' \in S_{\text{aux}}^s} \left( \frac{|\mathcal{E}_{b,1}^{\mathbf{e}'}|}{2^{k+s-k_{\text{aux}}}} + \frac{|\mathcal{E}_{b,2}^{\mathbf{e}'}|}{2^k} \right) \end{aligned} \quad (27) $$

where for a fixed $\mathbf{e}'$,

$$ \mathcal{E}_{b,1}^{\mathbf{e}'} \stackrel{\text{def}}{=} \{ \mathbf{h} \in \mathbb{F}_2^n : (\mathbf{e}', \mathbf{h}) \in \mathcal{E}_b \text{ and } \mathbf{h}_{\mathcal{P}} \neq \mathbf{e}' \}, \quad (28) $$

$$ \mathcal{E}_{b,2}^{\mathbf{e}'} \stackrel{\text{def}}{=} \{ \mathbf{h} \in \mathbb{F}_2^n : (\mathbf{e}', \mathbf{h}) \in \mathcal{E}_b \text{ and } \mathbf{h}_{\mathcal{P}} = \mathbf{e}' \}. \quad (29) $$

Notice that for any $\mathbf{e}'$,

$$ |\mathcal{E}_{b,1}| = \frac{|\mathcal{E}_{b,2}|}{2^s} \quad (30) $$

It is readily seen that,

$$ |\mathcal{E}_b| = \sum_{\mathbf{e}' \in S_{\text{aux}}^s} \left( |\mathcal{E}_{b,1}^{\mathbf{e}'}| + |\mathcal{E}_{b,2}^{\mathbf{e}'}| \right) $$

which implies that

$$ \sum_{\mathbf{e}' \in S_{\text{aux}}^s} |\mathcal{E}_{b,1}^{\mathbf{e}'}| = \frac{|\mathcal{E}_b|}{1 + \frac{1}{2^s}} = \Theta(1) |\mathcal{E}_b| \quad \text{and} \quad \sum_{\mathbf{e}' \in S_{\text{aux}}^s} |\mathcal{E}_{b,2}^{\mathbf{e}'}| = \frac{|\mathcal{E}_b|}{2^s - 1} = \Theta(2^{-s}) |\mathcal{E}_b| $$

Plugging this into Equation (27) leads to,

$$ \mathbb{E}_{\mathbf{H},\mathbf{H}_{\text{aux}}} (E_b) = \Theta(1) \frac{|\mathcal{E}_b|}{2^{k+s-k_{\text{aux}}}} + \Theta(1) \frac{|\mathcal{E}_b|}{2^{k+s}} = \Theta(1) \frac{|\mathcal{E}_b|}{2^{k+s-k_{\text{aux}}}} \quad (31) $$

which shows Equation (23). Let us show now Equation (24). By definition

$$ \begin{aligned} \operatorname{Var}(E_b) &= \sum_{(\mathbf{e}',\mathbf{h}) \in \mathcal{E}_b} \operatorname{Var}(\mathbf{1}_{\mathbf{e}',\mathbf{h}}) + \sum_{\substack{(\mathbf{e}'_0,\mathbf{h}^0), (\mathbf{e}'_1,\mathbf{h}^1) \in \mathcal{E}_b \\ (\mathbf{e}'_0,\mathbf{h}^0) \neq (\mathbf{e}'_1,\mathbf{h}^1)}} \mathbb{E}(\mathbf{1}_{\mathbf{e}'_0,\mathbf{h}^0} \mathbf{1}_{\mathbf{e}'_1,\mathbf{h}^1}) - \mathbb{E}(\mathbf{1}_{\mathbf{e}'_0,\mathbf{h}^0}) \mathbb{E}(\mathbf{1}_{\mathbf{e}'_1,\mathbf{h}^1}) \\ &\le \frac{E_b'}{2^{k+s-k_{\text{aux}}}} + \sum_{\substack{(\mathbf{e}'_0,\mathbf{h}^0), (\mathbf{e}'_1,\mathbf{h}^1) \in \mathcal{E}_b \\ (\mathbf{e}'_0,\mathbf{h}^0) \neq (\mathbf{e}'_1,\mathbf{h}^1)}} \mathbb{E}(\mathbf{1}_{\mathbf{e}'_0,\mathbf{h}^0} \mathbf{1}_{\mathbf{e}'_1,\mathbf{h}^1}) - \mathbb{E}(\mathbf{1}_{\mathbf{e}'_0,\mathbf{h}^0}) \mathbb{E}(\mathbf{1}_{\mathbf{e}'_1,\mathbf{h}^1}) \end{aligned} $$

where we used that $\operatorname{Var}(\mathbf{1}_{\mathbf{e}',\mathbf{h}}) \le \mathbb{E}(\mathbf{1}_{\mathbf{e},\mathbf{h}}^2) = \mathbb{E}(\mathbf{1}_{\mathbf{e},\mathbf{h}})$ and Equation (31).

To compute the above expectations, we will split in two cases according to $\mathcal{E}_{b,1}^{\mathbf{e}'}$ and $\mathcal{E}_{b,2}^{\mathbf{e}'}$ which are respectively defined in Equations (28) and (29). More precisely, we will fix $\mathbf{e}'_b$ and suppose that $\mathbf{h}^b$ belongs to $\mathcal{E}_{b,1}$ or $\mathcal{E}_{b,2}$. We will treat the following disjoint cases.

$$ \text{1. } \mathcal{F}_{0}^{\mathbf{e}'_0, \mathbf{e}'_1} = \{ (\mathbf{h}^0, \mathbf{h}^1) : \mathbf{h}^0 \in \mathcal{E}_{b,0}^{\mathbf{e}'_0} \text{ and } \mathbf{h}^1 \in \mathcal{E}_{b,1}^{\mathbf{e}'_1} \}, $$

$$ \text{2. } \mathcal{F}_{1}^{\mathbf{e}'_0, \mathbf{e}'_1} = \{ (\mathbf{h}^0, \mathbf{h}^1) : \mathbf{h}^0 \in \mathcal{E}_{b,2}^{\mathbf{e}'_0} \text{ and } \mathbf{h}^1 \in \mathcal{E}_{b,1}^{\mathbf{e}'_1} \} $$

$$ \text{3. } \mathcal{F}_{2}^{\mathbf{e}'_0, \mathbf{e}'_1} = \{ (\mathbf{h}^0, \mathbf{h}^1) : \mathbf{h}^0 \in \mathcal{E}_{b,1}^{\mathbf{e}'_0} \text{ and } \mathbf{h}^1 \in \mathcal{E}_{b,2}^{\mathbf{e}'_1} \} $$
$$
4. \mathcal{F}_3^{e'_0, e'_1} = \{ (\mathbf{h}^0, \mathbf{h}^1) : \mathbf{h}^0 \in \mathcal{E}_{b,2}^{e'_0} \text{ and } \mathbf{h}^1 \in \mathcal{E}_{b,2}^{e'_1} \}
$$

In particular,

$$
\begin{align}
\mathrm{Var}(E_b) \le & \frac{E_b'}{2^{k+s-k_{\mathrm{aux}}}} + \sum_{\substack{\mathbf{e}'_0, \mathbf{e}'_1 \\ \mathbf{h}^0, \mathbf{h}^1 \in \mathcal{F}_0^{\mathbf{e}'_0, \mathbf{e}'_1} \\ (\mathbf{e}'_0, \mathbf{h}^0) \neq (\mathbf{e}'_1, \mathbf{h}^1)}} \underbrace{\sum_{\substack{\mathbf{h}^0, \mathbf{h}^1 \in \mathcal{F}_0^{\mathbf{e}'_0, \mathbf{e}'_1} \\ (\mathbf{e}'_0, \mathbf{h}^0) \neq (\mathbf{e}'_1, \mathbf{h}^1)}} \mathbb{E}(\mathbf{1}_{\mathbf{e}'_0, \mathbf{h}^0} \mathbf{1}_{\mathbf{e}'_1, \mathbf{h}^1}) - \mathbb{E}(\mathbf{1}_{\mathbf{e}'_0, \mathbf{h}^0}) \mathbb{E}(\mathbf{1}_{\mathbf{e}'_1, \mathbf{h}^1})}_{\stackrel{\mathrm{def}}{=} F_0} \nonumber \\
& + \sum_{\substack{\mathbf{h}^0, \mathbf{h}^1 \in \mathcal{F}_1^{\mathbf{e}'_0, \mathbf{e}'_1} \\ (\mathbf{e}'_0, \mathbf{h}^0) \neq (\mathbf{e}'_1, \mathbf{h}^1)}} \underbrace{\sum_{\substack{\mathbf{h}^0, \mathbf{h}^1 \in \mathcal{F}_2^{\mathbf{e}'_0, \mathbf{e}'_1} \\ (\mathbf{e}'_0, \mathbf{h}^0) \neq (\mathbf{e}'_1, \mathbf{h}^1)}} \mathbb{E}(\mathbf{1}_{\mathbf{e}'_0, \mathbf{h}^0} \mathbf{1}_{\mathbf{e}'_1, \mathbf{h}^1}) - \mathbb{E}(\mathbf{1}_{\mathbf{e}'_0, \mathbf{h}^0}) \mathbb{E}(\mathbf{1}_{\mathbf{e}'_1, \mathbf{h}^1})}_{\stackrel{\mathrm{def}}{=} F_1} \nonumber \\
& + \sum_{\substack{\mathbf{h}^0, \mathbf{h}^1 \in \mathcal{F}_3^{\mathbf{e}'_0, \mathbf{e}'_1} \\ (\mathbf{e}'_0, \mathbf{h}^0) \neq (\mathbf{e}'_1, \mathbf{h}^1)}} \underbrace{\sum_{\substack{\mathbf{h}^0, \mathbf{h}^1 \in \mathcal{F}_3^{\mathbf{e}'_0, \mathbf{e}'_1} \\ (\mathbf{e}'_0, \mathbf{h}^0) \neq (\mathbf{e}'_1, \mathbf{h}^1)}} \mathbb{E}(\mathbf{1}_{\mathbf{e}'_0, \mathbf{h}^0} \mathbf{1}_{\mathbf{e}'_1, \mathbf{h}^1}) - \mathbb{E}(\mathbf{1}_{\mathbf{e}'_0, \mathbf{h}^0}) \mathbb{E}(\mathbf{1}_{\mathbf{e}'_1, \mathbf{h}^1})}_{\stackrel{\mathrm{def}}{=} F_2} \tag{32} \\
& + \sum_{\substack{\mathbf{h}^0, \mathbf{h}^1 \in \mathcal{F}_3^{\mathbf{e}'_0, \mathbf{e}'_1} \\ (\mathbf{e}'_0, \mathbf{h}^0) \neq (\mathbf{e}'_1, \mathbf{h}^1)}} \underbrace{\sum_{\substack{\mathbf{h}^0, \mathbf{h}^1 \in \mathcal{F}_3^{\mathbf{e}'_0, \mathbf{e}'_1} \\ (\mathbf{e}'_0, \mathbf{h}^0) \neq (\mathbf{e}'_1, \mathbf{h}^1)}} \mathbb{E}(\mathbf{1}_{\mathbf{e}'_0, \mathbf{h}^0} \mathbf{1}_{\mathbf{e}'_1, \mathbf{h}^1}) - \mathbb{E}(\mathbf{1}_{\mathbf{e}'_0, \mathbf{h}^0}) \mathbb{E}(\mathbf{1}_{\mathbf{e}'_1, \mathbf{h}^1})}_{\stackrel{\mathrm{def}}{=} F_3} \nonumber
\end{align}
$$

Let,

$$
\mathrm{Cov} \stackrel{\mathrm{def}}{=} F_0 + F_1 + F_2 + F_3 \quad (33)
$$

For each cases, we will split according to the following subcases.

$$
\text{i. } \mathbf{e}'_0 = \mathbf{e}'_1, \mathbf{h}^0 \neq \mathbf{h}^1 \text{ and } \mathbf{h}^0_{\mathcal{P}} = \mathbf{h}^1_{\mathcal{P}},
$$

$$
ii. \mathbf{e}'_0 = \mathbf{e}'_1, \mathbf{h}^0 \neq \mathbf{h}^1 \text{ and } \mathbf{h}^0_{\mathcal{P}} \neq \mathbf{h}^1_{\mathcal{P}},
$$

$$
iii. \mathbf{e}'_0 \neq \mathbf{e}'_1 \text{ and } \mathbf{h}^0 = \mathbf{h}^1
$$

$$
iv. \mathbf{e}'_0 \neq \mathbf{e}'_1, \mathbf{h}^0 \neq \mathbf{h}^1 \text{ and } \mathbf{h}^0_{\mathcal{P}} = \mathbf{h}^1_{\mathcal{P}}
$$

$$
v. \mathbf{e}'_0 \neq \mathbf{e}'_1, \mathbf{h}^0 \neq \mathbf{h}^1, \mathbf{h}^0_{\mathcal{P}} \neq \mathbf{h}^1_{\mathcal{P}} \text{ and } \mathbf{h}^0_{\mathcal{P}} + \mathbf{e}'_0 = \mathbf{h}^1_{\mathcal{P}} + \mathbf{e}'_1
$$

$$
\text{vi. } \mathbf{e}'_0 \neq \mathbf{e}'_1, \mathbf{h}^0 \neq \mathbf{h}^1, \mathbf{h}^0_{\mathcal{P}} \neq \mathbf{h}^1_{\mathcal{P}} \text{ and } \mathbf{h}^0_{\mathcal{P}} + \mathbf{e}'_0 \neq \mathbf{h}^1_{\mathcal{P}} + \mathbf{e}'_1
$$

**Case 1:** Recall that in this case we have

$$
\mathbf{h}_{\mathcal{P}}^{0} \neq \mathbf{e}_{0}' \quad \text{and} \quad \mathbf{h}_{\mathcal{P}}^{1} \neq \mathbf{e}_{1}' \qquad (34)
$$

We have,

$$
\mathbb{E}(\mathbf{1}_{\mathbf{e}'_0, \mathbf{h}^0}) \mathbb{E}(\mathbf{1}_{\mathbf{e}'_1, \mathbf{h}^1}) = \left( \frac{1}{2^{k+s-k_{\text{aux}}}} \right)^2
$$

Let us compute $\mathbb{E}_{\mathbf{H},\mathbf{H}_{\text{aux}}} (\mathbf{1}_{\mathbf{e}'_0,\mathbf{h}^0} \mathbf{1}_{\mathbf{e}'_1,\mathbf{h}^1})$ when $(\mathbf{e}'_0, \mathbf{h}^0) \neq (\mathbf{e}'_1, \mathbf{h}^1)$. By definition

$$
\begin{align*}
\mathbb{E}_{\mathbf{H},\mathbf{H}_{\text{aux}}} (\mathbf{1}_{\mathbf{e}'_0,\mathbf{h}^0} \mathbf{1}_{\mathbf{e}'_1,\mathbf{h}^1}) &= \mathbb{P}_{\mathbf{H},\mathbf{H}_{\text{aux}}} (\mathbf{h}^0, \mathbf{h}^1 \in \mathcal{C}^{\perp}, \mathbf{h}^0_{\mathcal{P}} + \mathbf{e}'_0 \in \mathcal{C}_{\text{aux}}, \mathbf{h}^1_{\mathcal{P}} + \mathbf{e}'_1 \in \mathcal{C}_{\text{aux}}) \\
&= \mathbb{P}_{\mathbf{H},\mathbf{H}_{\text{aux}}} (\mathbf{h}^0, \mathbf{h}^1 \in \mathcal{C}^{\perp}) \mathbb{P}_{\mathbf{H},\mathbf{H}_{\text{aux}}} (\mathbf{h}^0_{\mathcal{P}} + \mathbf{e}'_0 \in \mathcal{C}_{\text{aux}}, \mathbf{h}^1_{\mathcal{P}} + \mathbf{e}'_1 \in \mathcal{C}_{\text{aux}})
\end{align*}
$$
Therefore,

$$
\begin{align}
\sum_{\substack{\mathbf{e}'_0, \mathbf{e}'_1 \\ (\mathbf{e}'_0, \mathbf{h}^0) \neq (\mathbf{e}'_1, \mathbf{h}^1)}} F_0 &= \sum_{\substack{\mathbf{e}'_0, \mathbf{e}'_1 \\ \mathbf{h}^0, \mathbf{h}^1 \in \mathcal{F}^{\mathbf{e}'_0, \mathbf{e}'_1}}} \sum_{\substack{\mathbf{h}^0, \mathbf{h}^1 \in \mathcal{F}^{\mathbf{e}'_0, \mathbf{e}'_1} \\ (\mathbf{e}'_0, \mathbf{h}^0) \neq (\mathbf{e}'_1, \mathbf{h}^1)}} \mathbb{E} \left( \mathbf{1}_{\mathbf{e}'_0, \mathbf{h}^0} \mathbf{1}_{\mathbf{e}'_1, \mathbf{h}^1} \right) - \left( \frac{1}{2^{k+s-k_{\text{aux}}}} \right)^2 \nonumber \\
&= \sum_{\substack{\mathbf{e}'_0, \mathbf{e}'_1 \\ (\mathbf{e}'_0, \mathbf{h}^0) \neq (\mathbf{e}'_1, \mathbf{h}^1)}} \sum_{\substack{\mathbf{h}^0, \mathbf{h}^1 \in \mathcal{F}^{\mathbf{e}'_0, \mathbf{e}'_1} \\ (\mathbf{e}'_0, \mathbf{h}^0) \neq (\mathbf{e}'_1, \mathbf{h}^1)}} \text{Cov}^{(0)} \tag{35}
\end{align}
$$

where,

$$
\mathrm{Cov}^{(0)} \stackrel{\text{def}}{=} \mathbb{P}_{\mathbf{H}} (\mathbf{h}^0, \mathbf{h}^1 \in \mathcal{C}^{\perp}) \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_0 \in \mathcal{C}_{\text{aux}}, \mathbf{h}_{\mathcal{D}}^1 + \mathbf{e}'_1 \in \mathcal{C}_{\text{aux}}) - \left( \frac{1}{2^{k+s-k_{\text{aux}}}} \right)^2
$$

Our aim now it to upper-bound Cov<sup>(0)</sup> according to the above 6 sub-cases.

**Sub-case i.** Suppose that $\mathbf{e}'_0 = \mathbf{e}'_1$, $\mathbf{h}^0 \neq \mathbf{h}^1$ and $\mathbf{h}_{\mathcal{D}}^0 = \mathbf{h}_{\mathcal{D}}^1$. We have

$$
\begin{align*}
\mathrm{Cov}^{(0)} &= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_0 \in \mathcal{C}_{\text{aux}}, \mathbf{h}_{\mathcal{D}}^1 + \mathbf{e}'_1 \in \mathcal{C}_{\text{aux}}) - \left( \frac{1}{2^{k+s-k_{\text{aux}}}} \right)^2 \\
&= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_0 \in \mathcal{C}_{\text{aux}}) - \left( \frac{1}{2^{k+s-k_{\text{aux}}}} \right)^2 \quad (\text{as } \mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_0 = \mathbf{h}_{\mathcal{D}}^1 + \mathbf{e}'_1) \\
&= \frac{1}{2^{2k}} \frac{1}{2^{s-k_{\text{aux}}}} - \left( \frac{1}{2^{k+s-k_{\text{aux}}}} \right)^2
\end{align*}
$$

where in the last line we used Equation (34). Therefore, in that case

$$
\mathrm{Cov}^{(0)} \le \frac{1}{2^{2k}} \frac{1}{2^{s-k_{\mathrm{aux}}}}.
$$

**Sub-case ii.** Suppose that $\mathbf{e}'_0 = \mathbf{e}'_1$, $\mathbf{h}^0 \neq \mathbf{h}^1$ and $\mathbf{h}_{\mathcal{D}}^0 \neq \mathbf{h}_{\mathcal{D}}^1$. We have

$$
\begin{align}
\mathrm{Cov}^{(0)} &= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^{0} + \mathbf{e}'_{0} \in \mathcal{C}_{\text{aux}}, \mathbf{h}_{\mathcal{D}}^{1} + \mathbf{e}'_{1} \in \mathcal{C}_{\text{aux}}) - \left( \frac{1}{2^{k+s-k_{\text{aux}}}} \right)^{2} \nonumber \\
&= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^{0} + \mathbf{e}'_{0} \in \mathcal{C}_{\text{aux}}) \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^{1} + \mathbf{e}'_{1} \in \mathcal{C}_{\text{aux}}) - \left( \frac{1}{2^{k+s-k_{\text{aux}}}} \right)^{2} \tag{36}
\end{align}
$$

where in the last line we used that $\mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_0 \neq \mathbf{h}_{\mathcal{D}}^1 + \mathbf{e}'_1$ showing that these two vectors are linearly independent (we work in $\mathbb{F}_2$), and thus that both events are independent. But, as they are different from $\mathbf{0}$ (according to Equation (34)) we have for ($b \in \{0, 1\}$)

$$
\mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^{b} + \mathbf{e}'_{b} \in \mathcal{C}_{\text{aux}}) = \frac{1}{2^{s-k_{\text{aux}}}}
$$

Therefore, plugging this in Equation (36) leads to

$$
\mathrm{Cov}^{(0)} = 0.
$$

**Sub-case iii.** Suppose that $\mathbf{e}'_0 \neq \mathbf{e}'_1$, $\mathbf{h}^0 = \mathbf{h}^1$. In that case,

$$
\begin{align*}
\mathrm{Cov}^{(0)} &= \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}^0 \in \mathcal{C}^{\perp}) \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_0 \in \mathcal{C}_{\text{aux}}, \mathbf{h}_{\mathcal{D}}^1 + \mathbf{e}'_1 \in \mathcal{C}_{\text{aux}}) - \left( \frac{1}{2^{k+s-k_{\text{aux}}}} \right)^2 \\
&= \frac{1}{2^k} \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_0 \in \mathcal{C}_{\text{aux}}) \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^1 + \mathbf{e}'_1 \in \mathcal{C}_{\text{aux}}) - \left( \frac{1}{2^{k+s-k_{\text{aux}}}} \right)^2 \\
&= \frac{1}{2^k} \left( \frac{1}{2^{s-k_{\text{aux}}}} \right)^2 - \left( \frac{1}{2^{k+s-k_{\text{aux}}}} \right)^2
\end{align*}
$$
where in the second equality we used that $\mathbf{h}_{\mathscr{D}}^0 + \mathbf{e}'_0 \neq \mathbf{h}_{\mathscr{D}}^1 + \mathbf{e}'_1$ and are different from 0 (according to Equation (34)) which implies that both events are independent. Therefore, in that case

$$ \mathrm{Cov}^{(0)} \leq \frac{1}{2^{k+2s-2k_{\mathrm{aux}}}} \qquad (37) $$

**Sub-case iv.** Suppose that $\mathbf{e}'_0 \neq \mathbf{e}'_1$, $\mathbf{h}^0 \neq \mathbf{h}^1$, and $\mathbf{h}_{\mathscr{D}}^0 = \mathbf{h}_{\mathscr{D}}^1$. In that case,

$$
\begin{align*}
\mathrm{Cov}^{(0)} &= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}_{\mathscr{D}}^0 + \mathbf{e}'_0 \in \mathcal{C}_{\mathrm{aux}}, \mathbf{h}_{\mathscr{D}}^0 + \mathbf{e}'_1 \in \mathcal{C}_{\mathrm{aux}}) - \left( \frac{1}{2^{k+s-k_{\mathrm{aux}}}} \right)^2 \\
&= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}_{\mathscr{D}}^0 + \mathbf{e}'_0 \in \mathcal{C}_{\mathrm{aux}}) \mathbb{P}_{\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}_{\mathscr{D}}^0 + \mathbf{e}'_1 \in \mathcal{C}_{\mathrm{aux}}) - \left( \frac{1}{2^{k+s-k_{\mathrm{aux}}}} \right)^2 \\
&= \left( \frac{1}{2^{k+s-k_{\mathrm{aux}}}} \right)^2 - \left( \frac{1}{2^{k+s-k_{\mathrm{aux}}}} \right)^2 \\
&= 0
\end{align*}
$$

where in the second equality we used that $\mathbf{h}_{\mathscr{D}}^0 + \mathbf{e}'_0 = \mathbf{h}_{\mathscr{D}}^1 + \mathbf{e}'_0 \neq \mathbf{h}_{\mathscr{D}}^1 + \mathbf{e}'_1$ which implies that both events are independent.

**Sub-case v.** Suppose that $\mathbf{e}'_0 \neq \mathbf{e}'_1$, $\mathbf{h}^0 \neq \mathbf{h}^1$, $\mathbf{h}_{\mathscr{D}}^0 \neq \mathbf{h}_{\mathscr{D}}^1$ and $\mathbf{h}_{\mathscr{D}}^0 + \mathbf{e}'_0 = \mathbf{h}_{\mathscr{D}}^1 + \mathbf{e}'_1$. We have

$$
\begin{align*}
\mathrm{Cov}^{(0)} &= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}_{\mathscr{D}}^0 + \mathbf{e}'_0 \in \mathcal{C}_{\mathrm{aux}}) - \left( \frac{1}{2^{k+s-k_{\mathrm{aux}}}} \right)^2 \\
&= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}_{\mathscr{D}}^0 + \mathbf{e}'_0 \in \mathcal{C}_{\mathrm{aux}}) - \left( \frac{1}{2^{k+s-k_{\mathrm{aux}}}} \right)^2 \\
&= \frac{1}{2^{2k}} \frac{1}{2^{s-k_{\mathrm{aux}}}} - \left( \frac{1}{2^{k+s-k_{\mathrm{aux}}}} \right)^2
\end{align*}
$$

Therefore,

$$ \mathrm{Cov}^{(0)} \leq \frac{1}{2^{2k+s-k_{\mathrm{aux}}}} $$

**Sub-case vi.** Suppose that $\mathbf{e}'_0 \neq \mathbf{e}'_1$, $\mathbf{h}^0 \neq \mathbf{h}^1$, $\mathbf{h}_{\mathscr{D}}^0 \neq \mathbf{h}_{\mathscr{D}}^1$ and $\mathbf{h}_{\mathscr{D}}^0 + \mathbf{e}'_0 \neq \mathbf{h}_{\mathscr{D}}^1 + \mathbf{e}'_1$. In that case we can write

$$
\begin{align*}
\mathrm{Cov}^{(0)} &= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}_{\mathscr{D}}^0 + \mathbf{e}'_0 \in \mathcal{C}_{\mathrm{aux}}, \mathbf{h}_{\mathscr{D}}^1 + \mathbf{e}'_1 \in \mathcal{C}_{\mathrm{aux}}) - \left( \frac{1}{2^{k+s-k_{\mathrm{aux}}}} \right)^2 \\
&= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}_{\mathscr{D}}^0 + \mathbf{e}'_0 \in \mathcal{C}_{\mathrm{aux}}) \mathbb{P}_{\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}_{\mathscr{D}}^1 + \mathbf{e}'_1 \in \mathcal{C}_{\mathrm{aux}}) - \left( \frac{1}{2^{k+s-k_{\mathrm{aux}}}} \right)^2 \\
&= \left( \frac{1}{2^{k+s-k_{\mathrm{aux}}}} \right)^2 - \left( \frac{1}{2^{k+s-k_{\mathrm{aux}}}} \right)^2
\end{align*}
$$

Therefore we obtain,

$$ \mathrm{Cov}^{(0)} = 0. $$

**Case 2:** Recall that in this case we have

$$ \mathbf{h}_{\mathscr{D}}^0 = \mathbf{e}'_0 \quad \text{and} \quad \mathbf{h}_{\mathscr{D}}^1 \neq \mathbf{e}'_1 \qquad (38) $$

We have,

$$ \mathbb{E}(\mathbf{1}_{\mathbf{e}'_0, \mathbf{h}^0}) \mathbb{E}(\mathbf{1}_{\mathbf{e}'_1, \mathbf{h}^1}) = \frac{1}{2^k} \frac{1}{2^{k+s-k_{\mathrm{aux}}}} = \frac{1}{2^{2k+s-k_{\mathrm{aux}}}} $$

Let us compute $\mathbb{E}_{\mathbf{H},\mathbf{H}_{\mathrm{aux}}} (\mathbf{1}_{\mathbf{e}'_0,\mathbf{h}^0} \mathbf{1}_{\mathbf{e}'_1,\mathbf{h}^1})$ when $(\mathbf{e}'_0, \mathbf{h}^0) \neq (\mathbf{e}'_1, \mathbf{h}^1)$. By definition

$$
\begin{align*}
\mathbb{E}_{\mathbf{H},\mathbf{H}_{\mathrm{aux}}} (\mathbf{1}_{\mathbf{e}'_0,\mathbf{h}^0} \mathbf{1}_{\mathbf{e}'_1,\mathbf{h}^1}) &= \mathbb{P}_{\mathbf{H},\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}^0, \mathbf{h}^1 \in \mathcal{C}^{\perp}, \mathbf{h}_{\mathscr{D}}^0 + \mathbf{e}'_0 \in \mathcal{C}_{\mathrm{aux}}, \mathbf{h}_{\mathscr{D}}^1 + \mathbf{e}'_1 \in \mathcal{C}_{\mathrm{aux}}) \\
&= \mathbb{P}_{\mathbf{H},\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}^0, \mathbf{h}^1 \in \mathcal{C}^{\perp}) \mathbb{P}_{\mathbf{H},\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}_{\mathscr{D}}^0 + \mathbf{e}'_0 \in \mathcal{C}_{\mathrm{aux}}, \mathbf{h}_{\mathscr{D}}^1 + \mathbf{e}'_1 \in \mathcal{C}_{\mathrm{aux}})
\end{align*}
$$
Therefore,

$$
\begin{align}
\sum_{\mathbf{e}'_0, \mathbf{e}'_1} F_1 &= \sum_{\mathbf{e}'_0, \mathbf{e}'_1} \mathbb{E} (\mathbf{1}_{\mathbf{e}'_0, \mathbf{h}^0} \mathbf{1}_{\mathbf{e}'_1, \mathbf{h}^1}) - \frac{1}{2^{2k+s-k_{\text{aux}}}} \nonumber \\
&= \sum_{\mathbf{e}'_0, \mathbf{e}'_1} \sum_{\mathbf{h}^0, \mathbf{h}^1 \in \mathcal{F}_1^{\mathbf{e}'_0, \mathbf{e}'_1}} \mathrm{Cov}^{(1)} \tag{39} \\
&\qquad (\mathbf{e}'_0, \mathbf{h}^0) \neq (\mathbf{e}'_1, \mathbf{h}^1) \nonumber
\end{align}
$$

where,

$$
\mathrm{Cov}^{(1)} \stackrel{\text{def}}{=} \mathbb{P}_{\mathbf{H}}(\mathbf{h}^0, \mathbf{h}^1 \in \mathcal{C}^{\perp}) \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_0 \in \mathcal{C}_{\text{aux}}, \mathbf{h}_{\mathcal{D}}^1 + \mathbf{e}'_1 \in \mathcal{C}_{\text{aux}}) - \frac{1}{2^{2k+s-k_{\text{aux}}}}
$$

Our aim now it to upper-bound Cov(1) according to the above 6 sub-cases.

**Sub-case i.** Suppose that $\mathbf{e}'_0 = \mathbf{e}'_1$, $\mathbf{h}^0 \neq \mathbf{h}^1$ and $\mathbf{h}_{\mathcal{D}}^0 = \mathbf{h}_{\mathcal{D}}^1$. This subcase is impossible according to Equation (38). Therefore,

$$
\mathrm{Cov}^{(1)} = 0.
$$

**Sub-case ii.** Suppose that $\mathbf{e}'_0 = \mathbf{e}'_1$, $\mathbf{h}^0 \neq \mathbf{h}^1$ and $\mathbf{h}_{\mathcal{D}}^0 \neq \mathbf{h}_{\mathcal{D}}^1$. We have

$$
\begin{align}
\mathrm{Cov}^{(1)} &= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_0 \in \mathcal{C}_{\text{aux}}, \mathbf{h}_{\mathcal{D}}^1 + \mathbf{e}'_1 \in \mathcal{C}_{\text{aux}}) - \frac{1}{2^{2k+s-k_{\text{aux}}}} \nonumber \\
&= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^1 + \mathbf{e}'_1 \in \mathcal{C}_{\text{aux}}) - \frac{1}{2^{2k+s-k_{\text{aux}}}} \tag{40}
\end{align}
$$

where in the last line we used that $\mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_0 \neq \mathbf{h}_{\mathcal{D}}^1 + \mathbf{e}'_1$ showing that these two vectors are linearly independent (we work in $\mathbb{F}_2$), and thus that both events are independent. Furthermore, we also used that $\mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_0 = \mathbf{0}$ according to Equation (38). But,

$$
\mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^{1} + \mathbf{e}'_{1} \in \mathcal{C}_{\text{aux}}) = \frac{1}{2^{s-k_{\text{aux}}}}
$$

Therefore, plugging this in Equation (40) leads to

$$
\mathrm{Cov}^{(1)} = 0.
$$

**Sub-case iii.** Suppose that $\mathbf{e}'_0 \neq \mathbf{e}'_1$, $\mathbf{h}^0 = \mathbf{h}^1$. In that case,

$$
\begin{align*}
\mathrm{Cov}^{(1)} &= \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}^0 \in \mathcal{C}^{\perp}) \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_0 \in \mathcal{C}_{\text{aux}}, \mathbf{h}_{\mathcal{D}}^1 + \mathbf{e}'_1 \in \mathcal{C}_{\text{aux}}) - \frac{1}{2^{2k+s-k_{\text{aux}}}} \\
&= \frac{1}{2^k} \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_0 \in \mathcal{C}_{\text{aux}}) \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_1 \in \mathcal{C}_{\text{aux}}) - \frac{1}{2^{2k+s-k_{\text{aux}}}} \\
&= \frac{1}{2^k} \frac{1}{2^{s-k_{\text{aux}}}} - \frac{1}{2^{2k+s-k_{\text{aux}}}}
\end{align*}
$$

where in the second equality we used that $\mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_0 \neq \mathbf{h}_{\mathcal{D}}^1 + \mathbf{e}'_1$ which implies that both events are independent. Furthermore, we also used that $\mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_0 = \mathbf{0}$ according to Equation (38). Therefore, in that case

$$
\mathrm{Cov}^{(1)} \le \frac{1}{2^{k+s-k_{\text{aux}}}} \qquad (41)
$$

**Sub-case iv.** Suppose that $\mathbf{e}'_0 \neq \mathbf{e}'_1$, $\mathbf{h}^0 \neq \mathbf{h}^1$ and $\mathbf{h}_{\mathcal{D}}^0 = \mathbf{h}_{\mathcal{D}}^1$. In that case,

$$
\begin{align*}
\mathrm{Cov}^{(1)} &= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^{0} + \mathbf{e}'_{0} \in \mathcal{C}_{\text{aux}}, \mathbf{h}_{\mathcal{D}}^{0} + \mathbf{e}'_{1} \in \mathcal{C}_{\text{aux}}) - \frac{1}{2^{2k+s-k_{\text{aux}}}} \\
&= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\text{aux}}} (\mathbf{h}_{\mathcal{D}}^{0} + \mathbf{e}'_{1} \in \mathcal{C}_{\text{aux}}) - \frac{1}{2^{2k+s-k_{\text{aux}}}} \\
&= \frac{1}{2^{2k+s-k_{\text{aux}}}} - \frac{1}{2^{2k+s-k_{\text{aux}}}} \\
&= 0
\end{align*}
$$

where in the second equality we used that $\mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_0 = \mathbf{h}_{\mathcal{D}}^1 + \mathbf{e}'_0 \neq \mathbf{h}_{\mathcal{D}}^1 + \mathbf{e}'_1$ which implies that both events are independent. Furthermore, we also used that $\mathbf{h}_{\mathcal{D}}^0 + \mathbf{e}'_0 = \mathbf{0}$ according to Equation (38).
**Sub-case v.** Suppose that $e'_0 \neq e'_1$, $h^0 \neq h^1$, $h^0_{\mathcal{D}} \neq h^1_{\mathcal{D}}$ and $h^0_{\mathcal{D}} + e'_0 = h^1_{\mathcal{D}} + e'_1$. This subcase is impossible according to Equation (38). Therefore,

$$ \mathrm{Cov}^{(1)} = 0 $$

**Sub-case vi.** Suppose that $e'_0 \neq e'_1$, $h^0 \neq h^1$, $h^0_{\mathcal{D}} \neq h^1_{\mathcal{D}}$ and $h^0_{\mathcal{D}} + e'_0 \neq h^1_{\mathcal{D}} + e'_1$. In that case we can write

$$ \begin{aligned} \mathrm{Cov}^{(0)} &= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}_{\mathcal{D}}^{0} + \mathbf{e}'_{0} \in \mathcal{C}_{\mathrm{aux}}, \mathbf{h}_{\mathcal{D}}^{1} + \mathbf{e}'_{1} \in \mathcal{C}_{\mathrm{aux}}) - \frac{1}{2^{2k+s-k_{\mathrm{aux}}}} \\ &= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}_{\mathcal{D}}^{1} + \mathbf{e}'_{1} \in \mathcal{C}_{\mathrm{aux}}) - \frac{1}{2^{2k+s-k_{\mathrm{aux}}}} \\ &= \frac{1}{2^{2k+s-k_{\mathrm{aux}}}} - \frac{1}{2^{2k+s-k_{\mathrm{aux}}}} \end{aligned} $$

Therefore we obtain,

$$ \mathrm{Cov}^{(1)} = 0. $$

**Case 3:** This situation is symmetric to Case 2.

**Case 4:** Recall that in this case we have

$$ \mathbf{h}_{\mathcal{D}}^{0} = \mathbf{e}'_{0} \quad \text{and} \quad \mathbf{h}_{\mathcal{D}}^{1} = \mathbf{e}'_{1} \qquad (42) $$

We have,

$$ \mathbb{E}(\mathbf{1}_{\mathbf{e}'_{0}, \mathbf{h}^{0}}) \mathbb{E}(\mathbf{1}_{\mathbf{e}'_{1}, \mathbf{h}^{1}}) = \frac{1}{2^{2k}} $$

Let us compute $\mathbb{E}_{\mathbf{H},\mathbf{H}_{\mathrm{aux}}} (\mathbf{1}_{\mathbf{e}'_{0},\mathbf{h}^{0}} \mathbf{1}_{\mathbf{e}'_{1},\mathbf{h}^{1}})$ when $(\mathbf{e}'_{0}, \mathbf{h}^{0}) \neq (\mathbf{e}'_{1}, \mathbf{h}^{1})$. By definition

$$ \begin{aligned} \mathbb{E}_{\mathbf{H},\mathbf{H}_{\mathrm{aux}}} (\mathbf{1}_{\mathbf{e}'_{0},\mathbf{h}^{0}} \mathbf{1}_{\mathbf{e}'_{1},\mathbf{h}^{1}}) &= \mathbb{P}_{\mathbf{H},\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}^{0}, \mathbf{h}^{1} \in \mathcal{C}^{\perp}, \mathbf{h}_{\mathcal{D}}^{0} + \mathbf{e}'_{0} \in \mathcal{C}_{\mathrm{aux}}, \mathbf{h}_{\mathcal{D}}^{1} + \mathbf{e}'_{1} \in \mathcal{C}_{\mathrm{aux}}) \\ &= \mathbb{P}_{\mathbf{H},\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}^{0}, \mathbf{h}^{1} \in \mathcal{C}^{\perp}) \mathbb{P}_{\mathbf{H},\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}_{\mathcal{D}}^{0} + \mathbf{e}'_{0} \in \mathcal{C}_{\mathrm{aux}}, \mathbf{h}_{\mathcal{D}}^{1} + \mathbf{e}'_{1} \in \mathcal{C}_{\mathrm{aux}}) \end{aligned} $$

Therefore,

$$ \begin{aligned} \sum_{\mathbf{e}'_{0}, \mathbf{e}'_{1}} F_{3} &= \sum_{\mathbf{e}'_{0}, \mathbf{e}'_{1}} \sum_{\substack{\mathbf{h}^{0}, \mathbf{h}^{1} \in \mathcal{F}_{3}^{\mathbf{e}'_{0}, \mathbf{e}'_{1}} \\ (\mathbf{e}'_{0}, \mathbf{h}^{0}) \neq (\mathbf{e}'_{1}, \mathbf{h}^{1})}} \mathbb{E} (\mathbf{1}_{\mathbf{e}'_{0}, \mathbf{h}^{0}} \mathbf{1}_{\mathbf{e}'_{1}, \mathbf{h}^{1}}) - \frac{1}{2^{2k}} \\ &= \sum_{\mathbf{e}'_{0}, \mathbf{e}'_{1}} \sum_{\substack{\mathbf{h}^{0}, \mathbf{h}^{1} \in \mathcal{F}_{3}^{\mathbf{e}'_{0}, \mathbf{e}'_{1}} \\ (\mathbf{e}'_{0}, \mathbf{h}^{0}) \neq (\mathbf{e}'_{1}, \mathbf{h}^{1})}} \mathrm{Cov}^{(3)} \end{aligned} \qquad (43) $$

where,

$$ \mathrm{Cov}^{(3)} \stackrel{\mathrm{def}}{=} \mathbb{P}_{\mathbf{H}} (\mathbf{h}^{0}, \mathbf{h}^{1} \in \mathcal{C}^{\perp}) \mathbb{P}_{\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}_{\mathcal{D}}^{0} + \mathbf{e}'_{0} \in \mathcal{C}_{\mathrm{aux}}, \mathbf{h}_{\mathcal{D}}^{1} + \mathbf{e}'_{1} \in \mathcal{C}_{\mathrm{aux}}) - \frac{1}{2^{2k}} $$

Our aim now it to upper-bound $\mathrm{Cov}^{(3)}$ according to the above 6 sub-cases.

**Sub-case i.** Suppose that $\mathbf{e}'_0 = \mathbf{e}'_1$, $h^0 \neq h^1$ and $h^0_{\mathcal{D}} = h^1_{\mathcal{D}}$. We have

$$ \begin{aligned} \mathrm{Cov}^{(3)} &= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\mathrm{aux}}} (\mathbf{h}_{\mathcal{D}}^{0} + \mathbf{e}'_{0} \in \mathcal{C}_{\mathrm{aux}}, \mathbf{h}_{\mathcal{D}}^{1} + \mathbf{e}'_{1} \in \mathcal{C}_{\mathrm{aux}}) - \frac{1}{2^{2k}} \\ &= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\mathrm{aux}}} (\mathbf{0} \in \mathcal{C}_{\mathrm{aux}}) - \frac{1}{2^{2k}} \\ &= \frac{1}{2^{2k}} - \frac{1}{2^{2k}} \end{aligned} $$

where in the second equality we used Equation (42). Therefore, in that case

$$ \mathrm{Cov}^{(3)} = 0. $$

**Sub-case ii.** Suppose that $\mathbf{e}'_0 = \mathbf{e}'_1$, $h^0 \neq h^1$ and $h^0_{\mathcal{D}} \neq h^1_{\mathcal{D}}$. According to Equation (42) this sub-case is impossible. Therefore,

$$ \mathrm{Cov}^{(3)} = 0. $$
**Sub-case iii.** Suppose that $e'_0 \neq e'_1$, $h^0 = h^1$. According to Equation (42) this sub-case is impossible. Therefore,

$$ \mathrm{Cov}^{(3)} = 0. $$

**Sub-case iv.** Suppose that $e'_0 \neq e'_1$, $h^0 \neq h^1$ and $h^0_{\mathcal{P}} = h^1_{\mathcal{P}}$. According to Equation (42) this sub-case is impossible. Therefore,

$$ \mathrm{Cov}^{(3)} = 0. $$

**Sub-case v.** Suppose that $e'_0 \neq e'_1$, $h^0 \neq h^1$, $h^0_{\mathcal{P}} \neq h^1_{\mathcal{P}}$ and $h^0_{\mathcal{P}} + e'_0 = h^1_{\mathcal{P}} + e'_1$. We have

$$ \begin{aligned} \mathrm{Cov}^{(3)} &= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\mathrm{aux}}} (h_{\mathcal{P}}^0 + e'_0 \in \mathcal{C}_{\mathrm{aux}}) - \frac{1}{2^{2k}} \\ &= \frac{1}{2^{2k}} \mathbb{P}_{\mathbf{H}_{\mathrm{aux}}} (\mathbf{0} \in \mathcal{C}_{\mathrm{aux}}) - \frac{1}{2^{2k}} \\ &= \frac{1}{2^{2k}} - \frac{1}{2^{2k}} \end{aligned} $$

where in the second equality we used Equation (42). Therefore,

$$ \mathrm{Cov}^{(3)} = 0. $$

**Sub-case vi.** Suppose that $e'_0 \neq e'_1$, $h^0 \neq h^1$, $h^0_{\mathcal{P}} \neq h^1_{\mathcal{P}}$ and $h^0_{\mathcal{P}} + e'_0 \neq h^1_{\mathcal{P}} + e'_1$. According to Equation (42) this sub-case is impossible. Therefore,

$$ \mathrm{Cov}^{(3)} = 0. $$

We are now ready to gather Cases 1, 2, 3 and 4 according to Subcases i, ii, iii, iv, v and vi. Our aim is to bound Cov that were defined in Equation 33. We can already notice that Case 4 has no impact on this sum while Cases 2 and 3 have an influence only in Subcase iii. Furthermore, ii, iv and vi have no contribution to this sum, whatever is the considered case.

Let us upper-bound Cov according to the different subcases where $\mathrm{Cov}_i$ denotes the terms involved in Cov coming from Subcase i (in particular $\mathrm{Cov}_i$ is defined as a certain sum of $\mathrm{Cov}^{(i)}$, see Equations (35), (39) and (36)).

**Subcase i:** We have,

$$ \mathrm{Cov}_1 \le \sum_{(e'_0, h^0) \in \mathcal{E}_b} \sum_{\substack{h^1:(e'_0, h^1) \in \mathcal{E}_b \\ h^1 \neq h^0, h^0_{\mathcal{P}} = h^1_{\mathcal{P}}}} \frac{1}{2^{2k}} \frac{1}{2^{s-k_{\mathrm{aux}}}} \le \sum_{(e_0, h^0) \in \mathcal{E}_b} \frac{\binom{n-s}{w}}{2^{2k+s-k_{\mathrm{aux}}}} = \frac{\binom{n-s}{w}}{2^k} \frac{E'_b}{2^{k+s-k_{\mathrm{aux}}}} $$

**Subcase ii:** We have,

$$ \mathrm{Cov}_2 = 0. $$

**Subcase iii:** We have here to split the computation here between Cases 1 and 2. Recall that they are given by

$$ \mathcal{F}_0^{e'_0, e'_1} = \{ (h^0, h^1) : h^0 \in \mathcal{E}_{b,1}^{e'_0} \text{ and } h^1 \in \mathcal{E}_{b,1}^{e'_1} \}, $$

$$ \mathcal{F}_1^{e'_0, e'_1} = \{ (h^0, h^1) : h^0 \in \mathcal{E}_{b,2}^{e'_0} \text{ and } h^1 \in \mathcal{E}_{b,1}^{e'_1} \} $$

where,

$$ \mathcal{E}_{b,1}^{e'_1} \stackrel{\mathrm{def}}{=} \{ \mathbf{h} \in \mathbb{F}_2^n : (e'_1, \mathbf{h}) \in \mathcal{E}_b \text{ and } \mathbf{h}_{\mathcal{P}} \neq e'_1 \}, $$

$$ \mathcal{E}_{b,2}^{e'_1} \stackrel{\mathrm{def}}{=} \{ \mathbf{h} \in \mathbb{F}_2^n : (e'_1, \mathbf{h}) \in \mathcal{E}_b \text{ and } \mathbf{h}_{\mathcal{P}} = e'_1 \}. $$

But recall according to Equation (30) that,

$$ |\mathcal{E}_{b,1}| = \frac{|\mathcal{E}_{b,2}|}{2^s} $$
Therefore, in Subcase iii,

$$
\begin{align*}
\mathrm{Cov}_3 &= \sum_{e'_0 \neq e'_1} \sum_{h^0 = h^1 \in \mathcal{F}_0^{e'_0, e'_1}} \mathrm{Cov}^{(0)} + 2 \sum_{e'_0 \neq e'_1} \sum_{h^0 = h^1 \in \mathcal{F}_1^{e'_0, e'_1}} \mathrm{Cov}^{(1)} \\
&= \sum_{e'_0 \neq e'_1} \sum_{h^0 = h^1 \in \mathcal{F}_0^{e'_0, e'_1}} \frac{1}{2^{k+2s-2k_{\mathrm{aux}}}} + 2 \sum_{e'_0 \neq e'_1} \sum_{h^0 = h^1 \in \mathcal{F}_1^{e'_0, e'_1}} \frac{1}{2^{k+s-k_{\mathrm{aux}}}} \quad \text{(Equations (37)) and (41)} \\
&= \sum_{e'_0 \neq e'_1} \sum_{h^0 = h^1 \in \mathcal{F}_0^{e'_0, e'_1}} \frac{1}{2^{k+2s-2k_{\mathrm{aux}}}} + \frac{1}{2^s} \sum_{e'_0 \neq e'_1} \sum_{h^0 = h^1 \in \mathcal{F}_0^{e'_0, e'_1}} \frac{1}{2^{k+s-k_{\mathrm{aux}}}} \\
&= \mathcal{O}(1) \sum_{e'_0 \neq e'_1} \sum_{h^0 = h^1 \in \mathcal{F}_0^{e'_0, e'_1}} \frac{1}{2^{k+2s-2k_{\mathrm{aux}}}}
\end{align*}
$$

where we basically use the same reasoning than for proving Equation (31). There in this subcase,

$$
\mathrm{Cov}_3 \le \sum_{(e'_0, h^0) \in \mathcal{E}_b} \sum_{\substack{(e'_1, h^1) \in \mathcal{E}_b \\ h^1 = h^0, e'_0 \ne e'_1}} \frac{1}{2^{k+2s-2k_{\mathrm{aux}}}} \le \sum_{(e'_0, h^0) \in \mathcal{E}_b} \frac{\binom{s}{t_{\mathrm{aux}}}}{2^{k+2s-2k_{\mathrm{aux}}}} = \frac{\binom{s}{t_{\mathrm{aux}}}}{2^{s-k_{\mathrm{aux}}}} \frac{E'_b}{2^{k+s-k_{\mathrm{aux}}}}
$$

**Subcase iv:** We have,

$$
\mathrm{Cov}_4 = 0.
$$

**Subcase v:** We have,

$$
\begin{align*}
\mathrm{Cov}_5 &\le \sum_{(e'_0, h^0) \in \mathcal{E}_b} \sum_{\substack{(e'_1, h^1) \in \mathcal{E}_b \\ h^1 \ne h^0, h^0 \ne h^1, e'_0 \ne e'_1}} \frac{1}{2^{2k+s-k_{\mathrm{aux}}}} \\
&\le \sum_{(e_0, h^0) \in \mathcal{E}_b} \frac{\binom{s}{t_{\mathrm{aux}}}}{2^{2k+s-k_{\mathrm{aux}}}} \frac{\binom{n-s}{w}}{2^{2k+s-k_{\mathrm{aux}}}} \\
&= \frac{\binom{n-s}{w}}{2^k} \frac{\binom{s}{t_{\mathrm{aux}}}}{2^{k+s-k_{\mathrm{aux}}}} E'_b
\end{align*}
$$

**Subcase vi:** We have,

$$
\mathrm{Cov}_6 = 0.
$$

Plugging all these bounds on the $Cov_i$ together and using that $\mathrm{Cov} = \sum_i \mathrm{Cov}_i$ leads to

$$
\begin{align*}
\mathrm{Cov} &\le \left( \frac{\binom{n-s}{w}}{2^k} + \frac{\binom{s}{t_{\mathrm{aux}}}}{2^{s-k_{\mathrm{aux}}}} + \frac{\binom{n-s}{w}}{2^k} \frac{\binom{s}{t_{\mathrm{aux}}}}{2^{k+s-k_{\mathrm{aux}}}} \right) \frac{E'_b}{2^{k+s-k_{\mathrm{aux}}}} \\
&= \mathcal{O}(n^\alpha) \frac{E'_b}{2^{k+s-k_{\mathrm{aux}}}}
\end{align*}
$$

where in the last lines we used the constraints (22) given in the proposition. Plugging this equation
in Equation (32) concludes the proof. $\square$

We are now ready to prove our proposition:

*Proof of Proposition 2.* Let $E_b$ and $E_b'$ (for $b \in \{0,1\}$) be defined as in Lemma 2. By using the Bienaymé-Tchebychev inequality, we obtain for any function $f$ mapping the positive integers to positive real numbers:

$$
\mathbb{P}_{\mathbf{H},\mathbf{H}_{\text{aux}}} \left( |E_b - \mathbb{E}(E_b)| \ge \sqrt{f(n)\mathbb{E}(E_b)} \right) \le \frac{\text{Var}(E_b)}{f(n)\mathbb{E}(E_b)} = \frac{\mathcal{O}(n^\alpha)}{f(n)}
$$

where the last inequality is a consequence of Lemma 2. Since,

$$
\text{bias}_{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \stackrel{\$}{\leftrightarrow} \mathcal{H}} ((\mathbf{c}_{\text{aux}} + \mathbf{h}_{\mathcal{P}}, \mathbf{e}_{\mathcal{P}}) + (\mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}})) = \frac{E_0 - E_1}{E_0 + E_1},
$$
we have with probability greater than $1 - \frac{\mathcal{O}(n^\alpha)}{f(n)}$ that

$$ \frac{\mu_0 - \mu_1 - \sqrt{2f(n)}\sqrt{\mu_0 + \mu_1}}{\mu_0 + \mu_1 + \sqrt{2f(n)}\sqrt{\mu_0 + \mu_1}} \le \underset{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \stackrel{\$}{\leftarrow} \mathcal{H}}{\text{bias}} \left( \langle \mathbf{c}_{\text{aux}} + \mathbf{h}_{\mathcal{P}}, \mathbf{e}_{\mathcal{P}} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle \right) \\ \le \frac{\mu_0 - \mu_1 + \sqrt{2f(n)}\sqrt{\mu_0 + \mu_1}}{\mu_0 + \mu_1 - \sqrt{2f(n)}\sqrt{\mu_0 + \mu_1}} \quad (44) $$

where

$$ \mu_i \stackrel{\text{def}}{=} \mathbb{E}(E_i) $$

and where we used that for all positive $x$ and $y$, $\sqrt{x} + \sqrt{y} \le \sqrt{2(x + y)}$. Let,

$$ N = \mu_0 + \mu_1 $$

It is readily seen that,

$$ N = \frac{\binom{n-s}{w} \binom{s}{t_{\text{aux}}}}{2^{k-k_{\text{aux}}}} $$

We let $f(n) = \delta\sqrt{N}/2$. Since $N = \mu_0 + \mu_1$ this implies $f(n) = \delta\sqrt{\mu_0 + \mu_1}/2$. By Equation (7), note that $f(n)/\mathcal{O}(n^\alpha)$ tends to infinity as $n$ tends to infinity. We notice that

$$ \begin{aligned} \sqrt{2f(n)}\sqrt{\mu_0 + \mu_1} &= \delta^{1/2}(\mu_0 + \mu_1)^{3/4} \\ &= o(\delta(\mu_0 + \mu_1)) \end{aligned} $$

because

$$ \frac{\delta^{1/2}(\mu_0 + \mu_1)^{3/4}}{\delta(\mu_0 + \mu_1)} = \frac{1}{\sqrt{\delta\sqrt{\mu_0 + \mu_1}}} = \frac{1}{\sqrt{2f(n)}} \underset{n \to +\infty}{\longrightarrow} 0. $$

Equation (44) can now be rewritten as

$$ \frac{\mu_0 - \mu_1 - o(\delta(\mu_0 + \mu_1))}{\mu_0 + \mu_1 + o(\delta(\mu_0 + \mu_1))} \le \text{bias} \left( \langle \mathbf{e}''_{\mathcal{P}}, \mathbf{e}_{\mathcal{P}} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle \right) \\ \le \frac{\mu_0 - \mu_1 + o(\delta(\mu_0 + \mu_1))}{\mu_0 + \mu_1 - o(\delta(\mu_0 + \mu_1))} \quad (45) $$

Now on the other hand

$$ \begin{aligned} \delta &= \underset{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \stackrel{\$}{\leftarrow} \mathcal{H}}{\text{bias}} \left( \langle \mathbf{c}_{\text{aux}} + \mathbf{h}_{\mathcal{P}}, \mathbf{e}_{\mathcal{P}} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle \right) \\ &= \frac{E'_0 - E'_1}{E'_0 + E'_1} \\ &= \frac{\frac{E'_0}{2^{k+s-k_{\text{aux}}}} - \frac{E'_1}{2^{k+s-k_{\text{aux}}}}}{\frac{E'_0}{2^{k+s-k_{\text{aux}}}} + \frac{E'_1}{2^{k+s-k_{\text{aux}}}}} \\ &= \frac{\mu_0 - \mu_1}{\mu_0 + \mu_1} \end{aligned} $$

where the last equality is a consequence of Lemma 2, in particular Equation (23). From this it follows that we can rewrite (45) as

$$ \frac{\delta}{1 + o(\delta)} - o(\delta) \le \underset{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \stackrel{\$}{\leftarrow} \mathcal{H}}{\text{bias}} \left( \langle \mathbf{c}_{\text{aux}} + \mathbf{h}_{\mathcal{P}}, \mathbf{e}_{\mathcal{P}} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle \right) \\ \le \frac{\delta}{1 - o(\delta)} + o(\delta) $$

from which it follows immediately that

$$ \underset{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \stackrel{\$}{\leftarrow} \mathcal{H}}{\text{bias}} \left( \langle \mathbf{c}_{\text{aux}} + \mathbf{h}_{\mathcal{P}}, \mathbf{e}_{\mathcal{P}} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle \right) = \delta(1 + o(1)) $$

which concludes the proof. □
APPENDIX B. CORRECTNESS AND RUNNING-TIME OF THE double-RLPN ALGORITHM
(ALGORITHM 4)

In this section we prove the correctness of Algorithm 4 in Subsection B.1. Furthermore, we give its running-time in Subsection B.2. To this aim, we instantiate Instructions 1 (PARITYCHECKEQUATIONS) 1 (DECODE) of Algorithm 1.

**Notation 3.** • *Instantiation of Algorithm 4.*

- We instantiate PARITYCHECKEQUATIONS instruction with the technique devised in [CDMT22, §5] to compute all the parity-checks of a given weight in a code (which is inspired from [BJMM12]). Its asymptotic complexity is recalled in Proposition 11.

- The family of auxiliary $[s, k_{aux}]$ linear codes $C_{aux}$ used will be product of $\log s$ random codes as devised in Section 7. Using these the DECODE procedure outputs almost all codeword at distance $t_{aux}$ in time $2^{o(s)} \max\left(\frac{\binom{s}{t_{aux}}}{2^{s-k_{aux}}}, 1\right)$.

• Framework for the analysis of Algorithm 4

- We prove the correctness (Proposition 8) and we make the complexity analysis (Proposition 9) in the framework of Proposition 5. More specifically, analysis is made for $C$ and $C_{aux}$ being random $[n, k]$ and $[s, k]_{aux}$ codes. We argue in Section 7 that the proof would be roughly the same (but more complicated) if we were to make it using $C_{aux}$ being random product codes. The complexity of Algorithm 4 would only grow by a factor of $2^{o(s)}$ when using these codes.

- Note that with the PARITYCHECKEQUATIONS and DECODE procedures we have chosen, Algorithm 4 computes in fact all the possible LPN samples, namely we have (as required in Proposition 5):

$$ \mathcal{H} = \tilde{\mathcal{H}} $$

- We reuse notation introduced in Proposition 5: the set $\mathcal{S}^{(j)}$ of candidates for the j'th auxiliary code $C_{aux}^{(j)}$ is defined by

$$ \mathcal{S}^{(j)} \stackrel{\text{def}}{=} \{\mathbf{s} \in \mathbb{F}_2^{k_{aux}} : f_{\mathbf{y}, \mathcal{H}, \mathbf{G}_{aux}^{(j)}}(\mathbf{s}) \geq \frac{\delta}{2} \tilde{H}\}, \quad (46) $$

where

$$ \tilde{H} \stackrel{\text{def}}{=} \frac{\binom{n-s}{w} \binom{s}{t_{aux}}}{2^{k-k_{aux}}}, \quad \delta \stackrel{\text{def}}{=} \frac{K_w^{(n-s)}(u) K_{t_{aux}}^{(s)}(t-u)}{\binom{n-s}{w} \binom{s}{t_{aux}}}. \quad (47) $$

B.1. Correctness of the algorithm. The goal of this section is to prove that double-RLPN, namely Algorithm 4, outputs the desired error vector e after essentially $N_{iter} \approx \frac{\binom{n}{t}}{\binom{s}{t-u}\binom{n-s}{u}}$ iterations of the outer loop (Line (2) of Algorithm 4). This is given by the following proposition.

**Proposition 8.** Let $C$ be a code taken uniformly at random among the $[n, k]$ linear codes and $C_{aux}^{(1)}, \dots, C_{aux}^{(N_{aux})}$ which are $N_{aux}$ codes taken uniformly at random among the $[s, k_{aux}]$ linear codes. Let $\mathbf{y} \stackrel{\text{def}}{=} \mathbf{c} + \mathbf{e}$ where $\mathbf{c} \in C$ and where $\mathbf{e} \in S_t^n$ is a fixed error vector of weight $t$. As long as the parameters $s, k_{aux}, t_{aux}, w, u$ verify the Parameters constraint (1) and as long as $N_{iter} = \omega\left(\frac{\binom{n}{t}}{\binom{s}{t-u}\binom{n-s}{u}}\right)$ and $N_{aux} = \mathcal{O}(1)$, Algorithm 4 outputs the error vector $\mathbf{e}$ with probability $1-o(1)$.

It is readily seen that when $N_{iter} = \omega\left(\frac{\binom{n}{t}}{\binom{s}{t-u}\binom{n-s}{u}}\right)$ then, with probability $1-o(1)$ over the choice of $\mathcal{P}$ there exists an iteration such that $|e_{\mathcal{N}}| = u$. We only have left to show that for such an iteration we have with high probability that $e_{\mathcal{P}}(\mathbf{G}_{aux}^{(j)})^\top \in \mathcal{S}^{(j)}$ for $j = 1, \dots, N_{aux}$ which is the purpose of the following lemma.

**Lemma 3.** Let us reuse the setting of Proposition 8. Moreover, let us fix $\mathcal{P}$ and $\mathcal{N}$ two complementary sets of $[1, n]$ of size $s$ and $n-s$ respectively and such that $|e_{\mathcal{N}}| = u$. Let us
denote by $G_{\text{aux}}^{(1)}, \dots, G_{\text{aux}}^{(N_{\text{aux}})}$ the generators matrices of the codes $C_{\text{aux}}^{(1)}, \dots, C_{\text{aux}}^{(N_{\text{aux}})}$ respectively.
Then,

$$ \mathbb{P}\left(\bigcap_{j=1}^{N_{\text{aux}}} \text{``} \mathbf{e}_{\mathscr{P}} \mathbf{G}_{\text{aux}}^{(j)} \mathbf{\tau} \in \mathscr{S}^{(j)} \text{''}\right) = 1 - o(1). \quad (48) $$

*Proof.* First, notice that

$$ \begin{aligned} \mathbb{P}\left(\bigcap_{j=1}^{N_{\text{aux}}} \text{``} \mathbf{e}_{\mathscr{P}} \mathbf{G}_{\text{aux}}^{(j)} \mathbf{\tau} \in \mathscr{S}^{(j)} \text{''}\right) &= 1 - \mathbb{P}\left(\bigcup_{j=1}^{N_{\text{aux}}} \text{``} \mathbf{e}_{\mathscr{P}} \mathbf{G}_{\text{aux}}^{(j)} \mathbf{\tau} \notin \mathscr{S}^{(j)} \text{''}\right) \\ &\ge 1 - \sum_{j=1}^{N_{\text{aux}}} \mathbb{P}\left(\text{``} \mathbf{e}_{\mathscr{P}} \mathbf{G}_{\text{aux}}^{(j)} \mathbf{\tau} \notin \mathscr{S}^{(j)} \text{''}\right) \end{aligned} $$

where we used the union-bound. Now, as $N_{\text{aux}} = \mathcal{O}(1)$ we only have to show that $\mathbb{P}(\text{``} \mathbf{e}_{\mathscr{P}} \mathbf{G}_{\text{aux}}^{(j)} \mathbf{\tau} \notin \mathscr{S}^{(j)} \text{''}) = o(1)$ to prove Equation (48). By using Fact 4,

$$ \text{``} \mathbf{e}_{\mathscr{P}} \mathbf{G}_{\text{aux}}^{(j)} \mathbf{\tau} \notin \mathscr{S}^{(j)} \text{''} \iff \operatorname{bias}_{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \stackrel{\$}{\leftarrow} \tilde{\mathcal{H}}} (\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{e}_{\mathscr{P}}, \mathbf{c}_{\text{aux}} \rangle) < \frac{\delta}{2} \frac{\tilde{H}}{|\tilde{\mathcal{H}}|} $$

Our aim is to show,

$$ \mathbb{P}\left(\operatorname{bias}_{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \stackrel{\$}{\leftarrow} \tilde{\mathcal{H}}} (\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{e}_{\mathscr{P}}, \mathbf{c}_{\text{aux}} \rangle) < \frac{\delta}{2} \frac{\tilde{H}}{|\tilde{\mathcal{H}}|}\right) = o(1). $$

To simplify notation let $b \stackrel{\text{def}}{=} \operatorname{bias}_{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \stackrel{\$}{\leftarrow} \tilde{\mathcal{H}}} (\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{e}_{\mathscr{P}}, \mathbf{c}_{\text{aux}} \rangle)$. It is readily seen that $\mathbb{E}_{\mathcal{C}, \mathcal{C}_{\text{aux}}} (|\tilde{\mathcal{H}}|) = \tilde{H}(1 + o(1))$ and $\mathbf{Var}_{\mathcal{C}, \mathcal{C}_{\text{aux}}} (|\tilde{\mathcal{H}}|) \le \tilde{H}(1 + o(1))$. Therefore, by using Bienaymé-Tchebychev inequality, for any $a$,

$$ \mathbb{P}\left(\left|\tilde{\mathcal{H}}\right| - (1 + o(1))\tilde{H} \ge \sqrt{a\tilde{H}}\right) \le \frac{1 + o(1)}{a} $$

We have the following computation,

$$ \begin{aligned} \mathbb{P}\left(b < \frac{\delta}{2} \frac{\tilde{H}}{|\tilde{\mathcal{H}}|}\right) &= \mathbb{P}\left(b < \frac{\delta}{2} \frac{\tilde{H}}{|\tilde{\mathcal{H}}|} \mid \left|\tilde{\mathcal{H}}\right| - (1 + o(1))\tilde{H} \ge \sqrt{a\tilde{H}}\right) \mathbb{P}\left(\left|\tilde{\mathcal{H}}\right| - (1 + o(1))\tilde{H} \ge \sqrt{a\tilde{H}}\right) \\ &\quad + \mathbb{P}\left(b < \frac{\delta}{2} \frac{\tilde{H}}{|\tilde{\mathcal{H}}|} \mid \left|\tilde{\mathcal{H}}\right| - (1 + o(1))\tilde{H} < \sqrt{a\tilde{H}}\right) \mathbb{P}\left(\left|\tilde{\mathcal{H}}\right| - (1 + o(1))\tilde{H} < \sqrt{a\tilde{H}}\right) \end{aligned} $$

Therefore,

$$ \begin{aligned} \mathbb{P}\left(b < \frac{\delta}{2} \frac{\tilde{H}}{|\tilde{\mathcal{H}}|}\right) &\le \mathbb{P}\left(\left|\tilde{\mathcal{H}}\right| - (1 + o(1))\tilde{H} \ge \sqrt{a\tilde{H}}\right) + \mathbb{P}\left(b < \frac{\delta}{2} \frac{\tilde{H}}{(1 + o(1))\tilde{H} - \sqrt{a\tilde{H}}}\right) \\ &\le \frac{1 + o(1)}{a} + \mathbb{P}\left(b < \frac{\delta}{2} \frac{1}{(1 + o(1)) - \sqrt{\frac{a}{H}}}\right) \end{aligned} $$

Let us choose $a = \tilde{H}^{1/2}$. Recall that $\tilde{H} = \omega(\frac{n^{\alpha+8}}{\delta^2})$ where $\delta \le 1$. Therefore,

$$ \begin{aligned} \mathbb{P}\left(b < \frac{\delta}{2} \frac{\tilde{H}}{|\tilde{\mathcal{H}}|}\right) &= o(1) + \mathbb{P}\left(b < \frac{\delta}{2}(1 + o(1))\right) \\ &= o(1) \end{aligned} $$
where in the last equality we used Proposition 7. It concludes the proof. □

B.2. **Asymptotic complexity of double-RLPN.** We now have every tool to give the complexity of our algorithm, namely, we can compute the expected number of candidates at each iteration given by Proposition 5 and we have the correctness of our algorithm which is given by Proposition 8.

**Proposition 9.** Asymptotic complexity exponent of the double-RLPN algorithm. Define

$$ 
\begin{aligned}
R &\stackrel{\text{def}}{=} \lim_{n \to \infty} \frac{k}{n}, & \tau &\stackrel{\text{def}}{=} \lim_{n \to \infty} \frac{t}{n}, & \sigma &\stackrel{\text{def}}{=} \lim_{n \to \infty} \frac{s}{n}, & R_{\text{aux}} &\stackrel{\text{def}}{=} \lim_{n \to \infty} \frac{k_{\text{aux}}}{n} \\
\tau_{\text{aux}} &\stackrel{\text{def}}{=} \lim_{n \to \infty} \frac{t_{\text{aux}}}{n}, & \omega &\stackrel{\text{def}}{=} \lim_{n \to \infty} \frac{w}{n}, & \mu &\stackrel{\text{def}}{=} \lim_{n \to \infty} \frac{u}{n}
\end{aligned}
$$

Suppose that the DECODE procedure has an expected time complexity of $2^{n \cdot \sigma \cdot o(1)}$. The expected complexity of the double-RLPN algorithm to decode a code of rate $R$ at relative distance $\tau$ is upper bounded by $2^n (\alpha_{\text{double-RLPN}} + o(1))$ where

$$ \alpha_{\text{double-RLPN}} \le -\pi + \max \left( (1-\sigma) \cdot \alpha_{\text{eq}} \left( \frac{R-\sigma}{1-\sigma}, \frac{\omega}{1-\sigma} \right), \nu_{\text{sample}}, R_{\text{aux}}, \nu_{\text{candidate}} \cdot N_{\text{aux}} + \alpha_{\text{ISD}} \right) $$

where

$$ \pi \stackrel{\text{def}}{=} h(\tau) - \sigma \cdot h_2 \left( \frac{\tau - \mu}{\sigma} \right) - (1 - \sigma) \cdot h \left( \frac{\mu}{1 - \sigma} \right), $$

$$ \nu_{\text{samples}} \stackrel{\text{def}}{=} (1 - \sigma) \cdot h_2 \left( \frac{\omega}{1 - \sigma} \right) + \sigma \cdot h_2 \left( \frac{\tau_{\text{aux}}}{\sigma} \right) - (R - R_{\text{aux}}), $$

$$ \alpha_{\text{ISD}} \stackrel{\text{def}}{=} \max \left( \sigma \cdot \alpha_{\text{ISD-Dumer}} \left( 1 - \frac{N_{\text{aux}} \cdot \tau_{\text{aux}}}{\sigma}, \frac{\tau - \mu}{\sigma} \right), \nu_{\text{ISD}} + (1 - \sigma) \cdot \alpha_{\text{ISD-Dumer}} \left( \frac{R - \sigma}{1 - \sigma}, \frac{\mu}{1 - \sigma} \right) \right), $$

$$ \nu_{\text{ISD}} \stackrel{\text{def}}{=} \max \left( \sigma \cdot h_2 \left( \frac{\tau - \mu}{\sigma} \right) - N_{\text{aux}} \cdot \tau_{\text{aux}}, 0 \right) $$

$$ \nu_{\text{candidates}} \stackrel{\text{def}}{=} \max \left( \max_{(\eta, \zeta) \in \mathcal{A}} \sigma \cdot h_2 \left( \frac{\zeta}{\sigma} \right) + (1-\sigma) \cdot h_2 \left( \frac{\eta}{1-\sigma} \right) - (1-R), 0 \right), $$

with

$$ A^{\text{def}} = \left\{ (\eta, \zeta) \in [0, 1-\sigma] \times [0, \sigma] : \sigma \left[ \tilde{\kappa} \left( \frac{t_{\text{aux}}}{\sigma}, \frac{\tau-\mu}{\sigma} \right) - \tilde{\kappa} \left( \frac{t_{\text{aux}}}{\sigma}, \frac{\zeta}{\sigma} \right) \right] + (1-\sigma) \left[ \tilde{\kappa} \left( \frac{\omega}{1-\sigma}, \frac{\mu}{1-\sigma} \right) - \tilde{\kappa} \left( \frac{\omega}{1-\sigma}, \frac{\eta}{1-\sigma} \right) \right] \le 0 \right\}, $$

and

* $\alpha_{\text{eq}}(R', \tau')$ is the complexity exponent of PARITYCHECKEQUATIONS to compute all parity-checks of relative weight $\tau'$ of a code of rate $R'$. It is instantiated here with a technique devised in [CDMT22, §5 Eq. (5.4)] and its complexity is recalled in Proposition 11.

* $\alpha_{\text{ISD-Dumer}}(R', \tau')$ is the complexity exponent of DECODE-DUMER to return all the solutions to the decoding problem in a code of rate $R'$ at relative distance $\tau'$. Its complexity is recalled in Proposition 10.

Moreover, $\sigma$, $R_{\text{aux}}$, $\tau_{\text{aux}}$, $\omega$, $\mu$, are non-negative and such that

$$ \sigma \le R, \quad \tau - \sigma \le \mu \le \tau, \quad \omega \le 1 - \sigma, $$

$$ \nu_{\text{samples}} \ge -2 \varepsilon_{\text{bias}}, \qquad (49) $$

$$ 0 \ge (1 - \sigma) h_2 \left( \frac{\omega}{1 - \sigma} \right) + \sigma h_2 \left( \frac{\tau_{\text{aux}}}{\sigma} \right) - R \qquad (50) $$

$$ 0 \ge \sigma h_2 \left( \frac{\tau_{\text{aux}}}{\sigma} \right) - (\sigma - R_{\text{aux}}) \qquad (51) $$
where $\tilde{\kappa}$ is the function defined in Proposition 1 and

$$ \varepsilon_{\text{bias}} \stackrel{\text{def}}{=} \sigma \left[ \tilde{\kappa} \left( \frac{t_{\text{aux}}}{\sigma}, \frac{\tau - \mu}{\sigma} \right) - h_2 \left( \frac{\tau_{\text{aux}}}{\sigma} \right) \right] + (1 - \sigma) \left[ \tilde{\kappa} \left( \frac{\omega}{1 - \sigma}, \frac{\mu}{1 - \sigma} \right) - h_2 \left( \frac{\omega}{1 - \sigma} \right) \right]. $$

Finally, we require that $N_{\text{aux}} = O(1)$.

**Remark 5.** In practice our parameters are such that we decode the auxiliary code at Gilbert-Varshamov distance, namely $\tau_{\text{aux}} = \sigma h_2^{-1} (1 - R_{\text{aux}})$.

While initially Dumer's decoder [Dum91] is designed to produce only one solution to the decoding problem it suffices to re-run it as many time as the number of solutions we expect from the decoding problem to find all of them. We get the following proposition giving the asymptotic complexity of the DECODE-DUMER procedure.

**Proposition 10** (Asymptotic time complexity of ISD Decoder [Dum91] to produce all solutions to the decoding problem). Let $R \stackrel{\text{def}}{=} \lim_{n \to \infty} \frac{k}{n}$, $\tau \stackrel{\text{def}}{=} \lim_{n \to \infty} \frac{\ell}{n}$. Let $\ell$ and $w$ be two (implicit) parameters of the algorithm and define $\lambda \stackrel{\text{def}}{=} \lim_{n \to \infty} \frac{\ell}{n}$, $\omega \stackrel{\text{def}}{=} \lim_{n \to \infty} \frac{w}{n}$. The time and space complexities of [Dum91] to find a proportion $1-o(1)$ of all solutions to the decoding problem at distance $t$ on an $[n, k]$ linear code are given by $2^n (\alpha_{\text{ISD-Dumer}}+o(1))$ and $2^n (\beta_{\text{ISD-Dumer}}+o(1))$ respectively where

$$ \alpha_{\text{ISD-Dumer}} \stackrel{\text{def}}{=} \min_{\omega, \lambda} \left( \pi + \max \left( \frac{R+\lambda}{2} h_2 \left( \frac{\omega}{R+\lambda} \right), (R+\lambda) h_2 \left( \frac{\omega}{R+\lambda} \right) - \lambda \right) \right), \quad (52) $$

$$ \pi \stackrel{\text{def}}{=} h_2(\tau) - (1 - R - \lambda)h_2 \left( \frac{\tau - \omega}{1 - R - \lambda} \right) - (R + \lambda)h_2 \left( \frac{\omega}{R + \lambda} \right), \quad (53) $$

$$ \nu_{\text{sol}} \stackrel{\text{def}}{=} \max(h_2(\tau) - (1 - R), 0), \quad (54) $$

$$ \beta_{\text{ISD-Dumer}} \stackrel{\text{def}}{=} \frac{R + \lambda}{2} h_2 \left( \frac{\omega}{R + \lambda} \right). \quad (55) $$

Moreover $\lambda$ and $\omega$ must verify the following constraints:

$$ 0 \le \lambda \le 1 - R, \quad \max(R + \lambda + \tau - 1, 0) \le \omega \le \min(\tau, R + \lambda). $$

The expected number of solutions is given by $2^n (\nu_{\text{sol}}+o(1))$.

We recall here the asymptotic complexity of the technique devised in [CDMT22, §5, Equation (5.4)] based on [BJMM12] decoder to produce all parity-checks of low weight of a code.

**Proposition 11.** Asymptotic time complexity exponent of BJMM technique [BJMM12], [CDMT22, §5, Equation (5.4)] to produce all parity-checks of relative weight $\omega$ of a code of rate $R$

$$ \alpha_{\text{BJMM}}(R, \omega) \stackrel{\text{def}}{=} \min_{\pi_1, \pi_2, \lambda_1, \lambda_2} \gamma \quad (56) $$

where

$$ \gamma \stackrel{\text{def}}{=} \max(\gamma_1, \gamma_2, \gamma_3) $$

$$ \gamma_1 \stackrel{\text{def}}{=} \max(\nu_0, 2\nu_0 - \lambda_1), \quad \gamma_2 \stackrel{\text{def}}{=} \max(\nu_1, 2\nu_1 - (\lambda_2 - \lambda_1)), \quad \gamma_3 \stackrel{\text{def}}{=} \max(\nu_2, 2\nu_2 - (\lambda - \lambda_2)) $$

$$ \nu_0 \stackrel{\text{def}}{=} \frac{h(\pi_1)}{2}, \quad \nu_1 \stackrel{\text{def}}{=} h(\pi_1) - \lambda_1, \quad \nu_2 \stackrel{\text{def}}{=} h(\pi_2) - \lambda_2, \quad \nu_3 \stackrel{\text{def}}{=} h(\omega) - \lambda. $$

and the constraint region $\mathcal{R}$ is defined by the sub-region of nonnegative tuples $(\pi_1, \pi_2, \lambda_1, \lambda_2)$ such that

$$ \lambda_1 \le \lambda_2 \le \lambda, \quad \pi_1 \le \pi_2 \le \pi, \quad \pi_2 \le 2\pi_1, \quad \pi \le 2\pi_2, \quad \pi_2 \le \lambda_1, \quad \pi \le \lambda_2, $$

and

$$ \lambda_1 = \pi_2 + (1 - \pi_2)h \left( \frac{\pi_1 - \pi_2/2}{1 - \pi_2} \right), \quad (57) $$

$$ \lambda_2 = \omega + (1 - \omega)h \left( \frac{\pi_2 - \omega/2}{1 - \omega} \right) \quad (58) $$
The expected number of parity-checks computed is given by $2^n (\nu_3+o(1))$

APPENDIX C. PROOF OF PROPOSITION 4

Let us recall Proposition 4.

**Proposition 4.** Let $\mathcal{P}$ and $\mathcal{N}$ be two complementary subsets of $\llbracket 1, n \rrbracket$ of size $s$ and $n-s$ respectively. Let $\mathcal{C}$ be an $[n, k]$-code such that $\mathcal{C}_{\mathcal{P}}$ is of dimension $s$ and let $\mathcal{C}_{\text{aux}}$ be an $[s, k_{\text{aux}}]$-code. We have for any $\mathbf{x} \in \mathbb{F}_2^s$

$$ \text{bias}_{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \stackrel{\text{def}}{\leftarrow} \tilde{\mathcal{H}}} ((\mathbf{y}, \mathbf{h}) + \langle \mathbf{x}, \mathbf{c}_{\text{aux}} \rangle) = \frac{1}{2^{k-k_{\text{aux}}}} \frac{1}{|\tilde{\mathcal{H}}|} \sum_{i=0}^{n-s} \sum_{j=0}^{s} N_{i,j} K_{w}^{(n-s)}(i) K_{t_{\text{aux}}}^{(s)}(j) \quad (10) $$

where

$$ N_{i,j} \stackrel{\text{def}}{=} |\{(\mathbf{r}, \mathbf{c}^{\mathcal{N}}) \in (\mathbf{x} + \mathcal{C}_{\text{aux}}^{\perp}) \times \mathcal{C}^{\mathcal{N}} : |\mathbf{r}| = j \text{ and } |(\mathbf{r} + \mathbf{e}_{\mathcal{P}})\mathbf{R} + \mathbf{e}_{\mathcal{N}} + \mathbf{c}^{\mathcal{N}}| = i\}|, \\ \tilde{\mathcal{H}} = \{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \in \mathcal{C}^{\perp} \times \mathcal{C}_{\text{aux}} : |\mathbf{h}_{\mathcal{N}}| = w \text{ and } |\mathbf{h}_{\mathcal{P}} + \mathbf{c}_{\text{aux}}| = t_{\text{aux}}\} $$

and where $\mathbf{R} \in \mathbb{F}_2^{s \times (n-s)}$ is such that for any $\mathbf{h} \in \mathcal{C}^{\perp}$ we have $\mathbf{h}_{\mathcal{P}} = \mathbf{h}_{\mathcal{N}}\mathbf{R}^{\top}$.

Let us devise a more convenient expression for $\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{c}_{\text{aux}} \rangle$. By noticing that $\mathbf{h}_{\mathcal{P}}$ and $\mathbf{h}_{\mathcal{N}}$ are linearly linked we get the following lemma.

**Lemma 4.** Let $\mathcal{P}$ and $\mathcal{N}$ be two complementary subsets of $\llbracket 1, n \rrbracket$ of size $s$ and $n-s$ respectively. Let $\mathcal{C}$ and $\mathcal{C}_{\text{aux}}$ be two $[n, k]$ linear and $[s, k_{\text{aux}}]$ linear codes respectively such that $\mathcal{C}_{\mathcal{P}}$ is of dimension $s$. Let $\mathbf{x} \in \mathbb{F}_2^s$ and $(\mathbf{h}, \mathbf{c}_{\text{aux}}) \in \tilde{\mathcal{H}}$ where recall that

$$ \tilde{\mathcal{H}} \stackrel{\text{def}}{=} \{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \in \mathcal{C}^{\perp} \times \mathcal{C}_{\text{aux}} : |\mathbf{h}_{\mathcal{N}}| = w \text{ and } |\mathbf{h}_{\mathcal{P}} + \mathbf{c}_{\text{aux}}^{\perp}| = t_{\text{aux}}\}. $$

We have that

$$ \langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{c}_{\text{aux}} \rangle = \langle (\mathbf{x} + \mathbf{e}_{\mathcal{P}}) \mathbf{R} + \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle + \langle \mathbf{x}, \mathbf{h}_{\mathcal{P}} + \mathbf{c}_{\text{aux}} \rangle \quad (59) $$

where $\mathbf{R} \in \mathbb{F}_2^{s \times (n-s)}$ is (independently of the parity-check $\mathbf{h}$) such that

$$ \mathbf{h}_{\mathcal{P}} = \mathbf{h}_{\mathcal{N}}\mathbf{R}^{\top}. \quad (60) $$

*Proof.* First, let us show Equation (60). Suppose without loss of generality that $\mathcal{P} = \llbracket 1, s \rrbracket$ and $\mathcal{N} = \llbracket s+1, n \rrbracket$. Let $\mathbf{G} \in \mathbb{F}_2^{k \times n}$ be a generator matrix of $\mathcal{C}$. Because $\mathcal{C}_{\mathcal{P}}$ is of dimension $s$ there exists an invertible $\mathbf{J} \in \mathbb{F}_2^{k \times k}$ such that

$$ \mathbf{JG} = \begin{pmatrix} \mathbf{I}_{d_s} & \mathbf{R} \\ \mathbf{0}_{k-s} & \mathbf{R}' \end{pmatrix} $$

where $\mathbf{R} \in \mathbb{F}_2^{s \times (n-s)}$ and $\mathbf{R}' \in \mathbb{F}_2^{(k-s) \times (n-s)}$. Furthermore, $\mathbf{JG}$ is another generator matrix for $\mathcal{C}$. Therefore for any $\mathbf{h} \in \mathcal{C}^{\perp}$ we have $\mathbf{JG} \mathbf{h}^{\top} = \mathbf{0}$. Since $\mathbf{JG} \mathbf{h}^{\top} = \mathbf{h}_{\mathcal{P}}^{\top} + \mathbf{R} \mathbf{h}_{\mathcal{N}}^{\top}$, this gives (60). Now, let us prove (59). Recall that, using Equation (60) we have:

$$ \begin{aligned} \langle \mathbf{y}, \mathbf{h} \rangle &= \langle \mathbf{e}_{\mathcal{P}}, \mathbf{h}_{\mathcal{P}} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle \\ &= \langle \mathbf{e}_{\mathcal{P}}, \mathbf{h}_{\mathcal{N}} \mathbf{R}^{\top} \rangle + \langle \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle \\ &= \langle \mathbf{e}_{\mathcal{P}} \mathbf{R} + \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle, \end{aligned} $$

and

$$ \begin{aligned} \langle \mathbf{x}, \mathbf{c}_{\text{aux}} \rangle &= \langle \mathbf{x}, \mathbf{h}_{\mathcal{P}} \rangle + \langle \mathbf{x}, \mathbf{h}_{\mathcal{P}} + \mathbf{c}_{\text{aux}} \rangle \\ &= \langle \mathbf{x} \mathbf{R}, \mathbf{h}_{\mathcal{N}} \rangle + \langle \mathbf{x}, \mathbf{h}_{\mathcal{P}} + \mathbf{c}_{\text{aux}} \rangle \end{aligned} $$

where in the last equality we used Equation (60). This concludes the proof. $\square$
Proof of Proposition 4. Let us consider $\mathbf{R} \in \mathbb{F}_2^{s \times (n-s)}$ as in Lemma 4 and let us prove Equation (10). By definition of the bias and $\tilde{\mathcal{H}}$ given Equation (60) we have the following computation and

$$
\begin{align*}
\text{bias}_{(\mathbf{h}, \mathbf{c}_{\text{aux}})}(\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{c}_{\text{aux}} \rangle) &= \frac{1}{|\tilde{\mathcal{H}}|} \sum_{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \in \tilde{\mathcal{H}}} (-1)^{\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{c}_{\text{aux}} \rangle} \\
&= \frac{1}{|\tilde{\mathcal{H}}|} \sum_{\substack{(\mathbf{h}_{\mathcal{N}}, \mathbf{c}_{\text{aux}}) \in (\mathcal{C}^{\perp})_{\mathcal{N}} \\ |\mathbf{h}_{\mathcal{N}}| = w, |\mathbf{R}\mathbf{h}_{\mathcal{N}} + \mathbf{c}_{\text{aux}}| = t_{\text{aux}}}} (-1)^{\langle (\mathbf{x} + \mathbf{e}_{\mathcal{P}})\mathbf{R} + \mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle + \langle \mathbf{x}, \mathbf{h}_{\mathcal{N}}\mathbf{R}^{\top} + \mathbf{c}_{\text{aux}} \rangle}
\end{align*}
$$

where in the last equality we used Lemma 4. Therefore,

$$
\text{bias}_{(\mathbf{h}, \mathbf{c}_{\text{aux}})}(\mathcal{H}) = \frac{1}{|\mathcal{H}|} \sum_{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \in (\mathcal{C}^{\perp})_{\mathcal{N}} \times \mathcal{C}_{\text{aux}}} f(\mathbf{h}_{\mathcal{N}}, \mathbf{c}_{\text{aux}}) \quad (61)
$$

where,

$$
f(\mathbf{h}_{\mathcal{N}}, \mathbf{c}_{\text{aux}}) \stackrel{\text{def}}{=} (-1)^{\langle (\mathbf{x}+\mathbf{e}_{\mathcal{P}})\mathbf{R}+\mathbf{e}_{\mathcal{N}}, \mathbf{h}_{\mathcal{N}} \rangle + \langle \mathbf{x}, \mathbf{h}_{\mathcal{N}}\mathbf{R}^{\top}+\mathbf{c}_{\text{aux}} \rangle} \mathbf{1}_{\{|\mathbf{h}_{\mathcal{N}}|=w, |\mathbf{h}_{\mathcal{N}}\mathbf{R}^{\top}+\mathbf{c}_{\text{aux}}|=t_{\text{aux}}|}}
$$

Using Equation 3 we have that $(\mathcal{C}^{\perp})_{\mathcal{N}} = (\mathcal{C}^{\mathcal{N}})^{\perp}$ and thus $((\mathcal{C}^{\mathcal{N}})^{\perp} \times \mathcal{C}_{\text{aux}})^{\perp} = \mathcal{C}^{\mathcal{N}} \times \mathcal{C}_{\text{aux}}^{\perp}$.
By using the Poisson formula (see [MS86, Lemma 2, Ch. 5.2]), together with the fact that
$\dim(\mathcal{C}^{\mathcal{N}} \times \mathcal{C}_{\text{aux}}^{\perp}) = k - k_{\text{aux}}$, we get

$$
\sum_{(\mathbf{h}_{\mathcal{N}}, \mathbf{c}_{\text{aux}}) \in (\mathcal{C}^{\mathcal{N}})^{\perp} \times \mathcal{C}_{\text{aux}}} f(\mathbf{h}_{\mathcal{N}}, \mathbf{c}_{\text{aux}}) = \frac{1}{2k-k_{\text{aux}}} \sum_{(\mathbf{c}^{\mathcal{N}}, \mathbf{c}_{\text{aux}}) \in \mathcal{C}^{\mathcal{N}} \times \mathcal{C}_{\text{aux}}^{\perp}} \hat{f}(\mathbf{c}^{\mathcal{N}}, \mathbf{c}_{\text{aux}}^{\perp}). \quad (62)
$$

Let us compute the right-hand term. By definition of $f$, it is readily seen that

$$
\begin{align*}
\hat{f}(\mathbf{y}_1, \mathbf{y}_2) &= \sum_{\substack{\mathbf{z}_1 \in \mathbb{F}_2^{n-1}, \mathbf{z}_2 \in \mathbb{F}_2^s \\ |\mathbf{z}_1| = w, |\mathbf{z}_1 \mathbf{R}^\top + \mathbf{z}_2| = t_{\text{aux}}}} (-1)^{\langle \mathbf{y}_1, \mathbf{z}_1 \rangle + \langle \mathbf{y}_2, \mathbf{z}_2 \rangle} (-1)^{\langle (\mathbf{x} + \mathbf{e}_{\mathcal{P}})\mathbf{R} + \mathbf{e}_{\mathcal{N}}, \mathbf{z}_1 \rangle + \langle \mathbf{x}, \mathbf{z}_1 \mathbf{R}^\top + \mathbf{z}_2 \rangle} \\
&= \sum_{\mathbf{z}_1 \in \mathbb{F}_2^{n-s}: |\mathbf{z}_1| = w} (-1)^{\langle \mathbf{y}_1 + (\mathbf{x} + \mathbf{e}_{\mathcal{P}} + \mathbf{y}_2)\mathbf{R} + \mathbf{e}_{\mathcal{N}}, \mathbf{z}_1 \rangle} \sum_{\mathbf{z}_2 \in \mathbb{F}_2^s: |\mathbf{z}_1 \mathbf{R}^\top + \mathbf{z}_2| = t_{\text{aux}}} (-1)^{\langle \mathbf{y}_2 + \mathbf{x}, \mathbf{z}_1 \mathbf{R}^\top + \mathbf{z}_2 \rangle} \\
&= K_w^{(n-s)} (|\mathbf{y}_1 + (\mathbf{y}_2 + \mathbf{x} + \mathbf{e}_{\mathcal{P}})\mathbf{R} + \mathbf{e}_{\mathcal{N}}|) K_{t_{\text{aux}}}^{(s)} (|\mathbf{y}_2 + \mathbf{x}|)
\end{align*}
$$

where in the last equality we used Fact 1. Plugging this into Equation (62) and then into Equation (61) concludes the proof. $\square$

APPENDIX D. PROOF OF PROPOSITION 5

The proof of this Appendix is to prove Proposition 5 which we recall is given by

**Proposition 5.** Using Distribution 1 for $C$, $C_{\text{aux}}$, **e** and **y** and given that our parameters verify Parameter Constraint 1, that the number of computed LPN samples is the total number of available LPN samples, i.e. $\mathcal{H} = \tilde{\mathcal{H}}$ and under Conjecture 1 we have that the expected number of candidates per iteration is bounded by

$$
\mathbb{E}_{C, C_{\text{aux}}} (|\mathcal{S}|) = \tilde{\mathcal{O}} \left( \max_{(i,j) \in \mathcal{A}} \frac{\binom{s}{j} \binom{n-s}{i}}{2^{n-k}} \right) + 1 \quad (11)
$$

where

$$
\mathcal{A} \stackrel{\text{def}}{=} \left\{ (i, j) \in [0, n-s] \times [0, s], \left| \frac{K_w^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u)}{K_w^{(n-s)}(i) K_{t_{\text{aux}}}^{(s)}(j)} \right| \le n^{3.2} \right\}. \quad (12)
$$
The set $\mathcal{S}$ of candidates is defined by

$$ \mathcal{S} \stackrel{\text{def}}{=} \left\{ \mathbf{s} \in \mathbb{F}_2^{k_{\text{aux}}} : f_{\mathbf{y}, \mathcal{H}, \mathbf{G}_{\text{aux}}} (\mathbf{s}) \geq \frac{\delta}{2} \tilde{H} \right\}, \quad (13) $$

where

$$ \tilde{H} \stackrel{\text{def}}{=} \frac{\binom{n-s}{w} \binom{s}{t_{\text{aux}}}}{2^{k-k_{\text{aux}}}} \quad \text{and} \quad \delta \stackrel{\text{def}}{=} \frac{K_w^{(n-s)} (u) K_{t_{\text{aux}}}^{(s)} (t-u)}{\binom{n-s}{w} \binom{s}{t_{\text{aux}}}}. \quad (14) $$

The proof is divided in the following steps.

**Step 1:** in Lemma 5 we show that the expected size of $\mathcal{S}$ is related to the probability that the bias of $\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{h}_{\mathcal{P}} \rangle$ is superior to the threshold $\approx \frac{\delta}{2}$.

**Step 2:** We give an exponential bound on the aforementioned probability by using Poisson summation formula as it was done in the proof of Proposition 4.

**Step 1.** Recall that we have from Equation 13 that

$$ \mathcal{S} \stackrel{\text{def}}{=} \left\{ \mathbf{s} \in \mathbb{F}_2^{k_{\text{aux}}} : f_{\mathbf{y}, \mathcal{H}, \mathbf{G}_{\text{aux}}} (\mathbf{s}) \geq \frac{\delta}{2} \tilde{H} \right\}. $$

By using Lemma 1 we get the following condition for an element $\mathbf{s}$ to be a candidate:

**Fact 4.** Let $\mathbf{s} \in \mathbb{F}_2^{k_{\text{aux}}}$ and $\mathbf{x} \in \mathbb{F}_2^s$ such that $\mathbf{x}\mathbf{G}_{\text{aux}}^{\top} = \mathbf{s}$. We have,

$$ \mathbf{s} \in \mathcal{S} \iff \underset{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \stackrel{\$}{\leftarrow} \mathcal{H}}{\text{bias}} (\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{c}_{\text{aux}} \rangle) \geq \frac{\delta}{2} \frac{\tilde{H}}{|\mathcal{H}|}. $$

From there, we can derive the following lemma linking the expected size of $\mathcal{S}$ and the previous bias.

**Lemma 5.** Under Distribution 1, using notation of Proposition 5 and under the constraint of Proposition 5 that $\mathcal{H} = \tilde{\mathcal{H}}$ we have

$$ \mathbb{E}_{\mathcal{C}, \mathcal{C}_{\text{aux}}} (|\mathcal{S}|) \le 2^{k_{\text{aux}}} \mathbb{P}_{\mathcal{C}, \mathcal{C}_{\text{aux}}, \mathbf{x}} \left( \underset{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \stackrel{\$}{\leftarrow} \tilde{\mathcal{H}}}{\text{bias}} (\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{c}_{\text{aux}} \rangle) \ge \frac{\delta}{2} \frac{\tilde{H}}{|\tilde{\mathcal{H}}|} \right) + 1 $$

where $\mathbf{x}$ is taken uniformly at random in $\mathbb{F}_2^s \setminus \{\mathcal{C}_{\text{aux}}^{\perp} + \mathbf{e}_{\mathcal{P}}\}$.

**Proof.** We have the following computation,

$$ \begin{aligned} \mathbb{E}_{\mathcal{C}, \mathcal{C}_{\text{aux}}} (|\mathcal{S}|) &= \mathbb{E} \left( \sum_{\mathbf{s} \in \mathbb{F}_2^{k_{\text{aux}}}} \mathbf{1}_{\mathbf{s} \in \mathcal{S}} \right) \\ &\le 1 + \mathbb{E} \left( \sum_{\mathbf{s} \in \mathbb{F}_2^{k_{\text{aux}}} : \mathbf{s} \ne \mathbf{e}_{\mathcal{P}} \mathbf{G}_{\text{aux}}^{\top}} \mathbf{1}_{\mathbf{s} \in \mathcal{S}} \right) \\ &= 1 + \mathbb{E} \left( \sum_{\mathbf{s} \in \mathbb{F}_2^{k_{\text{aux}}} : \mathbf{s} \ne \mathbf{e}_{\mathcal{P}} \mathbf{G}_{\text{aux}}^{\top}} \frac{1}{2^{s-k_{\text{aux}}}} \sum_{\mathbf{z} \in \mathbb{F}_2^s : \mathbf{z} = \mathbf{G}_{\text{aux}}^{\top} = \mathbf{s}} \mathbf{1}_{\mathbf{z} \mathbf{G}_{\text{aux}}^{\top} \in \mathcal{S}} \right) \end{aligned} $$

where in the last equality we used that $\mathbf{G}_{\text{aux}}$, which is a generator matrix of $\mathcal{C}_{\text{aux}}$, has rank $s-k_{\text{aux}}$ according to Distribution 1. Now, from the linearity of the expectation we get,

$$ \begin{aligned} \mathbb{E}_{\mathcal{C}, \mathcal{C}_{\text{aux}}} (|\mathcal{S}|) &\le 1 + \frac{1}{2^{s-k_{\text{aux}}}} \sum_{\mathbf{z} \in \mathbb{F}_2^s : \mathbf{z} \notin \mathcal{C}_{\text{aux}}^{\perp} + \mathbf{e}_{\mathcal{P}}} \mathbb{P}_{\mathcal{C}, \mathcal{C}_{\text{aux}}} (\mathbf{z}\mathbf{G}_{\text{aux}}^{\top} \in \mathcal{S}) \\ &= 1 + 2^{k_{\text{aux}}} \mathbb{P}_{\mathcal{C}, \mathcal{C}_{\text{aux}}, \mathbf{x}} (\mathbf{x}\mathbf{G}_{\text{aux}}^{\top} \in \mathcal{S}) \end{aligned} $$
where in the last line we used that $G_{aux}$ has full rank, $|C_{aux}^{\perp} + e_{\mathcal{P}}| = 2^s$ and $\mathbf{x}$ is taken uniformly at random in $\mathbb{F}_2^s \setminus \{C_{aux}^{\perp} + e_{\mathcal{P}}\}$. Using Fact 4 concludes the proof. $\square$

Step 2. The following lemma relates the upper-bound given in Lemma 5 to the involved probability in Conjecture 1.

**Lemma 6.** *Using Distribution 1 and notation of Proposition 5 we have*

$$ \mathbb{P}_{C, C_{aux}, \mathbf{x}} \left( \text{bias}_{(\mathbf{h}, \mathbf{c}_{aux}) \stackrel{\$}{\leftarrow} \mathcal{H}} \left( \langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{c}_{aux} \rangle \right) \ge \frac{\delta}{2} \frac{\tilde{H}}{|\mathcal{H}|} \right) = \\ \mathbb{P}_{C, C_{aux}, \mathbf{x}} \left( \sum_{j=0}^{s} \sum_{i=0}^{n-s} K_{t_{aux}}^{(s)}(j) K_{w}^{(n-s)}(i) N_{i,j} \ge \frac{1}{2} K_{w}^{(n-s)}(u) K_{t_{aux}}^{(s)}(t-u) \right). $$

where $\mathbf{x}$ is taken uniformly at random in $\mathbb{F}_2^s \setminus \{C_{aux}^{\perp} + e_{\mathcal{P}}\}$.

*Proof.* Recall that we have that from notation of Proposition 5,

$$ \tilde{H} \stackrel{\text{def}}{=} \frac{\binom{n-s}{w} \binom{s}{t_{aux}}}{2^{k-k_{aux}}}, \qquad \delta \stackrel{\text{def}}{=} \frac{K_w^{(n-s)}(u) K_{t_{aux}}^{(s)}(t-u)}{\binom{n-s}{w} \binom{s}{t_{aux}}}. \qquad (63) $$

According to Proposition 4 we have the following computation,

$$ \begin{aligned} & \mathbb{P} \left( \text{bias}_{(\mathbf{h}, \mathbf{c}_{aux}) \stackrel{\$}{\leftarrow} \mathcal{H}} \left( \langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{c}_{aux} \rangle \right) \ge \frac{\delta}{2} \frac{\tilde{H}}{|\mathcal{H}|} \right) \\ &= \mathbb{P} \left( \frac{1}{2^{k-k_{aux}}} \frac{1}{|\mathcal{H}|} \sum_{j=0}^{s} \sum_{i=0}^{n-s} K_{t_{aux}}^{(s)}(j) K_{w}^{n-s}(i) N_{i,j} \ge \frac{\delta}{2} \frac{\tilde{H}}{|\mathcal{H}|} \right) \\ &= \mathbb{P} \left( \sum_{j=0}^{s} \sum_{i=0}^{n-s} K_{t_{aux}}^{(s)}(j) K_{w}^{n-s}(i) N_{i,j} \ge \frac{K_w^{(n-s)}(u) K_{t_{aux}}^{(s)}(t-u)}{2} \right) \end{aligned} $$

where in the last equality we used Equation (63). It concludes the proof. $\square$

We will now use Conjecture 1 to bound the right-hand term of Lemma 6 by the probability of the event “$N_{i,j} \ne 0$” for some low $i$ and $j$ (more precisely when $K_w^{(n-s)}(u) K_{t_{aux}}^{(s)}(t-u) \le K_w^{(n-s)}(i) K_{t_{aux}}^{(s)}(j)$).

**Lemma 7.** *Under Distribution 1 we have that for $(i, j) \in [0, n-s] \times [0, s]$,*

$$ \mathbb{P}_{C, C_{aux}, \mathbf{x}} (N_{i,j} \neq 0) = \mathcal{O} \left( \frac{\binom{s}{j} \binom{n-s}{i}}{2^{k_{aux}+n-k}} \right) $$

where $\mathbf{x}$ is taken uniformly at random in $\mathbb{F}_2^s \setminus \{C_{aux}^{\perp} + e_{\mathcal{P}}\}$.

*Proof.* This is proved in the first lemma of Appendix E. $\square$

We are now ready to prove Proposition 5.

*proof of Proposition 5.* Recall that we want to show,

$$ \mathbb{E}_{C, C_{aux}}(|\mathcal{S}|) = \tilde{\mathcal{O}} \left( \max_{(i,j) \in A} \frac{\binom{s}{j} \binom{n-s}{i}}{2^{n-k}} \right) + 1. $$

Lemma 5 gives us that

$$ \mathbb{E}_{C, C_{aux}}(|\mathcal{S}|) \le 2^{k_{aux}} \mathbb{P}_{C, C_{aux}, \mathbf{x}} \left( \text{bias}_{(\mathbf{h}, \mathbf{c}_{aux}) \stackrel{\$}{\leftarrow} \mathcal{H}} \left( \langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{c}_{aux} \rangle \right) \ge \frac{\delta}{2} \frac{\tilde{H}}{|\mathcal{H}|} \right) + 1 \quad (64) $$
Now using Lemma 6 we get that

$$
\begin{equation} \tag{65}
\begin{aligned}
& \mathbb{P} \left( \operatorname{bias}_{(\mathbf{h}, \mathbf{c}_{\text{aux}}) \leftarrow \mathcal{H}} (\langle \mathbf{y}, \mathbf{h} \rangle + \langle \mathbf{x}, \mathbf{c}_{\text{aux}} \rangle) \ge \frac{\delta}{2} \frac{\tilde{H}}{|\tilde{\mathcal{H}}|} \right) = \\
& \qquad \mathbb{P} \left( \sum_{j=0}^{s} \sum_{i=0}^{n-s} K_{t_{\text{aux}}}^{(s)}(j) K_{w}^{(n-s)}(i) N_{i,j} \ge \frac{1}{2} K_{w}^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u) \right).
\end{aligned}
\end{equation}
$$

From Conjecture 1,

$$
\mathbb{P} \left( \sum_{j=0}^{s} \sum_{i=0}^{n-s} K_{t_{\text{aux}}}^{(s)}(j) K_{w}^{(n-s)}(i) N_{i,j} \ge \frac{1}{2} K_{w}^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u) \right) = \tilde{\mathcal{O}} \left( \max_{(i,j) \in \mathcal{A}} \mathbb{P}_{C, \mathcal{C}_{\text{aux}}, \mathbf{x}} (N_{i,j} \ne 0) \right)
$$

Therefore, using Lemma 7 we get

$$
\mathbb{P} \left( \sum_{j=0}^{s} \sum_{i=0}^{n-s} K_{t_{\text{aux}}}^{(s)}(j) K_{w}^{(n-s)}(i) N_{i,j} \ge \frac{1}{2} K_{w}^{(n-s)}(u) K_{t_{\text{aux}}}^{(s)}(t-u) \right) = \tilde{\mathcal{O}} \left( \frac{\binom{s}{j} \binom{n-s}{i}}{2^{k_{\text{aux}}+n-k}} \right)
$$

Plugging this into Equation (65) and then in (64) concludes the proof. which proves our result. □

APPENDIX E. ABOUT THE DISTRIBUTION OF THE N<sub>i,j</sub>

This appendix is dedicated to studying the distribution of N<sub>i,j</sub> and in particular to prove
Lemma 7 which was used in Appendix C to prove Proposition 4. We recall that it is given by

**Lemma 7.** Under Distribution **1** we have that for (i, j) ∈ [0, n - s] × [0, s],

$$
\mathbb{P}_{C, c_{\text{aux}}, \mathbf{x}}(N_{i,j} \neq 0) = \mathcal{O}\left(\frac{\binom{s}{j} \binom{n-s}{i}}{2^{k_{\text{aux}}+n-k}}\right)
$$

where **x** is taken uniformly at random in $\mathbb{F}_2^s \setminus \{C_{\text{aux}}^{\perp} + \mathbf{e}_{\mathcal{P}}\}$.

First, using the union bound we can devise the following upper bound on our target probability:

**Fact 5.**

$$
\mathbb{P}(N_{i,j} \neq 0) \leq \mathbb{E}(N_{i,j}).
$$

To compute this expected value, we first need to give the following lemma giving the probability
that a word belongs to a random code.

**Lemma 8.** Let $\mathcal{C}$ be chosen uniformly at random among the $[n, k]$ linear codes. Let $\mathbf{c} \in \mathbb{F}_2^n \setminus \{\mathbf{0}\}$ we have

$$
\mathbb{P}_C (c \in C) = \frac{2^k - 1}{2^n - 1}, \qquad (66)
$$

$$
\mathbb{P}_C (\mathbf{0} \in \mathcal{C}) = 1. \tag{67}
$$

Proof. This lemma directly follows from [BCN89, §3, Lemma 9.3.2, (iii)]. □

We now give the preliminary lemma which breaks down the expected value of N<sub>i,j</sub> on the C<sub>aux</sub><sup>&perp;</sup>
part and on the C<sub>&infin;</sub><sup>&N</sup> part.

**Lemma 9.** Under Distribution **1** we denote by

$$
\overline{N_j^{(C_{\text{aux}}^{\perp})}} \stackrel{\text{def}}{=} \mathbb{E}_{C, \mathcal{C}_{\text{aux}}, \mathbf{x}} (N_j (C_{\text{aux}}^{\perp} + \mathbf{x}))
$$

where **x** is taken uniformly at random in $\mathbb{F}_2^s \setminus \{C_{\text{aux}}^{\perp} + \mathbf{e}_{\mathcal{P}}\}$ and $\mathbf{r} \in C_{\text{aux}}^{\perp} + \mathbf{x}$. We denote by fixing **x**,

$$
\overline{N_i^{(C_{\text{aux}}^{\perp})}} \stackrel{\text{def}}{=} \mathbb{E}_C (N_i (C_{\text{aux}}^{\perp} + (\mathbf{r} + \mathbf{e}_{\mathcal{P}})\mathbf{R} + \mathbf{e}_{\mathcal{N}})) \quad (68)
$$
We have that

$$ \overline{N_i^{(C^\mathcal{N})}} = \frac{\binom{n-s}{i}}{2^{n-k}} \left( 1 + \mathcal{O}\left(2^{-(s-k)}\right) \right) \qquad (69) $$

$$ \overline{N_j^{(C_{\text{aux}}^{\perp})}} \le \frac{\binom{s}{j}}{2^{k_{\text{aux}}}} \left( 1 + \mathcal{O}\left(2^{-(s-k_{\text{aux}})}\right) \right) \qquad (70) $$

Furthermore, the term $\mathcal{O}(2^{-(s-k_{\text{aux}})})$ in Equation (69) does not depend on $i$.

*Proof.* Under Distribution 1, $\mathcal{C}$ is taken at random among the $[n, k]$-codes that are such that $\mathcal{C}_{\mathcal{P}}$ is of full rank dimension $s$. Therefore, it is the same as if $\mathcal{C}$ was chosen by taking its generator matrix $\mathbf{G} \in \mathbb{F}_2^{k \times n}$ as follows:

$$ \mathbf{G}_{\mathcal{P}} \stackrel{\text{def}}{=} \begin{pmatrix} \mathbf{I}_s \\ \mathbf{0}_{k-s} \end{pmatrix}, \qquad \mathbf{G}_{\mathcal{N}} \stackrel{\text{def}}{=} \begin{pmatrix} \mathbf{R} \\ \mathbf{G}^{\mathcal{N}} \end{pmatrix}. $$

where $\mathbf{R}$ is chosen uniformly at random among matrices of $\mathbb{F}_2^{s \times (n-s)}$ and $\mathbf{G}^{\mathcal{N}}$ is any generator matrix of a code chosen uniformly at random among the $[n-s, k-s]$-codes. In particular, $\mathbf{G}^{\mathcal{N}}$ and $\mathbf{R}$ are independent.

Now, by definition $\mathbf{x} \in \mathbb{F}_2^s \setminus \{C_{\text{aux}}^{\perp} + \mathbf{e}_{\mathcal{P}}\}$ and $\mathbf{r} \in C_{\text{aux}}^{\perp} + \mathbf{x}$, therefore $\mathbf{r} + \mathbf{e}_{\mathcal{P}} \neq \mathbf{0}$. We deduce that, $(\mathbf{r} + \mathbf{e}_{\mathcal{P}})\mathbf{R}$ is uniformly distributed in $\mathbb{F}_2^{n-s}$ as a non-zero sum of uniformly distributed vectors. To simplify the notations let us define the uniformly distributed vector

$$ \mathbf{v} \stackrel{\text{def}}{=} (\mathbf{r} + \mathbf{e}_{\mathcal{P}}) \mathbf{R} + \mathbf{e}_{\mathcal{N}} $$

which is independent of $C^{\mathcal{N}}$ (by construction $\mathbf{G}^{\mathcal{N}}$ and $\mathbf{R}$ are independent). Now, let us show Equation (69). We have by linearity of the expected value that

$$ \begin{aligned} \overline{N_i^{(C^\mathcal{N})}} &= \sum_{\mathbf{z} \in S_i^{n-s}} \mathbb{P}_{C, \mathbf{v}} (\mathbf{z} \in C^\mathcal{N} + \mathbf{v}) \\ &= \sum_{\mathbf{z} \in S_i^{n-s}} \mathbb{P}_{C, \mathbf{v}} (\mathbf{z} \in C^\mathcal{N} + \mathbf{v} | \mathbf{v} = \mathbf{z}) \mathbb{P}_{C, \mathbf{v}} (\mathbf{v} = \mathbf{z}) + \mathbb{P}_{C, \mathbf{v}} (\mathbf{z} \in C^\mathcal{N} + \mathbf{v} | \mathbf{v} \neq \mathbf{z}) \mathbb{P}_{C, \mathbf{v}} (\mathbf{v} \neq \mathbf{z}) \\ &= \sum_{\mathbf{z} \in S_i^{n-s}} \frac{1}{2^{n-s}} + \frac{2^{k-s}-1}{2^{n-s}-1} \left(1 - \frac{1}{2^{n-s}}\right) \quad (\text{Lemma 8}) \\ &= \frac{\binom{n-s}{i}}{2^{n-k}} \left( \frac{2^{n-k}}{2^{n-s}} + 2^{n-k} \frac{2^{k-s}-1}{2^{n-s}-1} \mathcal{O}(1) \right) \\ &= \frac{\binom{n-s}{i}}{2^{n-k}} \left( \frac{1}{2^{k-s}} + \frac{2^{k-s}-2^{k}}{2^{k-s}-2^{n-k}} \mathcal{O}(1) \right) \\ &= \frac{\binom{n-s}{i}}{2^{n-k}} \left( \frac{1}{2^{k-s}} + \frac{1-2^{-k+s}}{1-2^{-n+s}} \mathcal{O}(1) \right) \\ &= \frac{\binom{n-s}{i}}{2^{n-k}} \left( 1 + \frac{1}{2^{k-s}} + \mathcal{O}(2^{-k+s}) \right) \quad (s \le k \le n) \end{aligned} $$

Let us now show Equation (70). Recall that

$$ \overline{N_j^{(C_{\text{aux}}^{\perp})}} \stackrel{\text{def}}{=} \mathbb{E}_{C_{\text{aux}}, \mathbf{x}} (N_j (C_{\text{aux}}^{\perp} + \mathbf{x})) $$