# Assessing the Impact of a Variant of MATZOV's Dual Attack on Kyber

Kevin Carrier, Charles Meyer-Hilfiger, Yixin Shen, Jean-Pierre Tillich

► To cite this version:

Kevin Carrier, Charles Meyer-Hilfiger, Yixin Shen, Jean-Pierre Tillich. Assessing the Impact of a Variant of MATZOV's Dual Attack on Kyber. CRYPTO 2025 - 45th Annual International Cryptology Conference, Aug 2025, Santa Barbara, United States. pp.1-36. hal-05406481

HAL Id: hal-05406481

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

Submitted on 9 Dec 2025

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Assessing the Impact of a Variant of MATZOV's Dual Attack on Kyber

Kevin Carrier¹, Charles Meyer-Hilfiger², Yixin Shen³, and Jean-Pierre Tillich²

¹ ETIS UMR 8051, CY Cergy-Paris Université, ENSEA, CNRS, kevin.carrier@cyu.fr

² Project COSMIQ, Inria de Paris,
charles.meyer-hilfiger@inria.fr, jean-pierre.tillich@inria.fr

³ Univ. Rennes, Inria, CNRS, IRISA, Rennes, France yixin.shen@inria.fr

**Abstract.** The dual attacks on the Learning With Errors (LWE) problem are currently a subject of controversy. In particular, the results of [MAT22], which claim to significantly lower the security level of KYBER [SAB$^+$20], a lattice-based cryptosystem currently being standardized by NIST, are not widely accepted. The analysis behind their attack depends on a series of assumptions that, in certain scenarios, have been shown to contradict established theorems or well-tested heuristics [DP23b].

In this paper, we introduce a new dual lattice attack on LWE, drawing from ideas in coding theory. Our approach revisits the dual attack proposed by [MAT22], replacing modulus switching with an efficient decoding algorithm. This decoding is achieved by generalizing polar codes over $Z_q$, and we confirm their strong distortion properties through benchmarks. This modification enables a reduction from small-LWE to plain-LWE, with a notable decrease in the secret dimension. Additionally, we replace the enumeration step in the attack by assuming the secret is zero for the portion being enumerated, iterating this assumption over various choices for the enumeration part.

We make an analysis of our attack without using the flawed independence assumptions used in [MAT22] and we fully back up our analysis with experimental evidences.

Lastly, we assess the complexity of our attack on KYBER; showing that the security levels for KYBER-512/768/1024 are 3.5/11.9/12.3 bits below the NIST requirements (143/207/272 bits) in the same nearest-neighbor cost model as in [SAB$^+$20,MAT22]. All in all the cost of our attack matches and even slightly beat in some cases the complexities originally claimed by the attack of [MAT22].

**Keywords:** Post-Quantum Cryptography · Learning With Errors · Dual Attack · Fast Fourier Transform · Polar Code

# 1 Introduction

## 1.1 Background

**The LWE Problem.** In this paper, we address the Learning With Errors (LWE) problem originally introduced by Regev in [Reg05]. It revolves around the task of finding $s \in Z_q^n$ given $(\mathbf{A}, \mathbf{b}) \in Z_q^{m \times n} \times Z_q^m$ with $\mathbf{b} = \mathbf{A}s + \mathbf{e}$ where $\mathbf{e}$ is of small Euclidean norm. This problem can be seen as the decoding problem for the code $C(\mathbf{A})$ generated by the columns of $\mathbf{A}$ (i.e. $C(\mathbf{A}) \triangleq \{\mathbf{A}\mathbf{x}, \mathbf{x} \in Z_q^n\}$) and the Euclidean distance, where we are asked to find the codeword (i.e. the element of $C$) which is close in Euclidean distance to $\mathbf{b}$. We are particularly interested in the case where $s$ is short too which is called the small LWE problem. This problem has emerged as a fundamental challenge in cryptography. Notably, it underpins the construction of various cryptographic primitives and is

<footnote>* The work of KC and JPT was funded by the French Agence Nationale de la Recherche through ANR JCJC DECODE (ANR-22-CE39-0004-01) for KC 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. The work of YS was funded by EPSRC grant EP/W02778X/2 and the France 2030 program managed by the French National Research Agency under grant agreement ANR-22-PETQ-0008 PQ-TLS.</footnote>
conjectured to withstand attacks from quantum computers [LPR10]. Our motivation for exploring this problem stems particularly from the need to gauge the security level of KYBER, a lattice-based cryptosystem that is being standardized by the NIST<fnref n="4" />.

**Dual Attacks.** The most efficient cryptanalysis techniques against LWE(-like) problems are “primal” and “dual” lattice attacks. The primal attack corresponds to lattice reduction being performed on the “primal” lattice $\Lambda_q(\mathbf{A})$ which is Construction A of the q-ary lattice obtained from $C(\mathbf{A})$, namely

$$ \begin{aligned} \Lambda_q(\mathbf{A}) &= \{\mathbf{y} \in \mathbb{Z}^m : \exists \mathbf{c} \in C(\mathbf{A}) \text{ such that } \mathbf{y} = \mathbf{c} \quad \mathrm{mod} \quad q\} \\ &= \{\mathbf{y} \in \mathbb{Z}^m : \exists \mathbf{s} \in \mathbb{Z}_q^n \text{ such that } \mathbf{y} = \mathbf{As} \quad \mathrm{mod} \quad q\}. \end{aligned} $$

Dual attacks mean that lattice reduction is performed over the dual lattice $\Lambda_q(\mathbf{A})^\vee$, which in this case, up to a q-multiplicative factor, is nothing but Construction A applied to the dual code $C(\mathbf{A})^{\perp} \triangleq \{\mathbf{x} \in \mathbb{Z}_q^m : \mathbf{A}^{\top}\mathbf{x} = \mathbf{0}\}$:

$$ \begin{aligned} \Lambda_q(\mathbf{A})^{\vee} &\triangleq \{\mathbf{x} \in \mathbb{R}^m : \langle \mathbf{x}, \mathbf{y} \rangle \in \mathbb{Z}, \forall \mathbf{y} \in \Lambda_q(\mathbf{A})\} \\ &= \frac{1}{q}\{\mathbf{x} \in \mathbb{Z}^m : \mathbf{A}^{\top}\mathbf{x} = \mathbf{0} \quad \mathrm{mod} \quad q\}. \end{aligned} $$

The lattice $\{\mathbf{x} \in \mathbb{Z}^m : \mathbf{A}^{\top}\mathbf{x} = \mathbf{0} \quad \mathrm{mod} \quad q\}$ is known under the name of the orthogonal lattice of $\mathbf{A}$, i.e. $\Lambda_q^{\perp}(\mathbf{A}) \triangleq \{\mathbf{x} \in \mathbb{Z}^m : \mathbf{A}^{\top}\mathbf{x} = \mathbf{0} \quad \mathrm{mod} \quad q\}$.

Dual attacks were introduced in [MR09]. In its simplest form, a dual attack is a distinguisher attack which is given either $(\mathbf{A}, \mathbf{A} \cdot \mathbf{s} + \mathbf{e})$ or $(\mathbf{A}, \mathbf{u})$ where $(\mathbf{A}, \mathbf{u})$ are uniform and $\mathbf{e}$ is short, and answers if we are in the first or the second case. It starts by computing many short $\mathbf{x}_j$'s in the dual lattice $\Lambda_q(\mathbf{A})^\vee$ and the associated $\langle \mathbf{x}_j, \mathbf{b} \rangle$'s. Those short vectors are obtained by lattice reduction of $\Lambda_q(\mathbf{A})^\vee$ or what is basically equivalent $\Lambda_q^{\perp}(\mathbf{A})$. In the second case, we expect that these scalar products are uniformly distributed in $\mathbb{Z}_q$. On the other hand in the first case since $\langle \mathbf{x}_j, \mathbf{b} \rangle = \langle \mathbf{x}_j, \mathbf{As} + \mathbf{e} \rangle = \langle \mathbf{A}^{\top}\mathbf{x}_j, \mathbf{s} \rangle + \langle \mathbf{x}_j, \mathbf{e} \rangle = \langle \mathbf{x}_j, \mathbf{e} \rangle \quad \mathrm{mod} \quad q$, we get scalar products of small vectors which are tilted towards small entries.

There have been a sequence of developments in dual attacks, for instance by combining these attacks with a guessing stage [Alb17] consisting in splitting the support of $\mathbf{s}$ in two parts $\begin{pmatrix} \mathbf{s}_{\mathrm{enu}} \\ \mathbf{s}_{\mathrm{lat}} \end{pmatrix}$ and guessing one part of this support. $\mathbf{A}$ is split accordingly $\mathbf{A} = [\mathbf{A}_{\mathrm{enu}} \ \mathbf{A}_{\mathrm{lat}}]$. This allows to only perform lattice reduction on Construction A of the code generated by $\begin{bmatrix} \mathbf{Id}_m \\ \mathbf{A}_{\mathrm{lat}}^{\top} \end{bmatrix}$. That means we only look for short vectors $\begin{pmatrix} \mathbf{x} \\ \mathbf{y}_{\mathrm{lat}} \end{pmatrix}$ such that $\mathbf{A}_{\mathrm{lat}}^{\top}\mathbf{x} = \mathbf{y}_{\mathrm{lat}} \quad \mathrm{mod} \quad q$. Define $\mathbf{y}_{\mathrm{enu}}$ by $\mathbf{y}_{\mathrm{enu}} = \mathbf{A}_{\mathrm{enu}}^{\top}\mathbf{x}$. The point is that looking for such vectors is faster because of the dimension reduction. We then guess $\mathbf{s}_{\mathrm{enu}}$ and check whether the $\langle \mathbf{x}, \mathbf{b} \rangle - \langle \mathbf{y}_{\mathrm{enu}}, \mathbf{s}_{\mathrm{enu}} \rangle$'s are tilted towards small values or not. This comes from the fact that

$$ \begin{aligned} \langle \mathbf{x}, \mathbf{b} \rangle &= \langle \mathbf{x}, \mathbf{A}_{\mathrm{enu}}\mathbf{s}_{\mathrm{enu}} + \mathbf{A}_{\mathrm{lat}}\mathbf{s}_{\mathrm{lat}} + \mathbf{e} \rangle = \langle \mathbf{A}_{\mathrm{enu}}^{\top}\mathbf{x}, \mathbf{s}_{\mathrm{enu}} \rangle + \langle \mathbf{A}_{\mathrm{lat}}^{\top}\mathbf{x}, \mathbf{s}_{\mathrm{lat}} \rangle + \langle \mathbf{x}, \mathbf{e} \rangle \\ &= \langle \mathbf{y}_{\mathrm{enu}}, \mathbf{s}_{\mathrm{enu}} \rangle + \langle \mathbf{y}_{\mathrm{lat}}, \mathbf{s}_{\mathrm{lat}} \rangle + \langle \mathbf{x}, \mathbf{e} \rangle \quad \mathrm{mod} \quad q \end{aligned} \quad (1.1) $$

In [EJK20] this was generalized to broader secret distributions paired with additional improvements on the exhaustive search. [GJ21] applied a Fast Fourier Transform-style algorithm to the search over $\mathbf{s}_{\mathrm{enu}}$ and the search space is significantly reduced by roughly considering only the most significant bits of $\mathbf{s}_{\mathrm{enu}}$. [MAT22] replaced this step with “modulus switching” [BV11,AFFP14], yielding significant performance gains. The algorithm can be described as follows.

<footnote n="4">⁴ https://csrc.nist.gov/projects/post-quantum-cryptography</footnote>
The MATZOV template. Let $n_{enu}$, $n_{fft}$, $n_{lat}$ be some positive integers such that $n_{enu}+n_{fft}+n_{lat} = n$. The matrix $\mathbf{A}$ and the secret $\mathbf{s}$ are divided accordingly:

$$ \mathbf{A} \triangleq [\mathbf{A}_{enu} \ \mathbf{A}_{fft} \ \mathbf{A}_{lat}] \in \mathbb{Z}_{q}^{m \times n_{enu}} \times \mathbb{Z}_{q}^{m \times n_{fft}} \times \mathbb{Z}_{q}^{m \times n_{lat}}, \qquad (1.2) $$

$$ \mathbf{s} \triangleq \begin{pmatrix} \mathbf{s}_{enu} \\ \mathbf{s}_{fft} \\ \mathbf{s}_{lat} \end{pmatrix} \in \mathbb{Z}_{q}^{n_{enu}} \times \mathbb{Z}_{q}^{n_{fft}} \times \mathbb{Z}_{q}^{n_{lat}}. \qquad (1.3) $$

The objective is to guess the part $\mathbf{s}_{enu}$ of the secret vector but to do that, we need to be able to distinguish between a right and a wrong guess. By performing lattice reduction on the lattice generated by $[\mathbf{Id}_m \quad \mathbf{0} \quad \mathbf{A}_{lat}^\top \quad q\mathbf{Id}_{n_{lat}}]$ , we obtain a set $\mathcal{S}$ of vectors $(\mathbf{x} \quad \mathbf{y})$ such that $\mathbf{x}$ and $\mathbf{y}$ are of small Euclidean norm in $\mathbb{Z}_q^m$ and $\mathbb{Z}_q^{n_{lat}}$ respectively and are such that $\mathbf{y} = \mathbf{A}_{lat}^\top \mathbf{x}$. Similarly to Equation (1.1), we have

$$ \langle \mathbf{x}, \mathbf{b} - \mathbf{A}_{enu}\mathbf{s}_{enu} \rangle - \langle \mathbf{A}_{fft}^\top \mathbf{x}, \mathbf{s}_{fft} \rangle = \langle \mathbf{x}, \mathbf{e} \rangle + \langle \mathbf{y}, \mathbf{s}_{lat} \rangle. \qquad (1.4) $$

Since $(\mathbf{x}, \mathbf{y})$ and $(\mathbf{e}, \mathbf{s}_{lat})$ are short, Equation (1.4) is biased towards zero, raising the issue of finding efficiently $\mathbf{s}_{enu}$ and $\mathbf{s}_{fft}$ such that the left-hand term in (1.4) is small.

One can notice that (1.4) actually gives us many small-LWE sample$^5$ $(\mathbf{a}', \mathbf{b}') \in \mathbb{Z}_q^{n_{fft}} \times \mathbb{Z}_q$ with secret $\mathbf{s}' \in \mathbb{Z}_q^{n_{fft}}$ and error $\mathbf{e}' \in \mathbb{Z}_q$ where

$$ \mathbf{a}' \triangleq \mathbf{A}_{fft}^{\top} \mathbf{x}, \qquad (1.5) $$

$$ \mathbf{b}' \triangleq \langle \mathbf{x}, \mathbf{b} - \mathbf{A}_{enu}\mathbf{s}_{enu} \rangle, \qquad (1.6) $$

$$ \mathbf{s}' \triangleq \mathbf{s}_{fft}, \qquad (1.7) $$

$$ \mathbf{e}' \triangleq \langle \mathbf{x}, \mathbf{e} \rangle + \langle \mathbf{y}, \mathbf{s}_{lat} \rangle. \qquad (1.8) $$

Thus, we can distinguish a correct and an incorrect guess for $\mathbf{s}_{enu}$ and recover $\mathbf{s}_{fft}$ by solving this small-LWE instance. Since $n_{enu}$ is small enough, $\mathbf{s}_{enu}$ can be exhaustively searched. Once $\mathbf{s}_{enu}$ is identified, $\mathbf{s}_{fft}$ is recovered by solving the above small-LWE instance. Specifically, this involves exhaustively searching for a $\mathbf{z} \in \mathbb{Z}_q^{n_{fft}}$ such that the vector $((\mathbf{x}, \mathbf{b} - \mathbf{A}_{enu}\mathbf{s}_{enu}) - \langle \mathbf{A}_{fft}^\top \mathbf{x}, \mathbf{z} \rangle)_{(\mathbf{x}, \mathbf{y}) \in \mathcal{S}}$ has a small Euclidean norm. One approach to speed up the search is to use a Fourier transform. The method introduces an evaluation function $E$, which assigns a real value to each guess $\tilde{\mathbf{s}}_{enu} \in \mathbb{Z}_q^{n_{enu}}$:

$$ E(\tilde{\mathbf{s}}_{enu}) \triangleq \max_{\mathbf{z} \in \mathbb{Z}_q^{n_{fft}}} F_{\tilde{\mathbf{s}}_{enu}}(\mathbf{z}) \qquad (1.9) $$

where

$$ F_{\tilde{\mathbf{s}}_{enu}}(\mathbf{z}) \triangleq \sum_{(\mathbf{x}, \mathbf{y}) \in \mathcal{S}} \cos \left( \frac{2\pi}{q} \left( \langle \mathbf{x}, \mathbf{b} - \mathbf{A}_{enu}\tilde{\mathbf{s}}_{enu} \rangle - \langle \mathbf{A}_{fft}^{\top}\mathbf{x}, \mathbf{z} \rangle \right) \right). \qquad (1.10) $$

MATZOV's algorithm essentially consists in finding $\tilde{\mathbf{s}}_{enu} \in \mathbb{Z}_q^{n_{enu}}$ such that $E(\tilde{\mathbf{s}}_{enu}) \ge T$, where $T \in \mathbb{N}$ is a threshold chosen around the expected value of $E$ when evaluated on the correct guess, namely $T \approx E(\mathbf{s}_{enu})$. The key idea is that we expect $E(\mathbf{s}_{enu})$ to be significantly larger than $E(\tilde{\mathbf{s}}_{enu})$ when $\tilde{\mathbf{s}}_{enu}$ is incorrect, i.e. when $\tilde{\mathbf{s}}_{enu} \neq \mathbf{s}_{enu}$. Indeed, for the correct guess, Equation (1.4) shows that $\langle \mathbf{x}, \mathbf{b} - \mathbf{A}_{enu}\mathbf{s}_{enu} \rangle - \langle \mathbf{A}_{fft}^{\top}\mathbf{x}, \mathbf{s}_{fft} \rangle \mod q$ is biased toward zero. Consequently, each term in the sum in Equation (1.10) will be biased toward 1, resulting in a large total value for $\mathbb{E}(F_{\tilde{\mathbf{s}}_{enu}}(\mathbf{s}_{fft}))$. On the other hand, if $\tilde{\mathbf{s}}_{enu} \neq \mathbf{s}_{enu}$, then for all $\mathbf{z} \in \mathbb{Z}_q^{n_{fft}}$, $\langle \mathbf{x}, \mathbf{b} - \mathbf{A}_{enu}\tilde{\mathbf{s}}_{enu} \rangle - \langle \mathbf{A}_{fft}^{\top}\mathbf{x}, \mathbf{z} \rangle \mod q$ is uniformly distributed over $\mathbb{Z}_q$, meaning that $\mathbb{E}(F_{\tilde{\mathbf{s}}_{enu}}(\mathbf{z})) = 0$.

<footnote>$^5$ By using $N$ samples $\{(\mathbf{a}'_i, \mathbf{b}'_i)\}_{i \in [1, N]}$, we can rewrite the LWE instance with a matrix $\mathbf{A}' \triangleq [\mathbf{a}'_1 \cdots \mathbf{a}'_N]$ and a vector $\mathbf{b}' \triangleq (\mathbf{b}'_1 \cdots \mathbf{b}'_N)^\top$.</footnote>
Modulus switching. The point of using the evaluation function E is that $F_{\tilde{s}_{enu}}$ can be computed efficiently with a Fast Fourier Transform (FFT). However, the large input space $\mathbb{Z}_q^{n_{fft}}$ makes the FFT costly. This size can be reduced, though at the cost of slightly weakening the bias of $F_{\tilde{s}_{enu}}(\mathbf{s}_{fft})$.

To do that, MATZOV proposes to reduce the size of the field $\mathbb{Z}_q$ by using a modulus switching technique: instead of considering $F_{\tilde{s}_{enu}}$, they consider

$$F_{\tilde{s}_{enu}}^{(\text{ms})}: \mathbb{Z}_p^{n_{fft}} \to \mathbb{R} \\ \mathbf{z} \mapsto \sum_{(\mathbf{x}, \mathbf{y}) \in \mathcal{S}} \cos \left( \frac{2\pi}{p} \left( \frac{p}{q} \langle \mathbf{x}, \mathbf{b} - \mathbf{A}_{enu} \tilde{\mathbf{s}_{enu}} \rangle - \langle \lfloor \frac{p}{q} \mathbf{A}_{fft}^{\top} \mathbf{x} \rfloor, \mathbf{z} \rangle \right) \right)$$

where $p \le q$ is a smaller modulus and $\lfloor \cdot \rfloor$ stands for the integer rounding operation. Thus, for the wrong guess $\tilde{\mathbf{s}}_{enu} \neq \mathbf{s}_{enu}$ and for all $\mathbf{z} \in \mathbb{Z}_p^{n_{fft}}$, $F_{\tilde{\mathbf{s}}_{enu}}^{(\text{ms})}(\mathbf{z})$ is still expected to be 0 whereas for the good guess $\mathbf{s}_{enu}$ we have, from Equation (1.4),

$$F_{\tilde{s}_{enu}}^{(\text{ms})}(\mathbf{s}_{fft} \bmod p) = \sum_{(\mathbf{x}, \mathbf{y}) \in \mathcal{S}} \cos \left( \frac{2\pi}{p} \left( \frac{p}{q} \langle \mathbf{x}, \mathbf{e} \rangle + \frac{p}{q} \langle \mathbf{y}, \mathbf{s}_{lat} \rangle + \langle \frac{p}{q} \mathbf{A}_{fft}^{\top} \mathbf{x} - \lfloor \frac{p}{q} \mathbf{A}_{fft}^{\top} \mathbf{x} \rfloor, \mathbf{s}_{fft} \rangle \right) \right) \\ = \sum_{(\mathbf{x}, \mathbf{y}) \in \mathcal{S}} \cos \left( \frac{2\pi}{q} \left( \langle \mathbf{x}, \mathbf{e} \rangle + \langle \mathbf{y}, \mathbf{s}_{lat} \rangle + \langle \mathbf{A}_{fft}^{\top} \mathbf{x} - \frac{q}{p} \lfloor \frac{p}{q} \mathbf{A}_{fft}^{\top} \mathbf{x} \rfloor, \mathbf{s}_{fft} \rangle \right) \right).$$

Even if it means reducing the threshold a little, we can still expect $F_{\tilde{s}_{enu}}^{(\text{ms})}(\mathbf{s}_{fft} \bmod p) \ge T$ since the additional term $\langle \mathbf{A}_{fft}^{\top} \mathbf{x} - \frac{q}{p} \lfloor \frac{p}{q} \mathbf{A}_{fft}^{\top} \mathbf{x} \rfloor, \mathbf{s}_{fft} \rangle$ is also biased toward zero. Indeed, it is the scalar product of two short vectors; in particular:

$$d_{\text{ms}} \triangleq \mathbb{E} \left( \left\| \mathbf{A}_{\text{fft}}^{\top} \mathbf{x} - \frac{q}{p} \lfloor \frac{p}{q} \mathbf{A}_{\text{fft}}^{\top} \mathbf{x} \rfloor \right\| \right) \approx \frac{q}{p} \sqrt{\frac{n_{\text{fft}}}{12}} \quad (1.11)$$

since we can make the approximation that each of the coordinates of $\frac{p}{q} \mathbf{A}_{fft}^{\top} \mathbf{x} - \lfloor \frac{p}{q} \mathbf{A}_{fft}^{\top} \mathbf{x} \rfloor$ are drawn uniformly at random in $] -0.5, 0.5]$.

Finally, [MAT22] claims that the security level of NIST candidates like KYBER could be significantly lowered. However, this result is not widely accepted, as the analysis relies on assumptions which turn out to be false according to [DP23b].

**Dual Attacks in Code-Based Cryptography and Analyzing Dual Attacks.** Dual attacks in lattice based cryptography can be viewed as the lattice based analogue of statistical decoding in code-based cryptography which dates back to Al Jabri [Jab01]. In this case, short codewords $\mathbf{h}$ in the dual code are computed, where short is with respect to the Hamming distance. The goal is to solve the decoding problem $\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}$ where $\mathbf{b}$ and $\mathbf{A}$ are given whereas $\mathbf{s}$ and $\mathbf{e}$ are unknown and $\mathbf{e}$ is of small Hamming weight (rather than of small Euclidean norm for the LWE problem). The issue is to recover $\mathbf{s}$. Here too, the inner product $\langle \mathbf{h}, \mathbf{b} \rangle$ is biased towards zero. This is used to solve the decoding problem very much in the same way as it is used to solve the LWE problem. Similarly to what happened in lattice based cryptography, dual attacks became much more effective through a splitting strategy which allowed to look for short codewords in a smaller code [CDMT22]. In an analogous way to what was done in lattice based cryptography, these attacks were analyzed by making assumptions and in particular independence assumptions [CDMT22, Ass. 3.7] which are close to the independence assumptions made for analyzing MATZOV's attack [MAT22, Ass. 4.4, Ass. 5.8]. In the lattice based case, these assumptions were shown to contradict some theorems in certain regimes or well-tested heuristics in some other regimes [DP23b].

Note that it was already noticed in [CDMT22, §3.4] that the i.i.d. Bernoulli model used for analyzing dual attacks in code-based cryptography is not always accurate. However, it was conjectured there that the difference between this ideal model and experiments has no impact on the asymptotic analysis of the decoding based on this model. This was proved to be wrong in [MT23]. 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] shedding some light on the fundamental quantities manipulated by the decoder. This allowed to obtain a proof of the correctness of a slightly modified version of the dual attack proposed in [CDMT22]. Dual attacks for solving the decoding problem have been further improved in [CDMT24] and the approach of [MT23] has been carried over to this improved dual attack. [CDMT24] can be viewed as a somewhat improved version of the MATZOV attack in the context of codes, where the modulus switching part is replaced by an optimal lossy source encoder. It is worthwhile to note that [CDMT24, Section 8] shows that the fundamental duality equation [MT23, Prop. 1.3] used to analyze dual attacks for codes also carries over to the lattice setting and could serve as a tool to analyze dual attacks for lattices. Moreover, at the same time, a series of papers [DP23a,PS24] provide some new ideas to properly analyze dual attacks in lattices. In particular, concurrently to [CDMT24, Section 8], [DP23a] provided, in a more in-depth work and using comparable but not identical reasoning, similar heuristics to predict the behavior of these attacks.

## 1.2 Our Contribution

Our purpose here is to come up with a variation of the MATZOV algorithm, that improves it and which also helps analyzing it. This is obtained by a lattice based analogue of [CDMT24], replacing the modulus switching by lossy source encoding/using the relevant quantizer based on polar coding. We use the duality approach [MT23,CDMT24,DP23a] to analyze our new dual attack to avoid relying on independence assumptions. This duality approach allows us to derive a new simple heuristic that is backed up by experimental evidence and which is essentially a generalization of the heuristics made in [CDMT24,DP23a]. All in all, it turns out that the complexities claimed in [MAT22] can be achieved and even slightly surpassed with our algorithm, which dents the parameters of KYBER by a few bits, as predicted in [MAT22].

**A Lossy Source Coding/Quantizer Approach.** Similarly to [CDMT24] we observe that the FFT approach factorizing the common computations for computing all the $F_{s_{enu}}(z)$ for $z \in \mathbb{Z}_q^{n_{ft}}$ is probably suboptimal, since the $z$ such that $F_{s_{enu}}(z)$ is maximum is likely to be attained for $z = s_{fft}$ which is of rather small norm. The problem is that the fast FFT algorithm doesn't leverage the fact that we only need to compute it for small $z$'s which have the same Euclidean norm as $s_{fft}$. In a sense, the modulus switching approach of [MAT22] is a way to alleviate this phenomenon since $s_{fft}$ mod $p$ is more uniformly distributed in $\mathbb{Z}_p^{n_{ft}}$ than $s$ is in $\mathbb{Z}_q^{n_{ft}}$. A further refinement of this method, in the spirit of [GJS15, Section 5.5], involves approximating the relevant $z \in \mathbb{Z}_q^{n_{ft}}$'s by close enough codewords. This also allows to reduce the size $q^{n_{ft}}$ of the space over which the fast Fourier transform is applied.

Basically the lossy source/quantizing approach can be explained as follows. We choose a linear code $C_{lsc}$ generated by the matrix $G \in \mathbb{Z}_q^{n_{ft} \times k_{ft}}$, i.e. $C_{lsc} \triangleq \{G u_{lsc} : u_{lsc} \in \mathbb{Z}_q^{k_{ft}}\}$ so that we can find efficiently, for any $y_{fft} \in \mathbb{Z}_q^{n_{ft}}$, a $u_{lsc} \in \mathbb{Z}_q^{k_{ft}}$ such that $G u_{lsc}$ is close to $y_{fft}$. $G u_{lsc}$ can be viewed as a "quantization" of $y_{fft}$ and $C_{lsc}$ as a lossy source code or code used for quantization. We apply this quantization to all pairs of short dual vectors $(x, y)$ in $\mathcal{S}$ and compute for all such $x$'s a corresponding $u_{lsc} \in \mathbb{Z}_q^{k_{ft}}$ such that

$$ \| \mathbf{A}_{fft}^{\top} \mathbf{x} - \mathbf{G} \mathbf{u}_{lsc} \| \approx d_{lsc} \qquad (1.12) $$

where $d_{lsc}$ is the decoding distance of the lossy source code. The point is that the left hand term in (1.4) can be rewritten as

$$ \langle \mathbf{x}, \mathbf{b} - \mathbf{A}_{enu}\mathbf{s}_{enu} \rangle - \langle \mathbf{A}_{fft}^{\top}\mathbf{x}, \mathbf{s}_{fft} \rangle = \langle \mathbf{x}, \mathbf{b} - \mathbf{A}_{enu}\mathbf{s}_{enu} \rangle - \langle \mathbf{G}\mathbf{u}_{lsc}, \mathbf{s}_{fft} \rangle - \langle \mathbf{e}_{lsc}, \mathbf{s}_{fft} \rangle \quad (1.13) $$

$$ = \langle \mathbf{x}, \mathbf{b} - \mathbf{A}_{enu}\mathbf{s}_{enu} \rangle - \langle \mathbf{u}_{lsc}, \mathbf{G}^{\top}\mathbf{s}_{fft} \rangle - \langle \mathbf{e}_{lsc}, \mathbf{s}_{fft} \rangle \quad (1.14) $$

where $\mathbf{e}_{lsc} \triangleq \mathbf{A}_{fft}^{\top}\mathbf{x} - \mathbf{G}\mathbf{u}_{lsc}$. If we use (1.4) we see that

$$ \langle \mathbf{x}, \mathbf{b} - \mathbf{A}_{enu}\mathbf{s}_{enu} \rangle - \langle \mathbf{u}_{lsc}, \mathbf{G}^{\top}\mathbf{s}_{fft} \rangle = \langle \mathbf{x}, \mathbf{e} \rangle + \langle \mathbf{y}, \mathbf{s}_{lat} \rangle + \langle \mathbf{e}_{lsc}, \mathbf{s}_{fft} \rangle. \quad (1.15) $$
So we expect that the left-hand term $\langle \mathbf{x}, \mathbf{b} - \mathbf{A}_{\text{enu}}\mathbf{s}_{\text{enu}} \rangle - \langle \mathbf{u}_{\text{lsc}}, \mathbf{G}^{\top}\mathbf{s}_{\text{fft}} \rangle$ is still small. In other words, we once again performed a reduction to an LWE problem. Indeed, Equation (1.15) can be interpreted as an LWE sample $(\mathbf{a}', \mathbf{b}') \in \mathbb{Z}_q^{k_{\text{mt}}} \times \mathbb{Z}_q$, with secret $\mathbf{s}' \in \mathbb{Z}_q^{k_{\text{mt}}}$ and error term $\mathbf{e}' \in \mathbb{Z}_q$, where

$$ \mathbf{a}' \triangleq \mathbf{u}_{\text{lsc}}, \qquad (1.16) $$

$$ \mathbf{b}' \triangleq \langle \mathbf{x}, \mathbf{b} - \mathbf{A}_{\text{enu}}\mathbf{s}_{\text{enu}} \rangle, \qquad (1.17) $$

$$ \mathbf{s}' \triangleq \mathbf{G}^{\top}\mathbf{s}_{\text{fft}}, \qquad (1.18) $$

$$ \mathbf{e}' \triangleq \langle \mathbf{x}, \mathbf{e} \rangle + \langle \mathbf{y}, \mathbf{s}_{\text{lat}} \rangle + \langle \mathbf{e}_{\text{lsc}}, \mathbf{s}_{\text{fft}} \rangle. \qquad (1.19) $$

The advantage of this reduction is that it drastically reduces the dimension of the problem. However, it is important to note that the secret $\mathbf{s}'$ is no longer small, but uniformly distributed over $\mathbb{Z}_q^{k_{\text{mt}}}$; thus, this new problem becomes a plain-LWE problem. We can now solve it using a technique similar to the one previously described. This motivates to replace $F_{\tilde{\mathbf{s}}_{\text{enu}}}$ by

$$ F_{\tilde{\mathbf{s}}_{\text{enu}}}^{(\text{lsc})} : \mathbb{Z}_{q}^{k_{\text{fft}}} \rightarrow \mathbb{R} \\ \mathbf{z} \mapsto \sum_{(\mathbf{x}, \mathbf{y}) \in \mathcal{S}} \cos \left( \frac{2\pi}{q} \left( \langle \mathbf{x}, \mathbf{b} - \mathbf{A}_{\text{enu}}\tilde{\mathbf{s}}_{\text{enu}} \rangle - \langle \mathbf{u}_{\text{lsc}}, \mathbf{z} \rangle \right) \right). \qquad (1.20) $$

Again, for the wrong guess $\tilde{\mathbf{s}}_{\text{enu}} \neq \mathbf{s}_{\text{enu}}$ and for all $\mathbf{z} \in \mathbb{Z}_p^{k_{\text{fft}}}$, $F_{\tilde{\mathbf{s}}_{\text{enu}}}^{(\text{lsc})}(\mathbf{z})$ is still expected to be 0 whereas for the good guess $\mathbf{s}_{\text{enu}}$ we have, from Equation (1.15), that

$$ F_{\tilde{\mathbf{s}}_{\text{enu}}}^{(\text{lsc})} (\mathbf{G}^{\top} \mathbf{s}_{\text{fft}}) = \sum_{(\mathbf{x}, \mathbf{y}) \in \mathcal{S}} \cos \left( \frac{2\pi}{q} \left( \langle \mathbf{x}, \mathbf{e} \rangle + \langle \mathbf{y}, \mathbf{s}_{\text{lat}} \rangle + \langle \mathbf{e}_{\text{lsc}}, \mathbf{s}_{\text{fft}} \rangle \right) \right) \qquad (1.21) $$

which is still expected to be large because the additional term $\langle \mathbf{e}_{\text{lsc}}, \mathbf{s}_{\text{fft}} \rangle$ is biased towards zero.

The pro and cons of this approach is that on the positive side:

- It allows us to choose large values for $n_{\text{fft}}$, since we are now not limited by the $q^{n_{\text{fft}}}$ term in the complexity coming from evaluating $F_{\tilde{\mathbf{s}}_{\text{enu}}}$ but by a smaller $q^{k_{\text{fft}}}$ term. This in turn allows us to decrease the $n_{\text{lat}}$ term and therefore the cost of lattice reduction.

- It allows us to solve radically the problem that $\mathbf{s}_{\text{fft}}$ is not uniformly distributed in $\mathbb{Z}_q^{n_{\text{fft}}}$. If $k_{\text{fft}}$ is low enough, it can namely be verified that the likely argmax $\mathbf{G}^{\top}\mathbf{s}_{\text{fft}}$ of $F_{\tilde{\mathbf{s}}_{\text{enu}}}^{(\text{lsc})}(\mathbf{z})$ is uniformly distributed in $\mathbb{Z}_q^{k_{\text{fft}}}$. This solves one source of suboptimality of this approach.

On the negative side, it increases the noise term in the right-hand side of (1.15) expressing the quantity $\langle \mathbf{x}, \mathbf{b} - \mathbf{A}_{\text{enu}}\mathbf{s}_{\text{enu}} \rangle - \langle \mathbf{u}_{\text{lsc}}, \mathbf{G}^{\top}\mathbf{s}_{\text{fft}} \rangle$. This is due to the additional term $\langle \mathbf{e}_{\text{lsc}}, \mathbf{s}_{\text{fft}} \rangle$ which appears there. We therefore expect $F_{\tilde{\mathbf{s}}_{\text{enu}}}^{(\text{lsc})}(\mathbf{G}^{\top}\mathbf{s}_{\text{fft}})$ to be smaller than $F_{\tilde{\mathbf{s}}_{\text{enu}}}^{(\text{lsc})}(\mathbf{s}_{\text{fft}})$ and will need to make $\mathcal{S}$ bigger to distinguish it from other values of $F_{\tilde{\mathbf{s}}_{\text{enu}}}^{(\text{lsc})}(\mathbf{z})$.

The last point above makes it clear that we want to make the additional noise term $\langle \mathbf{e}_{\text{lsc}}, \mathbf{s}_{\text{fft}} \rangle$ as small as possible. But of course for a given $k_{\text{fft}}$, there is a lower bound of what we can achieve. It can namely be proven (see Equation (2.11) in Section 2) that the best we can do is to choose, for a given $k_{\text{fft}}$, the decoding distance $d_{\text{lsc}}$ such that

$$ d_{\text{lsc}} \approx q^{1-\frac{k_{\text{fft}}}{n_{\text{fft}}}} \cdot \sqrt{\frac{n_{\text{fft}}}{2\pi e}}. \qquad (1.22) $$

This can be compared to the modulus switching approach. For a same FFT complexity, meaning roughly that $k_{\text{fft}}$ is such that $p^{n_{\text{fft}}} = q^{k_{\text{fft}}}$, we have

$$ d_{\text{ms}} \approx \frac{q}{p} \sqrt{\frac{n_{\text{fft}}}{12}} \approx 0.28867 \frac{q\sqrt{n_{\text{fft}}}}{p} \qquad (1.23) $$

$$ d_{\text{lsc}} \approx \frac{q}{p} \sqrt{\frac{n_{\text{fft}}}{2\pi e}} \approx 0.24197 \frac{q\sqrt{n_{\text{fft}}}}{p} \qquad (1.24) $$
Equations (1.23) and (1.24) show that the lossy source coding approach yields a smaller value for $\|\langle e_{\text{lsc}}, s_{\text{fft}} \rangle\|$ than modulus switching, as $d_{\text{lsc}} < d_{\text{ms}}$. However, unlike modulus switching, we need to construct a code that can be decoded efficiently up to the optimal decoding distance $d_{\text{lsc}}$. A classical approach involves using a Cartesian product of small random codes. This solution achieves asymptotically the optimal decoding distance $d_{\text{lsc}}$ but with a sub-exponential complexity that is not so negligible (super-polynomial). In Section 3.3, we propose an alternative solution using polar codes, which can achieve a decoding distance very close to $d_{\text{lsc}}$ in quasi-linear time.

It should be noted that the modulus switching strategy can really be viewed as a quantizing approach. In the modulus switching technique, we approximate $A_{\text{fft}}^{\top}x$ by $\frac{q}{p} \left\lfloor \frac{p}{q} A_{\text{fft}}^{\top}x \right\rfloor$, i.e. we quantize/approximate a point in $\mathbb{R}^{n_{\text{fft}}}$ by a point in the lattice $\frac{q}{p}\mathbb{Z}^{n_{\text{fft}}}$. On the other hand, in the case of the lossy source code approach we approximate a point in $\mathbb{Z}^{n_{\text{fft}}}$ by a codeword in $C_{\text{lsc}}$. If we express this as a quantizer, this means that we quantize/approximate a point in $\mathbb{R}^{n_{\text{fft}}}$ by a lattice point in Construction A applied to $C_{\text{lsc}}$. The second quantizer just turns out to be much better than the first quantizer in terms of the distortion/quantizing distance which is achieved.

**Getting Rid of Independence Assumptions in the Analysis and Results.** In [MAT22], it is argued that dual attacks can substantially lower the security level of certain NIST candidates, such as KYBER. However, this claim remains contested, as their analysis relies on assumptions that, according to [DP23b], have been proven to be incorrect. Specifically, [DP23b] highlights a flawed independence assumption, which can be stated as follows:

**Assumption 1.1 (Independence Assumption).** Let $\Lambda$ be a full-rank lattice of dimension $n$, and let $\mathbf{r}$ be a random variable distributed according to $\text{Unif}(\mathbb{R}^n/\Lambda)$ or $\mathcal{B}_{\alpha}^n$, where the $\mathcal{B}_{\alpha}$ are i.i.d. centered binomial variables. Assume that $(e^{2i\pi\langle\mathbf{w},\mathbf{r}\rangle})_{\mathbf{w}\in\Lambda}$ are mutually independent.

In dual attacks, evaluation functions involve sums of terms like those described in the assumption. Assuming independence when the terms are not independent can lead to significant miscalculations in estimating false positives passing the evaluation function. This issue is highlighted in [DP23b], which shows that predictions of such scoring functions are inaccurate in certain regimes.

Recent papers [DP23a,MT23,CDMT24] present new approaches to analyze dual attacks accurately, without relying on the independence assumption. Specifically, let

$$F(\mathbf{x}) \triangleq \sum_{\mathbf{w} \in \Lambda \cap \mathcal{B}} e^{2i\pi \langle \mathbf{w}, \mathbf{r}(\mathbf{x}) \rangle} \qquad (1.25)$$

define a scoring function, where $\Lambda$ is a full-rank lattice of dimension $n$, $\mathcal{B} \subseteq \mathbb{R}^n$ a set of small vectors, and $\mathbf{r}(\mathbf{x}) \in \mathbb{R}^n$, all depending on the specific dual attack method under consideration. It can be observed that $F(\mathbf{x})$ remains invariant when any vector from the dual lattice of $\Lambda$ is added to $\mathbf{r}(\mathbf{x})$. Indeed, for any $\mathbf{w}^{\vee} \in \Lambda^{\vee}$, we have

$$\langle \mathbf{w}, \mathbf{r}(\mathbf{x}) + \mathbf{w}^{\vee} \rangle = \langle \mathbf{w}, \mathbf{r}(\mathbf{x}) \rangle + \langle \mathbf{w}, \mathbf{w}^{\vee} \rangle = \langle \mathbf{w}, \mathbf{r}(\mathbf{x}) \rangle. \qquad (1.26)$$

Thus, it is reasonable to conclude that $\langle \mathbf{w}, \mathbf{r}(\mathbf{x}) \rangle$ depends on the structure of the coset $\Lambda^{\vee} + \mathbf{r}(\mathbf{x})$, and in particular, on its shortest vector. One way to see this is by invoking the Poisson summation formula:

$$F(\mathbf{x}) = \frac{1}{\text{Vol}(\Lambda)} \cdot \sum_{\mathbf{w}^{\vee} \in \Lambda^{\vee} + \mathbf{r}(\mathbf{x})} \widehat{1}_{\mathcal{B}}(\mathbf{w}^{\vee}). \qquad (1.27)$$

In [DP23a,CDMT24], it was observed that the Fourier transform of the indicator function can be expressed in terms of Bessel functions, depending only on the input's length. Consequently, $F(\mathbf{x})$ is essentially related to the length enumerator of the vectors in $\Lambda^{\vee} + \mathbf{r}(\mathbf{x})$, particularly the shortest. We distinguish between correct and incorrect candidates by noting that $\mathbf{r}(\mathbf{x})$ is notably small when $\mathbf{x}$ is the desired vector, and random otherwise. Therefore, for the correct guess, the
shortest vector in $\Lambda^\vee + \mathbf{r}(\mathbf{x})$ is $\mathbf{r}(\mathbf{x})$, while for incorrect guesses, it corresponds to the typical shortest vector in a random coset of a random lattice.

This approach allowed us to analyze our evaluation functions thoroughly (see Section 4). However, to simplify calculations, we make approximations that we validate through simulations. Finally, we control the number of false positives in our attack, ensuring they remain negligible. By doing so, we achieve results close to those of MATZOV (see Section 5). Furthermore, as they did previously, we apply our attack to the parameters of KYBER and confirm the claim in [MAT22], which asserts that KYBER's security does not meet the NIST's requirements.

## 2 Notation and Preliminaries

**Basic Notation.** We denote vectors by bold lowercase letters and matrices by bold uppercase letters, e.g. $\mathbf{v}$ and $\mathbf{M}$. We consider the vectors as column vectors and therefore row vectors are denoted $\mathbf{v}^\top$. The concatenation of vectors $\mathbf{x}$ and $\mathbf{y}$ is denoted as $(\mathbf{x}, \mathbf{y})$. The components of the vector $\mathbf{x} \in \mathbb{R}^n$ are denoted by $x_i$ for $i \in \llbracket 1, n \rrbracket$ where $\llbracket a, b \rrbracket$ are the integers between $a$ and $b$.

For any $x \in \mathbb{Z}_q$, denote by $\hat{x} \in x + q\mathbb{Z}$ the unique integer such that $|\hat{x}| \le \frac{q-1}{2}$. We extend this notion to vectors $\mathbf{x} \in \mathbb{Z}_q^n$ componentwise. In other words, $\hat{x}$ is the lift from $\mathbb{Z}_q$ to $\mathbb{Z}$ centered on 0. We define $\|\mathbf{x}\|$ for $\mathbf{x} \in \mathbb{Z}_q^n$ as

$$ \|\mathbf{x}\| \triangleq \|\hat{\mathbf{x}}\| \triangleq \sqrt{\sum_{i=1}^{n} \hat{x}_i^2} \triangleq \sqrt{\sum_{i=1}^{n} \operatorname{argmin}_{j \in \mathbb{Z}} ((x_i + jq)^2)} \quad (2.1) $$

**The Learning With Error Problem.** Let us define more formally the LWE problem here. It starts by defining an LWE oracle that produces samples according to the following distribution:

**Definition 2.1 (LWE oracle).** Let $q, n, m \in \mathbb{N}$, and let $\chi_s, \chi_e$ be distributions over $\mathbb{Z}_q$. We first draw $\mathbf{s} \in \mathbb{Z}_q^n$ with coordinates drawn independently from each other according to the distribution $\chi_s$ and then draw $m$ LWE samples $(\mathbf{a}_i, b_i) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$ where the $\mathbf{a}_i$'s are drawn uniformly at random in $\mathbb{Z}_q^n$ and $b_i = \langle \mathbf{a}_i, \mathbf{s} \rangle + e_i$ where the $e_i$'s are drawn independently according to the distribution $\chi_e$. We let $\mathbf{A} \in \mathbb{Z}_q^{m \times n}$ be the matrix where the i-th row is $\mathbf{a}_i$. The pair $(\mathbf{A}, \mathbf{b})$ is the output of the oracle and satisfies $\mathbf{b} \triangleq \mathbf{A}\mathbf{s} + \mathbf{e}$.

We then define the Search-LWE problem as follows:

**Problem 2.2 (Search-LWE).** Given a sample $(\mathbf{A}, \mathbf{b})$ drawn from an LWE $(q, n, m, \chi_s, \chi_e)$-oracle, the goal is to recover the secret vector $\mathbf{s}$.

In the literature, the LWE oracle is sometimes defined by replacing the matrix $\mathbf{A} \in \mathbb{Z}_q^{m \times n}$ by a vector $\mathbf{a} \in \mathbb{Z}_q^n$. Then the LWE problems are stated for an arbitrary number of calls to the oracle. If the LWE oracle is called $m$ times, then the situation is actually the same as above.

**The Centered Binomial Distribution.** In the LWE oracle, the distributions $\chi_s$ and $\chi_e$ depend on the context. Historically, the secret vector $\mathbf{s}$ was distributed uniformly in $\mathbb{Z}_q^n$ and the noise vector $\mathbf{e}$ was short. It is quite common today to consider the case where $\mathbf{s}$ is also short; we are then talking about Small-LWE problem. In recent cryptosystems, particularly those involved in the NIST Post-Quantum Standardization Process, the distributions for $\chi_s$ and $\chi_e$ are centered binomial distributions. Note that in KYBER, the distribution for the secret vector and the error vector is the same.

**Definition 2.3 (Centered Binomial Distribution).** The centered binomial distribution $\mathcal{B}_\alpha$ of parameter $\alpha \in [0, \frac{q-1}{2}]$ is defined as $\mathcal{B}_\alpha \sim \sum_{i=1}^\alpha (X_i - Y_i)$ where the $X_i$'s and $Y_i$'s are i.i.d. as uniform over $\{0, 1\}$. In particular, for all $i \in [-\alpha, \alpha]$, we have $\mathbb{P}(\mathcal{B}_\alpha = i) = 2^{-2\alpha} \binom{2\alpha}{\alpha+i}$. Note that $\mathcal{B}_\alpha$ has mean 0 and standard deviation $\sigma \triangleq \sqrt{\frac{\alpha}{2}}$.
**Coding Background.** To simplify the discussion, we assume that $q$ is a prime number implying that $\mathbb{Z}_q$ has the structure of a finite field. A linear code $\mathcal{C}$ of length $n$ and dimension $k$ is a subspace of $\mathbb{Z}_q^n$ of dimension $k$. We say that $\mathcal{C}$ is an $[n, k]_q$-code and its rate is $R \triangleq \frac{k}{n}$. A generator matrix $\mathbf{G}$ for $\mathcal{C}$ is a full rank matrix in $\mathbb{Z}_q^{n \times k}$ such that $\mathcal{C} = \{\mathbf{G}\mathbf{u} : \mathbf{u} \in \mathbb{Z}_q^k\}$, and a parity-check matrix $\mathbf{H}$ for $\mathcal{C}$ is a full rank matrix in $\mathbb{Z}_q^{(n-k) \times n}$ such that $\mathcal{C} = \{\mathbf{c} \in \mathbb{Z}_q^n : \mathbf{H}\mathbf{c} = \mathbf{0}\}$.

**Definition 2.4 (Dual Code).** Let $\mathcal{C}$ be an $[n, k]_q$-code. The dual code $\mathcal{C}^{\perp}$ of $\mathcal{C}$ is defined as the following $[n, n-k]_q$-code:

$$ \mathcal{C}^{\perp} \triangleq \{\mathbf{h} \in \mathbb{Z}_q^n : \forall \mathbf{c} \in \mathcal{C}, \langle \mathbf{c}, \mathbf{h} \rangle = 0\} \quad (2.2) $$

**Lattice Background.** A lattice $\Lambda$ is a discrete subgroup of $\mathbb{R}^d$. In particular, for a matrix $\mathbf{B} \in \mathbb{R}^{d \times d}$, the lattice $\Lambda(\mathbf{B})$ is defined as:

$$ \Lambda(\mathbf{B}) \triangleq \{\mathbf{B}\mathbf{x} : \mathbf{x} \in \mathbb{Z}^d\} \quad (2.3) $$

The matrix $\mathbf{B}$ is called a basis if it has full column rank.

The volume of a full-rank lattice $\Lambda \subset \mathbb{R}^d$ is the Euclidean volume of its fundamental Voronoï region $\text{Vor}(\Lambda) \triangleq \{\mathbf{v} \in \mathbb{R}^d : \|\mathbf{v}\| \le \|\mathbf{v} - \mathbf{x}\|, \forall \mathbf{x} \in \Lambda\}$. For a full-rank lattice $\Lambda(\mathbf{B})$, it is the volume of the fundamental $d$-dimensional parallelepiped defined by the column vectors of $\mathbf{B}$ (or any other basis of $\Lambda$). It is also the determinant of the matrix $\mathbf{B}$:

$$ \text{Vol}(\Lambda(\mathbf{B})) \triangleq \text{Vol}(\text{Vor}(\Lambda(\mathbf{B}))) = \det(\mathbf{B}) \quad (2.4) $$

The dual $\Lambda^{\vee}$ of a lattice $\Lambda$ is defined as

**Definition 2.5 (Dual Lattice).** The dual $\Lambda^{\vee}$ of a lattice $\Lambda \subset \mathbb{R}^d$ is

$$ \Lambda^{\vee} \triangleq \{\mathbf{x} \in \text{span}(\Lambda) : \forall \mathbf{y} \in \Lambda, \langle \mathbf{x}, \mathbf{y} \rangle \in \mathbb{Z}\}. \quad (2.5) $$

We can construct a lattice from a linear code through Construction A:

**Definition 2.6 (Construction A).** Let $\mathcal{C}$ be an $[n, k]_q$-code. The lattice $\Lambda$ obtained by Construction A applied to $\mathcal{C}$ is given by

$$ \Lambda(\mathcal{C}) \triangleq \{\mathbf{x} \in \mathbb{R}^n : \mathbf{x} \equiv \mathbf{c} \mod q, \mathbf{c} \in \mathcal{C}\}. \quad (2.6) $$

Note that if $\mathcal{C}$ is defined by a systematic generator matrix $\mathbf{G} \triangleq \begin{bmatrix} \mathbf{I}_{d_k} \\ \mathbf{A} \end{bmatrix} \in \mathbb{Z}_q^{n \times k}$, then the lattice $\Lambda(\mathcal{C})$ that is obtained through Construction A is also the lattice $\Lambda(\mathbf{B})$ generated by

$$ \mathbf{B} \triangleq \begin{bmatrix} \mathbf{I}_{d_k} & \mathbf{0} \\ \mathbf{A} & q\mathbf{I}_{d_{n-k}} \end{bmatrix}. \quad (2.7) $$

Clearly finding the closest point in Euclidean distance to some $\mathbf{y} \in \mathbb{Z}_q^n$ in $\mathcal{C}$ also amounts to find the closest lattice point in $\Lambda(\mathcal{C})$ of $\mathbf{y}$. The algorithm for performing this task when $\mathbf{y}$ belongs to $\mathbb{R}^n$ is known as a mean-squared-error (MSE) quantizer for $\Lambda(\mathcal{C})$. To analyze its performance, first notice that the fundamental Voronoï region $V$ of a lattice $\Lambda(\mathcal{C})$ associated to code $\mathcal{C}$ of dimension $k$ over $\mathbb{Z}_q^n$ has volume $\text{Vol}(V) \triangleq \text{Vol}(\Lambda(\mathcal{C})) = q^{n-k}$ [CS88]. The average decoding distance $\omega$ provided by the mean-square quantizer for $\Lambda$ can be assessed by the normalized second moment $G \triangleq G(\Lambda(\mathcal{C}))$, which is defined as

$$ G \triangleq \frac{1}{n \cdot \text{Vol}(V)^{\frac{2}{n}}} \int_V \frac{\|\mathbf{v}\|^2}{\text{Vol}(V)} d\mathbf{v}. \quad (2.8) $$
It is known that

$$G \geq \frac{1}{2\pi e} \qquad (2.9)$$

and is achieved asymptotically for lattices generated by Construction A from $q$-ary random codes when $q$ gets big [ZF96]. The case where the equality is achieved in Equation (2.9) really corresponds to the case when the equality

$$|C| \cdot \mathrm{Vol}(\mathrm{Ball}_{\omega}^{n}) = q^{n} \qquad (2.10)$$

is met, i.e. when the average decoding distance is

$$\omega \triangleq \sqrt{\int_V \frac{\|\mathbf{v}\|^2}{\mathrm{Vol}(V)} d\mathbf{v}} = \sqrt{\frac{n}{2\pi e}} \cdot q^{1-\frac{k}{n}} + o(1). \qquad (2.11)$$

It corresponds therefore to the lattice analogue of the Gilbert-Varshamov distance.

**Short Vector Sampler.** Dual attacks heavily depend on lattice reduction algorithms, such as BKZ, to find short vectors in a lattice or its dual. Our improvements in this paper do not address these algorithms. Instead, we will use Algorithm 2.1 to obtain short vectors and refer the reader to [GJ21,MAT22] for implementation details.

**Algorithm 2.1 Short Vectors Sampling Procedure [GJ21]**

**Input:** A basis $\mathbf{B} = [\mathbf{b}_0 \dots \mathbf{b}_{d-1}]$ for a lattice and $2 \leq \beta_{bkz}, \beta_{sieve} \in \mathbb{Z} \leq d$.

**Output:** A list of $N_{sieve}(\beta_{sieve}) \triangleq (\sqrt{\frac{4}{3}})^{\beta_{sieve}}$ vectors from the lattice.

1: Randomize the basis $\mathbf{B}$.

2: Run BKZ-$\beta_{bkz}$ to obtain a reduced basis $\mathbf{b}'_0, \dots, \mathbf{b}'_{d-1}$.

3: Run a sieve in dimension $\beta_{sieve}$ on the sublattice spanned by $\mathbf{b}'_0, \dots, \mathbf{b}'_{\beta_{sieve}-1}$ to obtain a list $L$ of $N_{sieve}(\beta_{sieve})$ vectors.

4: **return** $L$

The parameter $\beta_{bkz}$ controls the block size in the BKZ algorithm, with an exponential cost in $\beta_{bkz}$. The sieving algorithm outputs $N_{sieve}(\beta_{sieve})$ short vectors in the lattice and its complexity also scales exponentially with $\beta_{sieve}$. The magnitude $N_{sieve}(\beta_{sieve})$ also grows exponentially with $\beta_{sieve}$ but slower than the cost of sieving. We will write $T_{BKZ}(d, \beta_{bkz})$ for the cost of running BKZ-$\beta_{bkz}$ in dimension $d$ and $T_{sieve}(\beta_{sieve})$ for the cost of sieving in dimension $\beta_{sieve}$. One possible instantiation of the lattice sieve algorithm is [BDGL16] which has a cost of $2^{0.292 \beta_{sieve}+o(\beta_{sieve})}$. Thus, according to the best known algorithms we have $T_{BKZ}(d, \beta_{bkz}) \in \mathrm{poly}(d) \cdot 2^{\Theta(\beta_{bkz})}$ and $T_{sieve}(\beta_{sieve}) \in 2^{\Theta(\beta_{sieve})}$. More specifically, we take these complexities from [MAT22, Lemma 4.1, Assumption 7.3].

**Lemma 2.7 (Short Vectors Sampling Complexity).** Let $\mathbf{B}$ be a basis of a $d$-dimensional lattice. Then, the running time $T_{\mathrm{sample}}$ of Algorithm 2.1 to output $N_{\mathrm{sieve}}(\beta_{\mathrm{sieve}})$ short vectors is

$$T_{\mathrm{sample}}(d, \beta_{\mathrm{bkz}}, \beta_{\mathrm{sieve}}) = T_{\mathrm{BKZ}}(d, \beta_{\mathrm{bkz}}) + T_{\mathrm{sieve}}(\beta_{\mathrm{sieve}}) \qquad (2.12)$$

where

▷ $T_{\mathrm{BKZ}}(d, \beta_{\mathrm{bkz}}) = C_{\mathrm{prog}}^2 \cdot (d - \beta_{\mathrm{bkz}} + 1) \cdot T_{\mathrm{NNS}}(\beta_{\mathrm{bkz}}^{\mathrm{eff}})$,

▷ $T_{\mathrm{sieve}}(\beta_{\mathrm{sieve}}) = C_{\mathrm{prog}} \cdot T_{\mathrm{NNS}}(\beta_{\mathrm{sieve}})$,

▷ $N_{\mathrm{sieve}}(\beta) = (\sqrt{\frac{4}{3}})^{\beta}$ is the expected number of sieve results,

▷ $T_{\mathrm{NNS}}(\beta)$ is the time complexity for finding all close pairs in dimension $\beta$ (see [AGPS20a] with improvement of MATZOV [MAT22, Section 6]),

▷ $C_{\mathrm{prog}} = 1/(1 - 2^{-0.292})$ is the number of close pairs search to run,

▷ and $\beta^{\mathrm{eff}}$ is the optimal sieve dimension to use for solving the Shortest Vector Problem (SVP) for lattices in dimension $\beta$.

Note that in [Duc18], it is estimated that $\beta^{\mathrm{eff}} = \beta - \frac{\beta \log(4/3)}{\log(\beta/(2\pi e))}$.
The lengths of the short vectors produced by Algorithm 2.1. Assuming that the Gaussian Heuristic (GH) and the Geometric Series Assumption<fnref n="6" /> (GSA) [Sch03] hold for a d-dimensional lattice, applying BKZ-$\beta$ to it produces vectors $\mathbf{x}$ of average length [Che13]:

$$ \|\mathbf{x}\| \approx \delta(\beta)^d \cdot \mathrm{Vol}(\Lambda)^{\frac{1}{d}}, \qquad (2.13) $$

where $\delta(\beta) = \left(\frac{\beta}{2\pi e} (\pi\beta)^{\frac{1}{\beta}}\right)^{\frac{1}{2(\beta-1)}}$ is the root-Hermite factor<fnref n="7" />. With these assumptions, the expected length of the returned short vectors is given by:

**Lemma 2.8 (Length of the sampled short vectors [MAT22, Lemma 4.2]).** Let $\Lambda$ be a d-dimensional lattice. Then, Algorithm 2.1 outputs at least $N$ vectors of expected length $\ell$ given by

$$ \ell \triangleq \mathrm{Vol}(\Lambda)^{1/d} \cdot \sqrt{\frac{4}{3}} \cdot \delta(\beta_{\mathrm{sieve}})^{\beta_{\mathrm{sieve}}-1} \cdot \delta(\beta_{\mathrm{bkz}})^{d-\beta_{\mathrm{sieve}}}. \qquad (2.14) $$

In our attack, we select $\beta_{\mathrm{bkz}}$ and $\beta_{\mathrm{sieve}}$ such that $T_{\mathrm{BKZ}}(d, \beta_{\mathrm{bkz}}) = T_{\mathrm{sieve}}(\beta_{\mathrm{sieve}})$. Under the same GH and GSA assumptions, we derive the following lemma:

**Lemma 2.9.** The short vectors produced by Algorithm 2.1 are in a sublattice $\Lambda'$ of dimension $\beta_{\mathrm{sieve}}$ and expected volume

$$ \mathrm{Vol}(\Lambda') = \left( \mathrm{Vol}(\Lambda)^{\frac{1}{d}} \cdot \delta(\beta_{\mathrm{bkz}})^{d-\beta_{\mathrm{sieve}}} \right)^{\beta_{\mathrm{sieve}}}. \qquad (2.15) $$

**Fast Fourier Transform.** Dual lattice attacks widely use discrete Fourier transforms:

**Definition 2.10 (Discrete Fourier Transform).** The discrete Fourier transform $\hat{f}$ of a function $f: \mathbb{Z}_q^n \to \mathbb{C}$ is defined as

$$ \hat{f}(\mathbf{x}) = \sum_{\mathbf{a} \in \mathbb{Z}_q^n} f(\mathbf{a}) e^{-\frac{2i\pi}{q} \langle \mathbf{x}, \mathbf{a} \rangle}. \qquad (2.16) $$

The effectiveness of our dual attacks is heavily dependent on the speed at which we can compute discrete Fourier transforms. In [MAT22, Ass. 7.4], it is estimated that a Fast Fourier Transform (FFT) over $\mathbb{Z}_q^n$ requires $n \cdot q^{n+1}$ multiplications. Note that this is clearly suboptimal for large prime $q$'s: while this is not a problem in [MAT22] as $q$ is reduced thanks to modulus switching, here, we drop modulus switching resulting in $q$ being big and imposed by the original LWE instance (i.e. $q = 3329$ for KYBER). This motivates us to give the following finer estimation for the cost of an FFT over $\mathbb{Z}_{3329}^n$.

**Proposition 2.11 (Complexity of the FFT).** Let $q = 3329$. There exists an FFT over $\mathbb{Z}_q$ with complexity given by:

$$ N_{\mathrm{FFT}}^{(\mathrm{add})} = 240500 \quad \text{and} \quad N_{\mathrm{FFT}}^{(\mathrm{mul})} = 115928, \qquad (2.17) $$

the number of additions and multiplications, respectively.

By using the algorithm in [DM90, §2.3.2] that reduces the calculation of an FFT over $\mathbb{Z}_q^n$ to FFT's over $\mathbb{Z}_q$, we deduce that the total cost to perform a discrete Fourier transform over $\mathbb{Z}_q^n$ is

$$ n q^{n-1} N_{\mathrm{FFT}}^{(\mathrm{add})} \quad \text{and} \quad n q^{n-1} N_{\mathrm{FFT}}^{(\mathrm{mul})} \qquad (2.18) $$

additions and multiplications, respectively. Finally, by supposing as in [MAT22, Ass. 7.4] that the cost of an addition and a multiplication are

$$ C_{\mathrm{add}} = 160 \quad \text{and} \quad C_{\mathrm{mul}} = 1024, \qquad (2.19) $$

respectively, the total cost of an FFT over $\mathbb{Z}_q^n$ is

$$ C_{\mathrm{FFT}} = C_{\mathrm{add}} n q^{n-1} N_{\mathrm{FFT}}^{(\mathrm{add})} + C_{\mathrm{mul}} n q^{n-1} N_{\mathrm{FFT}}^{(\mathrm{mul})}. \qquad (2.20) $$

<footnote n="6">⁶ The GSA may lead us to underestimate the final complexity of a few bits (see [DP23b, Appendix A.3]).</footnote>

<footnote n="7">⁷ Experiments in [AD221] show that these assumptions hold for $d > \beta$ and $\beta \to \infty$ and in particular, it hold with good accuracy for $\beta > 50$.</footnote>
We now give details on the procedures `SET_OF_SHORT_LATTICE_VECTORS`, `LWE_SAMPLES`, `SOLVE_LWE_WITH_FFT` and `SUB_LWE_SOLVER`.

**The Lattice Reduction Function SET_OF_SHORT_LATTICE_VECTORS.** This function outputs a set $\mathcal{S}$ of pairs of short vectors $(\mathbf{x}, \mathbf{y})$ obtained by performing the short vectors sampler Algorithm 2.1 with the appropriate choice of parameters on the lattice $\Lambda(\mathbf{B})$ where the lattice basis $\mathbf{B} \in \mathbb{R}^{(m+n_{\text{lat}}) \times (m+n_{\text{lat}})}$ is given by Construction A:

$$ \mathbf{B} \triangleq \left[ \begin{array}{c|c} \mathbf{Id}_m & \mathbf{0} \\ \hline \mathbf{A}_{\text{lat}}^{\top} & q\mathbf{Id}_{n_{\text{lat}}} \end{array} \right]. \qquad (3.1) $$

This gives pairs $(\mathbf{x}, \mathbf{y}) \in \mathbb{Z}^m \times \mathbb{Z}^{n_{\text{lat}}}$ for which both $\mathbf{x}$ and $\mathbf{y}$ are short and satisfy $\mathbf{y} = \mathbf{A}_{\text{lat}}^{\top}\mathbf{x} \bmod q$. For the rest of this paper we denote by $N$ the expected size of $\mathcal{S}$. From Lemma 2.7, we have **Notation 3.1**.

$$ N \triangleq N_{\text{sieve}} (\beta_{\text{sieve}}) \triangleq \left(\sqrt{\frac{4}{3}}\right)^{\beta_{\text{sieve}}}. \qquad (3.2) $$

**Producing New LWE Samples with LWE_SAMPLES.** Each pair $(\mathbf{x}, \mathbf{y})$ of short vectors in $\mathcal{S}$ yields one LWE sample by decoding $\mathbf{A}_{\text{fft}}^{\top}\mathbf{x}$ in the code $C_{\text{lsc}}$ generated by $\mathbf{G}$. This yields an output $\mathbf{u}_{\text{lsc}} \in \mathbb{Z}_q^{k_{\text{fft}}}$ such that $\mathbf{e}_{\text{lsc}} \triangleq \mathbf{A}_{\text{fft}}^{\top}\mathbf{x} - \mathbf{G}\mathbf{u}_{\text{lsc}}$ is of small norm, say close to some $d_{\text{lsc}}$. The new LWE sample is given by the pair $(\mathbf{u}_{\text{lsc}}, \langle \mathbf{x}, \mathbf{b} \rangle)$. It is readily seen that, when $\mathbf{s}_{\text{enu}} = \mathbf{0}$ we have

$$ \langle \mathbf{x}, \mathbf{b} \rangle = \langle \mathbf{u}_{\text{lsc}}, \mathbf{G}^{\top} \mathbf{s}_{\text{fft}} \rangle + \langle \mathbf{x}, \mathbf{e} \rangle + \langle \mathbf{y}, \mathbf{s}_{\text{lat}} \rangle + \langle \mathbf{e}_{\text{lsc}}, \mathbf{s}_{\text{fft}} \rangle \qquad (3.3) $$

which corresponds to an LWE sample with secret $\mathbf{G}^{\top}\mathbf{s}_{\text{fft}}$ and noise $e' = \langle \mathbf{x}, \mathbf{e} \rangle + \langle \mathbf{y}, \mathbf{s}_{\text{lat}} \rangle + \langle \mathbf{e}_{\text{lsc}}, \mathbf{s}_{\text{fft}} \rangle$. All these samples $(\mathbf{u}_{\text{lsc}}, \langle \mathbf{x}, \mathbf{b} \rangle)$ are then put in a list $\mathcal{L}$ which is the output of `LWE_SAMPLES`.

**Solving the Induced LWE Instance with SOLVE_LWE_WITH_FFT.** This procedure outputs a real number $V$ which indicates to us how noisy the aforementioned LWE samples are. This is done by searching exhaustively for the solution $\mathbf{G}^{\top}\mathbf{s}_{\text{fft}}$ by computing the score function for all $\mathbf{z} \in \mathbb{Z}_q^{k_{\text{fft}}}$:

$$ F_0^{(\text{lsc})}(\mathbf{z}) \triangleq \sum_{(\mathbf{u}_{\text{lsc}}, \mathbf{b}) \in \mathcal{L}} \cos \left( \frac{2\pi}{q} (\mathbf{b} - \langle \mathbf{u}_{\text{lsc}}, \mathbf{z} \rangle) \right), \qquad (3.4) $$

and returning its maximum value, $V = \max_{\mathbf{z} \in \mathbb{Z}_q^{k_{\text{fft}}}} F_0^{(\text{lsc})}(\mathbf{z})$. If $\mathbf{s}_{\text{enu}} = \mathbf{0}$ we expect that this maximum value is achieved for $\mathbf{z} = \mathbf{G}^{\top}\mathbf{s}_{\text{fft}}$. The score function is efficiently computed with an FFT as follows. First we compute a function $f_0^{(\text{lsc})}$ defined for $\mathbf{a} \in \mathbb{Z}_q^{k_{\text{fft}}}$ as

$$ f_0^{(\text{lsc})}(\mathbf{a}) \triangleq \sum_{(\mathbf{a}, \mathbf{b}) : (\mathbf{a}, \mathbf{b}) \in \mathcal{L}} e^{\frac{2i\pi}{q} \mathbf{b}}, \qquad (3.5) $$

then we compute the FFT of $f_0^{(\text{lsc})}$ and take its real part. It is readily seen that

$$ F_0^{(\text{lsc})} = \Re \left( \widehat{f_0^{(\text{lsc})}} \right). \qquad (3.6) $$

**Recovering the Rest of the Secret with SUB_LWE_SOLVER.** At this point, we expect that, under the condition that our parameters are well-chosen, if $V \ge T$ (here $T$ will be chosen around the expected value of $F_0^{(\text{lsc})}(\mathbf{G}^{\top}\mathbf{s}_{\text{fft}})$ when $\mathbf{s}_{\text{enu}} = \mathbf{0}$) then with overwhelming probability, $\mathbf{s}_{\text{enu}} = \mathbf{0}$. In other words, we recovered $n_{\text{enu}}$ positions of the secret from the original LWE problem $(\mathbf{A}, \mathbf{b})$ of dimension $m \times n$. Note that when $\mathbf{s}_{\text{enu}} = \mathbf{0}$ we can write

$$ \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e} = \left[ \mathbf{A}_{\text{fft}} \quad \mathbf{A}_{\text{lat}} \right] \left( \frac{\mathbf{s}_{\text{fft}}}{\mathbf{s}_{\text{lat}}} \right) + \mathbf{e}. \qquad (3.7) $$
As such, if indeed $s_{enu} = 0$, we can recover $s_{fft}$ and $s_{lat}$ by solving the new LWE problem given by ($[A_{fft}, A_{lat}]$, $b$), which has strictly smaller dimension $m \times (n - n_{enu})$. We don't specify a particular algorithm for the SUB\_LWE\_SOLVER routine, since it will be called at most once, and solving an LWE instance with smaller dimension and with error distribution $\mathcal{B}_{\alpha}$ has complexity negligible compared to the other computations in Algorithm 3.1.

## 3.2 Correctness of the Algorithm

The following lemma provides the conditions on the parameters for Algorithm 3.1 to succeed.

**Lemma 3.2 (Correctness).** Suppose $(\mathbf{A}, b)$ is sampled from an LWE $(q, n, m, \mathcal{B}_{\alpha}, \mathcal{B}_{\alpha})$ oracle, and SUB\_LWE\_SOLVER returns $s_{fft}$ and $s_{lat}$ with probability $1 - \mu$ when the bet $s_{enu} = 0$ is valid and the secret meets the threshold, namely $F_0^{(\text{lsc})}(\mathbf{G}^{\top}s_{fft}) \ge T$. The probability that our algorithm succeeds in recovering the secret $\mathbf{s}$, is lower bounded by

$$P_{\text{success}} \triangleq \eta \cdot P_{\text{good}} \cdot (1 - \mu) - \varepsilon \quad (3.8)$$

where

$$\varepsilon \triangleq R \cdot q^{k_{fft}} \cdot P_{\text{wrong}}, \quad (3.9)$$

$$\eta \triangleq \left( 1 - \sum_{t=0}^{n_{enu}+n_{fft}} \left( 1 - \frac{\binom{t}{n_{enu}}}{\binom{n_{enu}+n_{fft}}{n_{enu}}} \right)^R \binom{n_{enu}+n_{fft}}{t} p_0^t (1-p_0)^{n_{enu}+n_{fft}-t} \right), \quad (3.10)$$

$$P_{\text{good}} \triangleq \mathbb{P} \left( F_0^{(\text{lsc})} (\mathbf{G}^{\top} \mathbf{s}_{fft}) \ge T \mid \mathbf{s}_{enu} = \mathbf{0} \right), \quad (3.11)$$

$$P_{\text{wrong}} \triangleq \mathbb{P} \left( F_0^{(\text{lsc})} (\mathbf{z}) \ge T \mid \mathbf{s}_{enu} \neq \mathbf{0} \right), \quad (3.12)$$

$$p_0 \triangleq \mathbb{P}(\mathcal{B}_{\alpha} = 0) = 2^{-2\alpha} \binom{2\alpha}{\alpha} \quad (3.13)$$

and where $\mathbf{z}$ is taken uniformly at random in $\mathbb{Z}_q^{k_{fft}}$. We will use Approximations 4.8 and 4.9 to estimate $P_{\text{good}}$ and $P_{\text{wrong}}$, respectively.

*Proof.* For $i \in [1, R]$, let us denote the following events for each iteration $i$:

- $A_i$: $s_{enu} = 0$;

- $B_i$: $F_0^{(\text{lsc})}(\mathbf{G}^{\top}\mathbf{s}_{fft}) \ge T$;

- $C_i$: "sub-LWE finds the secret";

- $D_i$: $\exists \mathbf{z} \in \mathbb{Z}_q^{k_{fft}}, F_0^{(\text{lsc})}(\mathbf{z}) \ge T$;

Using the union bound on the probability that the algorithm fails and taking the complement of this event yields that the probability that our algorithm succeeds is lower bounded by

$$\mathbb{P} \left( \left( \bigcup_i (A_i \cap B_i \cap C_i) \right) \cap \left( \bigcap_i (A_i \cup \overline{D_i}) \right) \right) \ge \mathbb{P} \left( \bigcup_i (A_i \cap B_i \cap C_i) \right) - \mathbb{P} \left( \bigcup_i (\overline{A_i} \cap D_i) \right)$$

Next, applying the union bound again and considering that we run $R$ iterations, we can upper bound $\mathbb{P}(\bigcup_i (\overline{A_i} \cap D_i))$ by $Rq^{k_{fft}}P_{\text{wrong}}$, which gives the $-\varepsilon$ term in the inequality stated in the lemma. On the other hand, it is straightforward to lower bound the first term:
$$
\begin{align*}
\mathbb{P}\left(\bigcup_i (A_i \cap B_i \cap C_i)\right) &= \mathbb{P}\left(\bigcup_i (A_i \cap B_i \cap C_i) \mid \bigcup_i A_i\right) \cdot \mathbb{P}\left(\bigcup_i A_i\right) \\
&\geq \mathbb{P}\left(B_{i_0} \cap C_{i_0} \mid A_{i_0}\right) \cdot \mathbb{P}\left(\bigcup_i A_i\right) \\
&= \mathbb{P}\left(C_{i_0} \mid A_{i_0}, B_{i_0}\right) \cdot \mathbb{P}\left(B_{i_0} \mid A_{i_0}\right) \cdot \mathbb{P}\left(\bigcup_i A_i\right) \\
&= (1 - \mu) \cdot P_{\text{good}} \cdot \mathbb{P}\left(\bigcup_i A_i\right)
\end{align*}
$$

Let $n_0$ denote the number of zeros in $s_{\llbracket 1,n \rrbracket} \setminus I_{\text{lat}}$. Then, we have

$$
\begin{align*}
\mathbb{P}\left(\bigcup_i A_i\right) &= 1 - \mathbb{P}\left(\bigcap_i \overline{A_i}\right) \\
&= 1 - \sum_{t=0}^{n_{\text{enu}}+n_{\text{fft}}} \mathbb{P}\left(\bigcap_i \overline{A_i} \mid n_0 = t\right) \cdot \mathbb{P}(n_0 = t) \\
&= 1 - \sum_{t=0}^{n_{\text{enu}}+n_{\text{fft}}} \left(1 - \frac{\binom{t}{n_{\text{enu}}} \binom{n}{n_{\text{enu}}}}{\binom{n}{n_{\text{enu}}}}\right) \cdot \mathbb{P}(n_0 = t)
\end{align*}
$$

Clearly, $n_0$ follows a binomial distribution with parameter $n_{\text{enu}} + n_{\text{fft}}$ and $p_0$. This concludes the proof. □

Note that Lemma 3.2 does not impose any constraints on $N$ and $T$. However, we must choose them carefully. First, if $R \cdot q^{k_{\text{fft}}} \cdot P_{\text{wrong}} \ge 1$ or if $P_{\text{good}}$ is too small, then the lower bound we obtain for the probability of success of our dual attack is 0, which means we cannot actually guarantee a success. This is why, in Section 5, we select $N$ and $T$ that ensure a high probability of success. In particular, we set $\eta \ge 0.62$ and $\varepsilon$ close to 0 (see Appendix C.2), ensuring a success probability of at least $0.3(1 - \mu)$. Furthermore, it is worth noting that the condition “$R \cdot q^{k_{\text{fft}}} \cdot P_{\text{wrong}}$ is much smaller than 1” resolves the indistinguishability issue raised in [DP23b].

## 3.3 Which Codes Should We Use?

In Algorithm 3.1, one could ask: which code should we use for $C_{\text{sc}}$? In terms of the decoding distance alone, the answer would be, just use a random code of dimension $k_{\text{fft}}$ in $\mathbb{Z}_q^{n_{\text{enu}}}$. In this case, we would obtain the decoding distance $d \approx q^{1-\frac{k_{\text{fft}}}{n_{\text{fft}}}} \sqrt{\frac{n_{\text{fft}}}{2\pi e}}$ (see Equation (2.11)) attaining the bound (2.9) or (2.10). However, the decoding algorithm we could use in this case would be too complex for our purpose. We could instead use a product code structure as in [BDGL16]. Contrarily to what happens in the latter case, where spherical codes can be used, we are in a situation where more structured codes could do the job better. A natural answer is given here by polar codes.

The generator matrix of such a code in length $n$ which is a power of 2 and an arbitrary code dimension $k$ is obtained as follows. We define a generator matrix $\mathbf{G}$ for our code as $\mathbf{G} \triangleq \mathbf{K}_1 \otimes \cdots \otimes \mathbf{K}_{\log_2(n)} \cdot \mathbf{F}$ where $\otimes$ stands for the Kronecker product, $\mathbf{K}_i \triangleq \begin{bmatrix} 1 & 1 \\ \alpha_i & 0 \end{bmatrix}$ and $\alpha_i$'s are some invertible elements chosen uniformly at random in $\mathbb{Z}_q^*$. The matrix $\mathbf{F} \in \mathbb{Z}_q^{n \times k}$ is an expansion matrix such that for all $\mathbf{m} \in \mathbb{Z}_q^k$, $\mathbf{F}\mathbf{m}$ is exactly $\mathbf{m}$ on $k$ positions and 0 on the others (that are the frozen positions). Since the code length we need is not necessarily a power of 2, we adjust it by puncturing the code (i.e. we remove as many rows of the generator matrix as needed).

Furthermore, the Successive Cancellation (SC) decoder which is classically used to decode polar codes in the error correction scenario can be turned with a simple modification into an algorithm for finding a close codeword (but not necessarily the closest one) [KU10]. This is precisely
what is needed in our context. It needs a noise model to instantiate it, and this can be done for our Euclidean metric by using the Gaussian noise model. To get even closer to the optimal decoding distance, we have improved the decoding process: firstly we turn the SC algorithm into a probabilistic decoder, then we call it several times to get a list of codeword candidates and choose the closest one from this list (see Appendix A to get more details about our list decoder). This procedure induces a new small constant factor L in the whole complexity which is the size of the decoding list; but in return this additional cost allows us to achieve a better decoding distance. The complexity for decoding is given by:

**Lemma 3.3 (Decoding polar codes).** List decoding an $[n_{\text{fft}}, k_{\text{fft}}]_q$ polar code by using L probabilistic SC decoders can be done with time complexity of order

$$T_{\text{dec}}(q, n_{\text{fft}}, k_{\text{fft}}) = 3 \cdot L \cdot \left( C_{\text{mul}} \cdot N_{\text{FFT}}^{(\text{mul})}(q) + C_{\text{add}} \cdot N_{\text{FFT}}^{(\text{add})}(q) \right) \cdot n'_{\text{fft}} \log_2(n'_{\text{fft}}) \quad (3.14)$$

where $n'_{\text{fft}}$ is the smallest power of 2 greater than $n_{\text{fft}}$ and $N_{\text{FFT}}^{(\text{mul})}(q)$ is the number of multiplications we need to achieve a discrete Fourier transform over $\mathbb{Z}_q$.

The proof of this lemma directly follows from Lemma A.4.

By using similar arguments as in [KU10], it can be proven that for $n_{\text{fft}}$ tending to infinity and constant $\frac{k_{\text{fft}}}{n_{\text{fft}}}$, the average distance achieved by our decoder is

$$d_{\text{lsc}} = \sqrt{\frac{n_{\text{fft}}}{2\pi e}} \cdot q^{1-\frac{k_{\text{fft}}}{n_{\text{fft}}}} \cdot (1 + o(1)) \quad (3.15)$$

This result is essentially due to the polarization phenomenon (see Appendix A). However, Equation (3.15) is not precise enough to accurately estimate the full complexity of our dual attack due to the $o(1)$ term. For this reason, we provide a C implementation<fnref n="9" /> and present experimental results demonstrating that polar codes are perfectly suited to our case. The experiments we conducted use the exact codes required for our dual attacks, and our optimization suggests choosing $L = 1$. To justify the use of polar codes in this context, we verified that the total complexity of our dual attack closely matches the ideal scenario, where decoding at the distance $d_{\text{lsc}} \triangleq \sqrt{\frac{n_{\text{fft}}}{2\pi e}} \cdot q^{1-\frac{k_{\text{fft}}}{n_{\text{fft}}}}$ would incur the same cost as using polar codes.

# 4 Analysis of our Dual Attack

## 4.1 Complexity of our Dual Attack

A general formula for the complexity of our algorithm using polar codes for $C_{\text{lsc}}$ is given by the following theorem:

**Theorem 4.1 (Complexity of Algorithm 3.1).** Using the same notations as in the correctness Lemma 3.2 and by supposing that the cost of one call to SUB\_LWE\_SOLVER is negligible, the average time complexity of Algorithm 3.1 is upper bounded by

$$T_{\text{sample}} + R \cdot (N \cdot T_{\text{dec}} + T_{\text{FFT}}) \quad (4.1)$$

where

▷ $T_{\text{sample}} \triangleq T_{\text{sample}}(m + n_{\text{lat}}, \beta_{\text{bkz}}, \beta_{\text{sieve}})$ is the cost to produce $N = N_{\text{sieve}}(\beta_{\text{sieve}})$ short vectors in $\Lambda(\mathbf{B})$. This cost is given by Lemma 2.7;

▷ $T_{\text{dec}} \triangleq T_{\text{dec}}(q, n_{\text{fft}}, k_{\text{fft}})$ is the cost for decoding a random vector in $\mathbb{Z}_q^{n_{\text{fft}}}$ in $C_{\text{lsc}}$ generated by $\mathbf{G}$. This cost is given by Lemma 3.3;

▷ $T_{\text{FFT}}$ is the cost of an FFT over $\mathbb{Z}_q^{k_{\text{fft}}}$ and is given by Proposition 2.11;

<footnote n="9">⁹ https://github.com/kevin-carrier/CodedDualAttack/tree/main/PolarCodeOverZq</footnote>
## 4.2 Computing an Accurate Approximation of $P_{\text{good}}$ and $P_{\text{wrong}}$

In this subsection, we provide an accurate estimation of the probabilities $P_{\text{good}}$ and $P_{\text{wrong}}$ that appear in Theorem 4.1. First, let's recall the expression of the score function:

$$F_{\tilde{\mathbf{s}}_{\text{lsc}}}^{(\text{lsc})} (\mathbf{G}^{\top} \tilde{\mathbf{s}}_{\text{lsc}}) \triangleq \sum_{(\mathbf{x}, \mathbf{y}) \in \mathcal{S}} \cos \left( \frac{2\pi}{q} \left( \langle \mathbf{x}, \mathbf{b} - \mathbf{A}_{\text{lsc}} \tilde{\mathbf{s}}_{\text{lsc}} \rangle - \langle \mathbf{u}_{\text{lsc}}, \mathbf{G}^{\top} \tilde{\mathbf{s}}_{\text{lsc}} \rangle \right) \right) \quad (4.2)$$

$$= \sum_{(\mathbf{x}, \mathbf{y}) \in \mathcal{S}} \cos \left( \frac{2\pi}{q} \left( \langle \mathbf{x}, \mathbf{b} - \mathbf{A}_{\text{lsc}} \tilde{\mathbf{s}}_{\text{lsc}} \rangle - \langle \mathbf{c}_{\text{lsc}}, \tilde{\mathbf{s}}_{\text{lsc}} \rangle \right) \right) \quad (4.3)$$

where $\mathcal{S}$ is a set of $N$ short vectors drawn from $\{(\mathbf{x}, \mathbf{y}) \in \Lambda(\mathbf{B}) : \|(\mathbf{x}, \mathbf{y})\| \le d_{\text{lat}}\}$. Here, $\mathbf{c}_{\text{lsc}} \triangleq \mathbf{G}\mathbf{u}_{\text{lsc}}$ is a codeword in $\mathcal{C}_{\text{lsc}} \subseteq \mathbb{Z}_q^{n_{\text{lsc}}}$, obtained by decoding $\mathbf{A}_{\text{lsc}}^{\top}\mathbf{x}$ using our polar code decoder. It is important to note that, according to Lemma 2.9, the short lattice vectors in $\mathcal{S}$ generated by Algorithm 2.1 are not uniformly distributed within $\Lambda(\mathbf{B}) \cap \text{Ball}_{d_{\text{lat}}}^{m+n_{\text{lat}}}$; instead, they belong to a $\beta_{\text{sieve}}$-dimensional sublattice $\Lambda(\mathbf{B}') \subseteq \Lambda(\mathbf{B})$, where $\mathbf{B}' \in \mathbb{R}^{(m+n_{\text{lat}}) \times \beta_{\text{sieve}}}$. More precisely, we make the following assumption regarding the distribution of vectors in $\mathcal{S}$:

**Assumption 4.2.** We assume that the set $\mathcal{S}$ consists of $N$ vectors uniformly sampled from

$$\{\mathbf{w} \in \Lambda(\mathbf{B}') : \|\mathbf{w}\| \le d_{\text{lat}}\},$$

where $\Lambda(\mathbf{B}')$ is a $\beta_{\text{sieve}}$-dimensional sublattice of $\Lambda(\mathbf{B})$ with basis $\mathbf{B}' \in \mathbb{R}^{(m+n_{\text{lat}}) \times \beta_{\text{sieve}}}$, and volume as stated in Lemma 2.9. The radius $d_{\text{lat}} \triangleq \frac{\ell(\beta_{\text{sieve}}+1)}{\beta_{\text{sieve}}}$ corresponds to that of a $\beta_{\text{sieve}}$-dimensional Euclidean ball, within which the average vector length $\ell$ is given in Lemma 2.8.

Additionally, we assume that the probability distribution of the output of our polar code decoder has radial symmetry. This means that the probability depends only on the distance between the returned codeword and the word to be decoded, not on the specific direction. Through experimentation, we observed that this distance closely follows a normal distribution. Based on these observations, we make the following assumption:

**Assumption 4.3.** Let $\mathbf{u}$ be any vector from $\mathbb{Z}_q^{n_{\text{lsc}}}$, and let $\text{Dec}(\mathbf{u})$ represent the random variable corresponding to the output of our polar code decoding algorithm. The distribution of $\|\mathbf{u} - \text{Dec}(\mathbf{u})\|$ does not depend on $\mathbf{u}$ and we assume that it can be smoothed and approximated by the normal distribution $N(\mu_{\text{lsc}}, \sigma_{\text{lsc}}^2)$, where $\mu_{\text{lsc}}$ is the mean and $\sigma_{\text{lsc}}$ is the standard deviation, both determined through simulations. We also assume that the conditional distribution of $\mathbf{u} - \text{Dec}(\mathbf{u})$ given that $\|\mathbf{u} - \text{Dec}(\mathbf{u})\| = d_{\text{lsc}}$ is uniform over $(\Lambda(\mathcal{C}_{\text{lsc}}) + \mathbf{u}) \cap \text{Sphere}_{d_{\text{lsc}}}^{n_{\text{lsc}}}$.

**First-Level Approximation of the Score Function.** The score function $F_{\tilde{\mathbf{s}}_{\text{lsc}}}^{(\text{lsc})} (\mathbf{G}^{\top} \tilde{\mathbf{s}}_{\text{lsc}})$, as recalled in Equation (4.3), is a random variable influenced by multiple sources of randomness:

(i) the randomness in the short vector sampling Algorithm 2.1 that generates $\mathcal{S}$,

(ii) the inherent randomness in the polar code decoder Dec,

(iii) the randomness in the LWE instance, particularly in the choice of the matrix $\mathbf{A}$,

(iv) the randomness of the guess $\tilde{\mathbf{s}}_{\text{lsc}}$, which primarily arises from the selection of $I_{\text{lsc}}$,

(v) the randomness of the guess $\tilde{\mathbf{s}}_{\text{lsc}}$.

We denote by $\mathbb{E}_{\mathcal{S}, \text{Dec}}(\cdot)$ the conditional expectation over the randomness sources (i) and (ii). Thus, a first-level approximation of the score function is:

**Approximation 4.4 (First-Level Approximation).** The score function $F_{\tilde{\mathbf{s}}_{\text{lsc}}}^{(\text{lsc})} (\mathbf{G}^{\top} \tilde{\mathbf{s}}_{\text{lsc}})$ can be approximated by its conditional expectation

$$\mathbb{E}_{\mathcal{S}, \text{Dec}} \left( F_{\tilde{\mathbf{s}}_{\text{lsc}}}^{(\text{lsc})} (\mathbf{G}^{\top} \tilde{\mathbf{s}}_{\text{lsc}}) \right) \quad (4.4)$$

where the expectation is taken over the randomness of the polar code decoder and the short vector sampler.
**Lemma 4.5.** The conditional expectation in Approximation 4.4 can be expressed as

$$ \mathbb{E}_{\mathcal{S}, \text{Dec}} \left( F_{\hat{\mathbf{s}}_{\text{enu}}}^{(\text{lsc})} (\mathbf{G}^{\top} \tilde{\mathbf{s}}_{\text{fft}}) \right) = \sum_{\substack{(\mathbf{w}_{\text{lat}}, \mathbf{w}_{\text{lsc}}^{\top}) \\ \in \Lambda(\mathbf{B}_{\text{global}}^{\text{tmp}})^{\vee} + \frac{(\mathbf{B}^{\top} \mathbf{r}_{\text{lat}} \cdot \mathbf{B}_{\text{lsc}}^{\top} \mathbf{r}_{\text{lsc}})}{q}}} \hat{f}_{\text{lat}}(\mathbf{w}_{\text{lat}}^{\vee}) \cdot \hat{f}_{\text{lsc}}(\mathbf{w}_{\text{lsc}}^{\vee}), \quad (4.5) $$

where

$$ f_{\text{lat}}(\mathbf{w}_{\text{lat}}) \triangleq \mathbb{P}(\mathbf{B}'\mathbf{w}_{\text{lat}} \in \mathcal{S}), \quad f_{\text{lsc}}(\mathbf{w}_{\text{lsc}}) \triangleq \mathbb{P}(\mathbf{u} - \text{Dec}(\mathbf{u}) = \mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}), \quad (4.6) $$

$$ (\mathbf{r}_{\text{lat}}, \mathbf{r}_{\text{lsc}}) \triangleq \mathbf{r} \triangleq (\mathbf{e} + \mathbf{A}_{\text{enu}}(\mathbf{s}_{\text{enu}} - \tilde{\mathbf{s}}_{\text{enu}}) + \mathbf{A}_{\text{fft}}(\mathbf{s}_{\text{fft}} - \tilde{\mathbf{s}}_{\text{fft}}), \mathbf{s}_{\text{lat}}, \tilde{\mathbf{s}}_{\text{fft}}), \quad (4.7) $$

and

$$ \mathbf{B}_{\text{global}}^{\text{tmp}} \triangleq \begin{bmatrix} \text{Id}_{\beta_{\text{sieve}}} & 0 \\ \mathbf{A}_{\text{fft}}^{\top} \mathbf{B}'_{[m]} & \text{Id}_{n_{\text{fft}}} \end{bmatrix}. \quad (4.8) $$

Here, $\mathbf{r}_{\text{lat}}$ corresponds to the first $m+n_{\text{lat}}$ coordinates of $\mathbf{r}$, while $\mathbf{r}_{\text{lsc}}$ corresponds to its last $n_{\text{fft}}$ coordinates. Additionally, under Assumption 4.3, we have that the random variable $\mathbf{u} - \text{Dec}(\mathbf{u})$ is independent of $\mathbf{u}$ and follows the distribution induced by the polar code decoder.

*Proof.* For any vector in $\Lambda(\mathbf{B}')$, let $\mathbf{x}$ and $\mathbf{y}$ denote its first $m$ coordinates and its next $n_{\text{lat}}$ coordinates, respectively. Taking the conditional expectation over the randomness of both the polar code decoder and the short vector sampler, we obtain:

$$ \begin{aligned} \mathbb{E}_{\mathcal{S}, \text{Dec}} \left( F_{\hat{\mathbf{s}}_{\text{enu}}}^{(\text{lsc})} (\mathbf{G}^{\top} \tilde{\mathbf{s}}_{\text{fft}}) \right) &= \sum_{\substack{(\mathbf{x}, \mathbf{y}) \in \Lambda(\mathbf{B}') \\ \mathbf{c}_{\text{lsc}} \in \Lambda(C_{\text{lsc}})}} \mathbb{P} \left( (\mathbf{x}, \mathbf{y}) \in \mathcal{S} \text{ and } \text{Dec}(\mathbf{A}_{\text{fft}}^{\top} \mathbf{x}) = \mathbf{c}_{\text{lsc}} \right) \\ &= \sum_{\substack{(\mathbf{x}, \mathbf{y}) \in \Lambda(\mathbf{B}') \\ \mathbf{w}_{\text{lsc}} \in \Lambda(C_{\text{lsc}}) + \mathbf{A}_{\text{fft}}^{\top} \mathbf{x}}} \mathbb{P} \left( (\mathbf{x}, \mathbf{y}) \in \mathcal{S} \text{ and } \mathbf{A}_{\text{fft}}^{\top} \mathbf{x} - \text{Dec}(\mathbf{A}_{\text{fft}}^{\top} \mathbf{x}) = \mathbf{w}_{\text{lsc}} \right) \\ &= \sum_{\substack{(\mathbf{x}, \mathbf{y}) \in \Lambda(\mathbf{B}') \\ \mathbf{w}_{\text{lsc}} \in \Lambda(C_{\text{lsc}}) + \mathbf{A}_{\text{fft}}^{\top} \mathbf{x}}} \mathbb{P} \left( (\mathbf{x}, \mathbf{y}) \in \mathcal{S} \right) \cdot \mathbb{P} \left( \mathbf{A}_{\text{fft}}^{\top} \mathbf{x} - \text{Dec}(\mathbf{A}_{\text{fft}}^{\top} \mathbf{x}) = \mathbf{w}_{\text{lsc}} \right) \\ &= \sum_{\substack{(\mathbf{x}, \mathbf{y}) \in \Lambda(\mathbf{B}') \\ \mathbf{w}_{\text{lsc}} \in \Lambda(C_{\text{lsc}}) + \mathbf{A}_{\text{fft}}^{\top} \mathbf{x}}} \mathbb{P} \left( (\mathbf{x}, \mathbf{y}) \in \mathcal{S} \right) \cdot \mathbb{P} \left( \mathbf{A}_{\text{fft}}^{\top} \mathbf{x} - \text{Dec}(\mathbf{A}_{\text{fft}}^{\top} \mathbf{x}) = \mathbf{w}_{\text{lsc}} \right) \end{aligned} $$

where the last equality holds because of the independence of the decoding noise $\mathbf{u} - \text{Dec}(\mathbf{u})$ from $\mathbf{u}$. Next, we simplify the inner expression inside the cosine function:

$$ \begin{aligned} & \langle \mathbf{x}, \mathbf{b} - \mathbf{A}_{\text{enu}} \tilde{\mathbf{s}}_{\text{enu}} \rangle - \langle \mathbf{A}_{\text{fft}}^{\top} \mathbf{x} - \mathbf{w}_{\text{lsc}}, \tilde{\mathbf{s}}_{\text{fft}} \rangle \\ &= \langle \mathbf{x}, \mathbf{e} + \mathbf{A}_{\text{enu}}(\mathbf{s}_{\text{enu}} - \tilde{\mathbf{s}}_{\text{enu}}) + \mathbf{A}_{\text{lat}} \mathbf{s}_{\text{lat}} + \mathbf{A}_{\text{fft}} \tilde{\mathbf{s}}_{\text{fft}} \rangle - \langle \mathbf{A}_{\text{fft}}^{\top} \mathbf{x} - \mathbf{w}_{\text{lsc}}, \tilde{\mathbf{s}}_{\text{fft}} \rangle \\ &= \langle \mathbf{x}, \mathbf{e} + \mathbf{A}_{\text{enu}}(\mathbf{s}_{\text{enu}} - \tilde{\mathbf{s}}_{\text{enu}}) + \mathbf{A}_{\text{fft}}(\tilde{\mathbf{s}}_{\text{fft}} - \tilde{\mathbf{s}}_{\text{fft}}) \rangle + \langle \mathbf{A}_{\text{lat}}^{\top} \mathbf{x}, \mathbf{s}_{\text{lat}} \rangle + \langle \mathbf{w}_{\text{lsc}}, \tilde{\mathbf{s}}_{\text{fft}} \rangle \\ &= \langle (\mathbf{x}, \mathbf{y}, \mathbf{w}_{\text{lsc}}), \mathbf{r} \rangle \mod q \end{aligned} $$

where $\mathbf{r}$ is as defined in Equation (4.7). So, we obtain

$$ \mathbb{E}_{\mathcal{S}, \text{Dec}} \left( F_{\hat{\mathbf{s}}_{\text{enu}}}^{(\text{lsc})} (\mathbf{G}^{\top} \tilde{\mathbf{s}}_{\text{fft}}) \right) = \sum_{\substack{(\mathbf{x}, \mathbf{y}) \in \Lambda(\mathbf{B}') \\ \mathbf{w}_{\text{lsc}} \in \Lambda(C_{\text{lsc}}) + \mathbf{A}_{\text{fft}}^{\top} \mathbf{x}}} \mathbb{P} \left( (\mathbf{x}, \mathbf{y}) \in \mathcal{S} \right) \cdot \mathbb{P} \left( \mathbf{A}_{\text{fft}}^{\top} \mathbf{x} - \text{Dec}(\mathbf{A}_{\text{fft}}^{\top} \mathbf{x}) = \mathbf{w}_{\text{lsc}} \right) \\ \cdot \cos \left( 2\pi \langle (\mathbf{x}, \mathbf{y}, \mathbf{w}_{\text{lsc}}), \frac{\mathbf{r}}{q} \rangle \right) $$

We observe that if $(\mathbf{x}, \mathbf{y}) \in \Lambda(\mathbf{B}')$ and $\mathbf{w}_{\text{lsc}} \in \Lambda(C_{\text{lsc}}) + \mathbf{A}_{\text{fft}}^{\top} \mathbf{x}$, then it follows that $(-\mathbf{x}, -\mathbf{y}) \in \Lambda(\mathbf{B}')$ and $-\mathbf{w}_{\text{lsc}} \in \Lambda(C_{\text{lsc}}) - \mathbf{A}_{\text{fft}}^{\top} \mathbf{x}$. Furthermore, the probabilities involved in the formula are invariant
under negation. This allows us to express the cosine function in its exponential form, which yields

$$
\begin{align*}
\mathbb{E}_{\mathcal{S}, \text{Dec}} \left( F_{\widetilde{\mathbf{s}}_{\text{enu}}}^{(\text{lsc})} \left( \mathbf{G}^{\top} \widetilde{\mathbf{s}}_{\text{fft}} \right) \right) &= \sum_{(\mathbf{x}, \mathbf{y}) \in \Lambda(\mathbf{B}^{\prime})} \mathbb{P}((\mathbf{x}, \mathbf{y}) \in \mathcal{S}) \cdot \mathbb{P} \left( \mathbf{A}_{\text{fft}}^{\top} \mathbf{x} - \text{Dec} \left( \mathbf{A}_{\text{fft}}^{\top} \mathbf{x} \right) = \mathbf{w}_{\text{lsc}} \right) \cdot e^{2i\pi \langle (\mathbf{x}, \mathbf{y}, \mathbf{w}_{\text{lsc}}), \frac{\mathbf{r}}{\mathbf{q}} \rangle} \\
&= \sum_{(\mathbf{w}_{\text{lat}}, \mathbf{w}_{\text{lsc}}) \in \Lambda(\mathbf{B}_{\text{global}}^{\text{tmp}})} f_{\text{lat}}(\mathbf{w}_{\text{lat}}) \cdot f_{\text{lsc}}(\mathbf{w}_{\text{lsc}}) \cdot e^{2i\pi \langle (\mathbf{B}'\mathbf{w}_{\text{lat}}, \mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}), \frac{\mathbf{r}}{\mathbf{q}} \rangle}.
\end{align*}
$$

Note that the function $f_{\text{lsc}}$ is defined in terms of a vector $\mathbf{u}$, which in this case depends on $\mathbf{w}_{\text{lat}}$.
However, the error vector produced by our polar code decoder is independent of the vector being de-
coded; that means the distribution $f_{\text{lsc}}$ does not depend on $\mathbf{u}$. Finally, following [CDMT24,DP23a],
we can apply the Poisson summation formula to obtain Equation (4.5). $\square$

**Second-Level Approximation of the Score Function.** By estimating the Fourier transforms $\widehat{f}_{\text{lat}}$ and $\widehat{f}_{\text{lsc}}$ from Lemma 4.5, we derive a new approximation of the score function:

**Approximation 4.6 (Second-Level Approximation).** *Based on Approximation 4.4, Assumptions 4.2 and 4.3, and assuming the Gaussian Heuristic holds, we have*

$$
F_{\widetilde{\mathbf{s}}_{\text{enu}}}^{(\text{lsc})} (\mathbf{G}^{\top} \widetilde{\mathbf{s}}_{\text{fft}}) \approx N \cdot \sum_{\substack{i>0 \\ j \ge 0}} N_{i,j} \cdot \int_{0}^{\infty} \psi_{\text{lsc}}(d_{\text{lsc}}) \cdot \Phi_{d_{\text{lsc}}}(i,j) dd_{\text{lsc}} \quad (4.9)
$$

where

$$
\Phi_{d_{\text{lsc}}}(i,j) \triangleq \Upsilon_{\frac{\beta_{\text{sieve}}}{2}} \left(\frac{2\pi}{q} d_{\text{lat}} i\right) \cdot \Upsilon_{\frac{n_{\text{fft}}}{2} - 1} \left(\frac{2\pi}{q} d_{\text{lsc}} j\right), \quad (4.10)
$$

$$
\gamma_n(x) \triangleq \frac{\Gamma(n+1) J_n(x)}{(x/2)^n} = \sum_{\ell=0}^{+\infty} \frac{(-1)^\ell (x/2)^{2\ell}}{\ell! \prod_{s=1}^\ell (n+s)}, \quad (4.11)
$$

$$
N_{i,j} \triangleq \left| \left\{ (\mathbf{w}_{\text{lat}}, \mathbf{w}_{\text{lsc}}) \in q\Lambda(\mathbf{B}_{\text{global}})^{\vee} + \mathbf{r}_{\text{proj}} \subseteq \text{span}(\mathbf{B}') \times \mathbb{R}^{n_{\text{fft}}} : \|\mathbf{w}_{\text{lat}}\| = i \text{ and } \|\mathbf{w}_{\text{lsc}}\| = j \right\} \right|, \quad (4.12)
$$

with $\mathbf{r}_{\text{proj}}$, the orthogonal projection on $\text{span}(\mathbf{B}_{\text{global}}) = \text{span}(\mathbf{B}') \times \mathbb{R}^{n_{\text{fft}}}$ of

$$
\mathbf{r} \triangleq (\mathbf{e} + \mathbf{A}_{\text{enu}}(\mathbf{s}_{\text{enu}} - \tilde{\mathbf{s}}_{\text{enu}}) + \mathbf{A}_{\text{fft}}(\mathbf{s}_{\text{fft}} - \tilde{\mathbf{s}}_{\text{fft}}), \mathbf{s}_{\text{lat}}, \tilde{\mathbf{s}}_{\text{fft}}), \quad (4.13)
$$

and

$$
\mathbf{B}_{\text{global}} \triangleq \left[ \begin{array}{c|c} \beta_{\text{sieve}} & n_{\text{fft}} \\ \hline \mathbf{B}' & \mathbf{0} \\ \hline \mathbf{A}_{\text{fft}}^{\top} \cdot \mathbf{B}'_{[m]} & \mathbf{B}_{\text{lsc}} \end{array} \right] \xrightarrow{m+n_{\text{lat}}} \left[ \begin{array}{c} \mathbf{r} \\ \hline \mathbf{A}_{\text{lsc}} \end{array} \right]
$$

Here:

- $\mathbf{B}' \in \mathbb{R}^{(m+n_{\text{lat}}) \times \beta_{\text{sieve}}}$ is a basis of the sublattice where the sampled short vectors lie,

- $\mathbf{B}'_{[m]}$ consists of the first $m$ rows of $\mathbf{B}'$,

- and $\mathbf{B}_{\text{lsc}}$ is a basis of the lattice $\Lambda(C_{\text{lsc}})$.
To justify the above approximation, we first show that under Assumptions 4.2 and 4.3, and assuming the Gaussian Heuristic holds, the following two approximations hold:

$$ \widehat{f}_{\text{lat}}(\mathbf{w}_{\text{lat}}^{\vee}) \approx N \cdot \Upsilon_{\frac{\beta_{\text{sieve}}}{2}} \left( 2\pi d_{\text{lat}} \left\| \mathbf{B}' (\mathbf{B}'^{\top} \mathbf{B}')^{-1} \mathbf{w}_{\text{lat}}^{\vee} \right\| \right), \quad (4.14) $$

and

$$ \widehat{f}_{\text{lsc}}(\mathbf{w}_{\text{lsc}}^{\vee}) \approx \int_{0}^{\infty} \psi_{\text{lsc}}(d_{\text{lsc}}) \cdot \Upsilon_{\frac{n_{\text{fft}}}{2}-1} \left( \frac{2\pi}{q} d_{\text{lsc}} \left\| \mathbf{B}_{\text{lsc}}^{-\top} \mathbf{w}_{\text{lsc}}^{\vee} \right\| \right) dd_{\text{lsc}}. \quad (4.15) $$

On the one hand, under Assumption 4.2 and the Gaussian Heuristic, we can smooth and approximate $f_{\text{lat}}$ by

$$ f_{\text{lat}}(\mathbf{w}_{\text{lat}}) \approx \mathbf{1}_{\le d_{\text{lat}}} (\mathbf{B}'\mathbf{w}_{\text{lat}}) \cdot N \cdot \frac{\text{Vol}(\Lambda(\mathbf{B}'))}{\text{Vol}(\text{Ball}_{d_{\text{lat}}}^{\beta_{\text{sieve}}})}. \quad (4.16) $$

Using the radial nature of both $\mathbf{1}_{\le d_{\text{lat}}}$ and $\widehat{\mathbf{1}}_{\le d_{\text{lat}}}$, and the facts that $\|\mathbf{B}'\mathbf{w}_{\text{lat}}\| = \|\sqrt{\mathbf{B}'^{\top}\mathbf{B}'}\mathbf{w}_{\text{lat}}\|$ and $\|\sqrt{\mathbf{B}'^{\top}\mathbf{B}'}^{-\top}\mathbf{w}_{\text{lat}}^{\vee}\| = \|\mathbf{B}'(\mathbf{B}'^{\top}\mathbf{B}')^{-1}\mathbf{w}_{\text{lat}}^{\vee}\|$, we have

$$ \begin{aligned} \widehat{f}_{\text{lat}}(\mathbf{w}_{\text{lat}}^{\vee}) &\approx \frac{N \cdot \text{Vol}(\Lambda(\mathbf{B}'))}{\text{Vol}(\text{Ball}_{d_{\text{lat}}}^{\beta_{\text{sieve}}})} \int_{\mathbb{R}^{\beta_{\text{sieve}}}} \mathbf{1}_{\le d_{\text{lat}}} (\mathbf{B}'\mathbf{w}_{\text{lat}}) e^{-2i\pi \langle \mathbf{w}_{\text{lat}}, \mathbf{w}_{\text{lat}}^{\vee} \rangle} d\mathbf{w}_{\text{lat}} \\ &= \frac{N \cdot \text{Vol}(\Lambda(\mathbf{B}'))}{\text{Vol}(\text{Ball}_{d_{\text{lat}}}^{\beta_{\text{sieve}}})} \int_{\mathbb{R}^{\beta_{\text{sieve}}}} \mathbf{1}_{\le d_{\text{lat}}} (\sqrt{\mathbf{B}'^{\top}\mathbf{B}'}\mathbf{w}_{\text{lat}}) e^{-2i\pi \langle \mathbf{w}_{\text{lat}}, \mathbf{w}_{\text{lat}}^{\vee} \rangle} d\mathbf{w}_{\text{lat}} \\ &= \frac{N \cdot \text{Vol}(\Lambda(\mathbf{B}'))}{\text{Vol}(\text{Ball}_{d_{\text{lat}}}^{\beta_{\text{sieve}}}) \cdot \sqrt{\det(\mathbf{B}'^{\top}\mathbf{B}')}} \cdot \int_{\mathbb{R}^{\beta_{\text{sieve}}}} \mathbf{1}_{\le d_{\text{lat}}} (\mathbf{v}) e^{-2i\pi \langle \sqrt{\mathbf{B}'^{\top}\mathbf{B}'}^{-1}\mathbf{v}, \mathbf{w}_{\text{lat}}^{\vee} \rangle} d\mathbf{v} \\ &= \frac{N}{\text{Vol}(\text{Ball}_{d_{\text{lat}}}^{\beta_{\text{sieve}}})} \cdot \widehat{\mathbf{1}}_{\le d_{\text{lat}}} (\sqrt{\mathbf{B}'^{\top}\mathbf{B}'}^{-\top}\mathbf{w}_{\text{lat}}^{\vee}) \\ &= \frac{N}{\text{Vol}(\text{Ball}_{d_{\text{lat}}}^{\beta_{\text{sieve}}})} \cdot \widehat{\mathbf{1}}_{\le d_{\text{lat}}} (\mathbf{B}'(\mathbf{B}'^{\top}\mathbf{B}')^{-1}\mathbf{w}_{\text{lat}}^{\vee}) \end{aligned} $$

where the Fourier transform of the indicator function of a ball can be expressed in term of the Bessel function:

$$ \begin{aligned} \widehat{\mathbf{1}}_{\le d_{\text{lat}}} (\mathbf{w}) &= \left( \frac{d_{\text{lat}}}{\|\mathbf{w}\|} \right)^{\frac{\beta_{\text{sieve}}}{2}} \cdot J_{\frac{\beta_{\text{sieve}}}{2}} (2\pi d_{\text{lat}} \|\mathbf{w}\|) \\ &= \text{Vol}(\text{Ball}_{d_{\text{lat}}}^{\beta_{\text{sieve}}}) \cdot \Upsilon_{\frac{\beta_{\text{sieve}}}{2}} (2\pi d_{\text{lat}} \|\mathbf{w}\|). \end{aligned} $$

On the other hand, based on Assumption 4.3, we state the following approximation for $f_{\text{lsc}}$:

$$ \begin{aligned} f_{\text{lsc}}(\mathbf{w}_{\text{lsc}}) &\triangleq \mathbb{P} (\mathbf{u} - \text{Dec}(\mathbf{u}) = \mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}) \\ &= \mathbb{P} (\|\mathbf{u} - \text{Dec}(\mathbf{u})\| = \|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|) \cdot \mathbb{P} (\mathbf{u} - \text{Dec}(\mathbf{u}) = \mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}} \mid \|\mathbf{u} - \text{Dec}(\mathbf{u})\| = \|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|) \\ &\approx \left( \int_{\|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|}^{\sqrt{\|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|^2+1}} \psi_{\text{lsc}}(d_{\text{lsc}}) dd_{\text{lsc}} \right) \cdot \frac{\text{Vol}(\Lambda(C_{\text{lsc}}))}{\text{Vol}(\text{Ball}_{\sqrt{\|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|^2+1}}^{n_{\text{fft}}}) - \text{Vol}(\text{Ball}_{\|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|}^{n_{\text{fft}}})} \end{aligned} $$

where $\psi_{\text{lsc}}$ is the probability density function of the normal distribution $N(\mu_{\text{lsc}}, \sigma_{\text{lsc}}^2)$. In the context of our dual attack on KYBER, the decoding distance $\|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|$ takes values in the hundreds or even thousands, as shown in Appendix C, Table C.1. Consequently, the difference $\sqrt{\|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|^2+1} - \|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|$ is small, allowing us to approximate $f_{\text{lsc}}(\mathbf{w}_{\text{lsc}})$ by

$$ \begin{aligned} f_{\text{lsc}}(\mathbf{w}_{\text{lsc}}) &\approx \frac{\left(\sqrt{\|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|^2 + 1} - \|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|\right) \cdot \psi_{\text{lsc}}(\|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|) \cdot \text{Vol}(\Lambda(C_{\text{lsc}}))}{\left(\sqrt{\|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|^2 + 1} - \|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|\right) \cdot \text{Vol}(\text{Sphere}_{\|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|}^{n_{\text{fft}}})} \\ &= \psi_{\text{lsc}}(\|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|) \cdot \frac{\text{Vol}(\Lambda(C_{\text{lsc}}))}{\text{Vol}(\text{Sphere}_{\|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|}^{n_{\text{fft}}})} \end{aligned} $$
Note that we must have

$$ \sum_{\mathbf{w}_{\text{lsc}} \in \mathbb{Z}^{n_{\text{fft}}}} \mathbb{P}(\mathbf{u} - \text{Dec}(\mathbf{u}) = \mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}) = 1. $$

Thus, the smoothed approximation of $f_{\text{lsc}}$ should represent a probability density function, as we can verify by the following<fnref n="10" />:

$$ \begin{aligned} \int_{\mathbb{R}^{n_{\text{fft}}}} \psi_{\text{lsc}} (\|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|) \cdot \frac{\text{Vol}(\Lambda(C_{\text{lsc}}))}{\text{Vol}(\text{Sphere}_{\|\mathbf{w}_{\text{lsc}}\|}^{n_{\text{fft}}})} d\mathbf{w}_{\text{lsc}} &= \int_{\mathbb{R}^{n_{\text{fft}}}} \psi_{\text{lsc}} (\|\mathbf{w}\|) \cdot \frac{\text{Vol}(\Lambda(C_{\text{lsc}}))}{\text{Vol}(\text{Sphere}_{\|\mathbf{w}\|}^{n_{\text{fft}}})} \cdot \frac{1}{\det(\mathbf{B}_{\text{lsc}})} d\mathbf{w} \\ &= \int_{\mathbb{R}^{n_{\text{fft}}}} \psi_{\text{lsc}} (\|\mathbf{w}\|) \cdot \frac{1}{\text{Vol}(\text{Sphere}_{\|\mathbf{w}\|}^{n_{\text{fft}}})} d\mathbf{w} \\ &= \int_{0}^{\infty} \psi_{\text{lsc}}(d_{\text{lsc}}) \int_{\text{Sphere}_{d_{\text{lsc}}}^{n_{\text{fft}}}} \frac{1}{\text{Vol}(\text{Sphere}_{d_{\text{lsc}}}^{n_{\text{fft}}})} d\sigma(\mathbf{s}) dd_{\text{lsc}} \\ &= \int_{0}^{\infty} \psi_{\text{lsc}}(d_{\text{lsc}}) dd_{\text{lsc}} \\ &\approx 1 \end{aligned} $$

where $d\sigma(\mathbf{s})$ represents the classical Lebesgue measure on the sphere $\text{Sphere}_{d_{\text{lsc}}}^{n_{\text{fft}}}$. Finally, by using [CE01, Prop.2.1], we have

$$ \begin{aligned} \hat{f}_{\text{lsc}}(\mathbf{w}_{\text{lsc}}^{\vee}) &\approx \int_{\mathbb{R}^{n_{\text{fft}}}} \psi_{\text{lsc}} (\|\mathbf{B}_{\text{lsc}}\mathbf{w}_{\text{lsc}}\|) \cdot \frac{\text{Vol}(\Lambda(C_{\text{lsc}}))}{\text{Vol}(\text{Sphere}_{\|\mathbf{w}_{\text{lsc}}\|}^{n_{\text{fft}}})} \cdot e^{-2i\pi \langle \mathbf{w}_{\text{lsc}}^{\vee}, \mathbf{w}_{\text{lsc}} \rangle} d\mathbf{w}_{\text{lsc}} \\ &= \int_{\mathbb{R}^{n_{\text{fft}}}} \psi_{\text{lsc}} (\|\mathbf{w}\|) \cdot \frac{\text{Vol}(\Lambda(C_{\text{lsc}}))}{\text{Vol}(\text{Sphere}_{\|\mathbf{w}\|}^{n_{\text{fft}}})} \cdot e^{-2i\pi \langle \mathbf{w}_{\text{lsc}}^{\vee}, \mathbf{B}_{\text{lsc}}^{-1} \mathbf{w}_{\text{lsc}} \rangle} \cdot \frac{1}{\det(\mathbf{B}_{\text{lsc}})} d\mathbf{w} \\ &= \int_{\mathbb{R}^{n_{\text{fft}}}} \psi_{\text{lsc}} (\|\mathbf{w}\|) \cdot \frac{1}{\text{Vol}(\text{Sphere}_{\|\mathbf{w}\|}^{n_{\text{fft}}})} \cdot e^{-2i\pi \langle \mathbf{B}_{\text{lsc}}^{-\top} \mathbf{w}_{\text{lsc}}^{\vee}, \mathbf{w}_{\text{lsc}} \rangle} d\mathbf{w} \\ &= \frac{2\pi}{\|\mathbf{B}_{\text{lsc}}^{-\top} \mathbf{w}_{\text{lsc}}^{\vee}\|^{\frac{n_{\text{fft}}}{2}-1}} \int_{0}^{\infty} \psi_{\text{lsc}}(d_{\text{lsc}}) \cdot \frac{\text{Vol}(\Lambda(C_{\text{lsc}}))}{\text{Vol}(\text{Sphere}_{d_{\text{lsc}}}^{n_{\text{fft}}})} \cdot d_{\text{lsc}}^{\frac{n_{\text{fft}}}{2}} \cdot J_{\frac{n_{\text{fft}}}{2}-1} (2\pi d_{\text{lsc}} \|\mathbf{B}_{\text{lsc}}^{-\top} \mathbf{w}_{\text{lsc}}^{\vee}\|) dd_{\text{lsc}} \\ &= \int_{0}^{\infty} \psi_{\text{lsc}}(d_{\text{lsc}}) \cdot \Upsilon_{\frac{n_{\text{fft}}}{2}-1} (2\pi d_{\text{lsc}} \|\mathbf{B}_{\text{lsc}}^{-\top} \mathbf{w}_{\text{lsc}}^{\vee}\|) dd_{\text{lsc}}. \end{aligned} $$

Finally, by leveraging Approximation 4.4 and Lemma 4.5, together with Approximations (4.14) and (4.15) for $\hat{f}_{\text{lat}}$ and $\hat{f}_{\text{lsc}}$, we can complete the justification for Approximation 4.6. First, we observe that for all $(\mathbf{w}_{\text{lat}}^{\vee}, \mathbf{w}_{\text{lsc}}^{\vee}) \in \Lambda(\mathbf{B}_{\text{global}}^{\text{tmp}})^{\vee} + \frac{(\mathbf{B}^{\top} \mathbf{r}_{\text{lat}}, \mathbf{B}_{\text{lsc}}^{\top} \mathbf{r}_{\text{lsc}})}{q}$, we have

$$ q (\mathbf{B}' (\mathbf{B}'^{\top} \mathbf{B}')^{-1} \mathbf{w}_{\text{lat}}^{\vee}, \mathbf{B}_{\text{lsc}}^{-\top} \mathbf{w}_{\text{lsc}}^{\vee}) \in q\Lambda(\mathbf{B}_{\text{global}})^{\vee} + \mathbf{r}_{\text{proj}}, $$

And so, combining all the terms and making the appropriate variable change, we obtain

$$ F_{\mathbf{s}_{\text{enu}}}^{(\text{lsc})} (\mathbf{G}^{\top} \mathbf{s}_{\text{fft}}) \approx N \cdot \int_{0}^{\infty} \psi_{\text{lsc}}(d_{\text{lsc}}) \cdot \sum_{\substack{(\mathbf{w}_{\text{lat}}^{\vee}, \mathbf{w}_{\text{lsc}}^{\vee}) \\ \in q\Lambda(\mathbf{B}_{\text{global}})^{\vee} + \mathbf{r}_{\text{proj}}}} \Upsilon_{\frac{\beta_{\text{sieve}}}{2}} \left( \frac{2\pi}{q} d_{\text{lat}} \|\mathbf{w}_{\text{lat}}^{\vee}\| \right) \cdot \Upsilon_{\frac{n_{\text{fft}}}{2}-1} \left( \frac{2\pi}{q} d_{\text{lsc}} \|\mathbf{w}_{\text{lsc}}^{\vee}\| \right) dd_{\text{lsc}}. $$

We conclude by noting that the inner sum depends only on the lengths of $\mathbf{w}_{\text{lat}}^{\vee}$ and $\mathbf{w}_{\text{lsc}}^{\vee}$, that we denote $i$ and $j$, respectively.

**Third-Level Approximation of the Score Function.** In Appendix B, we provide an initial intuition for why the good guess can be distinguished from the wrong ones, based on Approximation 4.6. However, here we present more precise calculations.

<footnote n="10">¹⁰ We verified that $\int_{-\infty}^{0} \psi_{\text{lsc}}(r) dr$ is negligible.</footnote>
Recall that Approximation 4.6 gives

$$F_{\tilde{\mathbf{s}}_{\text{enu}}}^{(\text{lsc})}(\mathbf{G}^{\top} \tilde{\mathbf{s}}_{\text{fft}}) \approx N \cdot \int_{0}^{\infty} \psi_{\text{lsc}}(d_{\text{lsc}}) \cdot \sum_{i,j} N_{i,j} \cdot \Phi_{d_{\text{lsc}}}(i, j) dd_{\text{lsc}} \quad (4.17)$$

where $N_{i,j}$ is a random variable representing the number of pairs $(\mathbf{w}_{\text{lat}}^{\vee}, \mathbf{w}_{\text{lsc}}^{\vee}) \in q\Lambda (\mathbf{B}_{\text{global}})^{\vee} + \mathbf{r}_{\text{proj}} \subseteq \text{span} (\mathbf{B}') \times \mathbb{R}^{n_{\text{fft}}}$ such that $\|\mathbf{w}_{\text{lat}}^{\vee}\| = i$ and $\|\mathbf{w}_{\text{lsc}}^{\vee}\| = j$.

Describing the distribution in Equation (4.17) is quite complex. To simplify this, we propose the following model:

**Model 4.7.** We assume that $F_{\tilde{\mathbf{s}}_{\text{enu}}}^{(\text{lsc})}(\mathbf{G}^{\top} \tilde{\mathbf{s}}_{\text{fft}})$ approximately follows the same distribution as $\mathcal{D} + \mathcal{N}(0, N/2)$, where $\mathcal{N}(0, N/2)$ denotes a normal distribution with mean 0 and standard deviation $\sqrt{N/2}$, and

$$\mathcal{D} \triangleq N \cdot \int_{0}^{\infty} \psi_{\text{lsc}}(d_{\text{lsc}}) \cdot \left( \max_{i,j: N_{i,j}=1} (\Phi_{d_{\text{lsc}}}(i,j)) \right) dd_{\text{lsc}}. \quad (4.18)$$

We recall that $\psi_{\text{lsc}}$ refers to the probability density function of $\mathcal{N}(\mu_{\text{lsc}}, \sigma_{\text{lsc}}^2)$.

Based on Approximation 4.6 and Model 4.7, we can make the following two approximations, with probabilities calculated over the randomness of the guesses $I_{\text{enu}}$ and $\tilde{\mathbf{s}}_{\text{fft}}$, as well as over the randomness of the LWE instance:

**Approximation 4.8 (Good Guess).** If we make the good guess $(\tilde{\mathbf{s}}_{\text{enu}}, \tilde{\mathbf{s}}_{\text{fft}}) = (\mathbf{s}_{\text{enu}}, \mathbf{s}_{\text{fft}})$ and if we choose $T$ around the expectation of $F_{\tilde{\mathbf{s}}_{\text{enu}}}^{(\text{lsc})}(\mathbf{G}^{\top} \tilde{\mathbf{s}}_{\text{fft}})$, namely by defining

$$\frac{T}{N} = \frac{\exp\left(\frac{-\alpha(\pi\mu_{\text{lsc}}/q)^2}{1+2\alpha(\pi\sigma_{\text{lsc}}/q)^2}\right)}{\sqrt{1+2\alpha(\pi\sigma_{\text{lsc}}/q)^2}} \cdot \int_{0}^{1} \beta_{\text{sieve}} \cdot t^{\beta_{\text{sieve}}-1} \cdot e^{-\alpha\left(\frac{\pi d_{\text{lat}} t}{q}\right)^2} dt, \quad (4.19)$$

then

$$P_{\text{good}} \triangleq \mathbb{P} \left( F_{\tilde{\mathbf{s}}_{\text{enu}}}^{(\text{lsc})} (\mathbf{G}^{\top} \tilde{\mathbf{s}}_{\text{fft}}) \ge T \right) \approx 0.5 \quad (4.20)$$

**Approximation 4.9 (Wrong Guess).** If we make the wrong guess $(\tilde{\mathbf{s}}_{\text{enu}}, \tilde{\mathbf{s}}_{\text{fft}}) \neq (\mathbf{s}_{\text{enu}}, \mathbf{s}_{\text{fft}})$, then

$$P_{\text{wrong}} \triangleq \mathbb{P} \left( F_{\tilde{\mathbf{s}}_{\text{enu}}}^{(\text{lsc})} (\mathbf{G}^{\top} \tilde{\mathbf{s}}_{\text{fft}}) \ge T \right) \quad (4.21)$$

$$\approx \int_{-\infty}^{+\infty} \int_{0}^{+\infty} \min \left( 1, \int_{\mathcal{E}(T-t)} \lambda(x)\mu(y)d(x, y) \right) \cdot \frac{e^{-\frac{t^2}{N} - \frac{(d_{\text{lsc}} - \mu_{\text{lsc}})^2}{2\sigma_{\text{lsc}}^2}}}{\pi\sigma_{\text{lsc}}\sqrt{2N}} dd_{\text{lsc}} dt \quad (4.22)$$

where

$$\mathcal{E}(T-t) \triangleq \{(x, y) \in \mathbb{R}_+^2 : N \cdot \Phi_{d_{\text{lsc}}}(x, y) \ge T-t\}, \quad (4.23)$$

$$\lambda(x) \triangleq \frac{2 \cdot \delta \left( \beta_{\text{bkz}} \right)^{\beta_{\text{sieve}}(m+n_{\text{lat}}-\beta_{\text{sieve}})} \cdot \pi^{\frac{\beta_{\text{sieve}}}{2}} \cdot x^{\beta_{\text{sieve}}-1}}{q^{\beta_{\text{sieve}} \cdot \frac{m}{m+n_{\text{lat}}}} \cdot \Gamma\left(\frac{\beta_{\text{sieve}}}{2}\right)} \quad \text{and} \quad \mu(y) \triangleq \frac{2 \cdot \pi^{\frac{n_{\text{fft}}}{2}} \cdot y^{n_{\text{fft}}-1}}{q^{k_{\text{fft}}} \cdot \Gamma\left(\frac{n_{\text{fft}}}{2}\right)}. \quad (4.24)$$

**Justification of Approximation 4.8.** The rationale behind Approximation 4.8 is that if we make the good guess $(\tilde{\mathbf{s}}_{\text{enu}}, \tilde{\mathbf{s}}_{\text{fft}}) = (\mathbf{s}_{\text{enu}}, \mathbf{s}_{\text{fft}})$, then there exists an element

$$\mathbf{r}_{\text{proj}} \triangleq (\mathbf{P}(\mathbf{e}, \mathbf{s}_{\text{lat}}), \mathbf{s}_{\text{fft}}) \in q\Lambda (\mathbf{B}_{\text{global}})^{\vee} + \mathbf{r}_{\text{proj}} \quad (4.25)$$
which has particularly small length. Specifically, the quantities $\frac{\|\mathbf{P}(\mathbf{e}, \mathbf{s}_{\text{lat}})\|}{\sqrt{\frac{\alpha}{2}}}$ and $\frac{\|\mathbf{s}_{\text{fft}}\|}{\sqrt{\frac{\alpha}{2}}}$ approximately follow a $\chi$-distribution<fnref n="11" /> with degrees of freedom $\beta_{\text{sieve}}$ and $n_{\text{fft}}$, respectively. Therefore, we obtain

$$ 
\begin{aligned}
\mathbb{E}_{\chi_{\beta_{\text{sieve}}} \cdot \chi_{n_{\text{fft}}}} (F_{\text{sieve}}^{(\text{lsc})} (\mathbf{G}^{\top} \mathbf{s}_{\text{fft}})) & \approx \mathbb{E}_{\chi_{\beta_{\text{sieve}}} \cdot \chi_{n_{\text{fft}}}} (\mathcal{D}) \\
& \approx N \cdot \mathbb{E}_{d_{\text{lsc}}} (\mathbb{E}_{\chi_{\beta_{\text{sieve}}} \cdot \chi_{n_{\text{fft}}}} (\Phi_{d_{\text{lsc}}} (\sqrt{\frac{\alpha}{2}} \chi_{\beta_{\text{sieve}}}, \sqrt{\frac{\alpha}{2}} \chi_{n_{\text{fft}}}))) \\
& = N \cdot \mathbb{E}_{\chi_{\beta_{\text{sieve}}} \cdot \chi_{n_{\text{fft}}}} \left( \gamma_{\beta_{\text{sieve}}} \left( \frac{2\pi}{q} d_{\text{lat}} \sqrt{\frac{\alpha}{2}} \chi_{\beta_{\text{sieve}}} \right) \right) \\
& \cdot \mathbb{E}_{\chi_{n_{\text{fft}}}, d_{\text{lsc}}} \left( \gamma_{\frac{n_{\text{fft}}}{2} - 1} \left( \frac{2\pi}{q} d_{\text{lsc}} \sqrt{\frac{\alpha}{2}} \chi_{n_{\text{fft}}} \right) \right)
\end{aligned}
$$

where $\mathbb{E}_{d_{\text{lsc}}} (\cdot)$ denotes the expectation with respect to the random variable $d_{\text{lsc}}$, which follows a normal distribution $N(\mu_{\text{lsc}}, \sigma_{\text{lsc}}^2)$.

Using Equation (4.11), each term in the above equation can be expressed in terms of the moments of the $\chi^2$-distribution:

$$ 
\begin{aligned}
\mathbb{E}_{\chi_{n_{\text{fft}}}, d_{\text{lsc}}} \left( \gamma_{\frac{n_{\text{fft}}}{2} - 1} \left( \frac{2\pi}{q} d_{\text{lsc}} \sqrt{\frac{\alpha}{2}} \chi_{n_{\text{fft}}} \right) \right) &= \mathbb{E}_{d_{\text{lsc}}} \left( \sum_{\ell=0}^{+\infty} \frac{\left(-\alpha \left(\frac{\pi d_{\text{lsc}}}{q}\right)^2\right)^{\ell}}{\ell!} \cdot \frac{\mathbb{E}(\chi_{n_{\text{fft}}}^{2\ell})}{2^{\ell} \prod_{s=1}^{\ell} \left(\frac{n_{\text{fft}}}{2} - 1 + s\right)} \right) \\
&= \mathbb{E}_{d_{\text{lsc}}} \left( \sum_{\ell=0}^{+\infty} \frac{\left(-\alpha \left(\frac{\pi d_{\text{lsc}}}{q}\right)^2\right)^{\ell}}{\ell!} \right) \\
&= \mathbb{E}_{d_{\text{lsc}}} \left( e^{-\alpha \left(\frac{\pi d_{\text{lsc}}}{q}\right)^2} \right) \\
&= \frac{\exp\left(\frac{-\alpha(\pi \mu_{\text{lsc}}/q)^2}{1+2\alpha(\pi \sigma_{\text{lsc}}/q)^2}}}{\sqrt{1+2\alpha(\pi \sigma_{\text{lsc}}/q)^2}}
\end{aligned}
$$

and

$$ 
\begin{aligned}
\mathbb{E}_{\chi_{\beta_{\text{sieve}}}} \left( \gamma_{\frac{\beta_{\text{sieve}}}{2}} \left( \frac{2\pi}{q} d_{\text{lat}} \sqrt{\frac{\alpha}{2}} \chi_{\beta_{\text{sieve}}} \right) \right) &= \sum_{\ell=0}^{+\infty} \frac{\left(-\alpha \left(\frac{\pi d_{\text{lsc}}}{q}\right)^2\right)^{\ell}}{\ell!} \cdot \frac{\mathbb{E}(\chi_{\beta_{\text{sieve}}}^{2\ell})}{2^{\ell} \prod_{s=1}^{\ell} \left(\frac{\beta_{\text{sieve}}}{2} + s\right)} \\
&= \sum_{\ell=0}^{+\infty} \frac{\left(-\alpha \left(\frac{\pi d_{\text{lsc}}}{q}\right)^2\right)^{\ell}}{\ell!} \cdot \frac{\prod_{s=0}^{\ell-1} \left(\frac{\beta_{\text{sieve}}}{2} + s\right)}{\prod_{s=0}^{\ell-1} \left(\frac{\beta_{\text{sieve}}}{2} + 1 + s\right)} \\
&= \int_{0}^{1} \beta_{\text{sieve}} \cdot t^{\beta_{\text{sieve}}-1} \cdot e^{-\alpha \left(\frac{\pi d_{\text{lsc}} t}{q}\right)^2} dt
\end{aligned}
$$

where the last equality is a well-known result concerning generalized hypergeometric functions<fnref n="12" />.

Finally, in Equation (4.19), we chose $T$ as the expected score $\mathbb{E}(F_{\text{sieve}}^{(\text{lsc})} (\mathbf{G}^{\top} \mathbf{s}_{\text{fft}}))$ of the good guess. Through experimentation, we verified that the expectation of this score is approximately equal to its median, which justifies Approximation 4.8.

<footnote n="11">¹¹ Strictly speaking, it is not an exact $\chi$-distribution since the coordinates of $\mathbf{r}_{\text{proj}}$ are not precisely normally distributed.</footnote>

<footnote n="12">¹² Note that $\int_{0}^{1} \beta_{\text{sieve}} \cdot t^{\beta_{\text{sieve}}-1} e^{-\alpha \left(\frac{\pi d_{\text{lsc}} t}{q}\right)^2} dt = \mathbb{E}_{t \sim \text{Unif}(\text{Ball}_{d_{\text{lat}}}^{\beta_{\text{sieve}}})} \left( e^{-\alpha \left(\frac{\pi t}{q}\right)^2} \right)$.</footnote>
Justification of Approximation 4.9. On the other hand, Approximation 4.9 is obtained by estimating the length of the short vectors in $q\Lambda(\mathbf{B}_{\text{global}})^{\vee} + \mathbf{r}_{\text{proj}}$, where $\mathbf{r}_{\text{proj}}$ is no longer the shortest vector in the lattice coset. For $i$ and $j$ small enough, we can make the approximation that

$$ \mathbb{P}(N_{i,j} > 0) \approx \mathbb{P}(N_{i,j} = 1). \qquad (4.26) $$

Thus, the survival function of $\mathcal{D}$, knowing that the achieved decoding distance is $d_{\text{lsc}}$, can be approximated by

$$ \mathbb{P}(\mathcal{D} > T | d_{\text{lsc}}) \approx \mathbb{P}(\exists(i, j) \in \mathcal{E}(T) : N_{i,j} > 0) \qquad (4.27) $$

$$ \approx \min \left( 1, \mathbb{E} \left( \sum_{\substack{(i,j) \in \mathcal{E}(T) \\ (i^2, j^2) \in \mathbb{N}^2}} N_{i,j} \right) \right) \qquad (4.28) $$

where

$$ \mathcal{E}(T) \triangleq \{(i, j) \in \mathbb{R}_+^2 : N \cdot \Phi_{d_{\text{lsc}}}(i, j) \ge T\}. \qquad (4.29) $$

We have already observed that when we make the correct guess, the probability $\mathbb{P}(N_{i,j} > 0)$ is particularly high for a pair $(i, j)$ close to $(\sqrt{\frac{\alpha\beta_{\text{sieve}}}{2}}, \sqrt{\frac{\alpha n_{\text{lsc}}}{2}})$. Now, in the case where we make a wrong guess – that is $(\tilde{\mathbf{s}}_{\text{enu}}, \tilde{\mathbf{s}}_{\text{fft}}) \neq (\mathbf{s}_{\text{enu}}, \mathbf{s}_{\text{fft}})$ – then we have

$$ \mathbb{E} \left( \sum_{\substack{(i,j) \in \mathcal{E}(T) \\ (i^2, j^2) \in \mathbb{N}^2}} N_{i,j} \right) \approx \frac{\int_{\mathcal{E}(T)} \mathrm{Vol}(\mathrm{Sphere}_x^{\beta_{\text{sieve}}}) \cdot \mathrm{Vol}(\mathrm{Sphere}_y^{n_{\text{fft}}}) d(x, y)}{\mathrm{Vol}(q\Lambda(\mathbf{B}_{\text{global}})^{\vee})} \\ = \int_{\mathcal{E}(T)} \frac{\mathrm{Vol}(\mathrm{Sphere}_x^{\beta_{\text{sieve}}}) \cdot \mathrm{Vol}(\Lambda(\mathbf{B}'))}{q^{\beta_{\text{sieve}}} \cdot n_{\text{lsc}}} \cdot \frac{\mathrm{Vol}(\mathrm{Sphere}_y^{n_{\text{fft}}} \cdot \mathrm{Vol}(\Lambda(\mathbf{B}_{\text{lsc}})))}{q^{n_{\text{fft}}}} d(x, y) $$

The volume of $\Lambda(\mathbf{B}')$ is provided in Lemma 2.9, while the volume of $\Lambda(\mathbf{B}_{\text{lsc}})$ is $q^{n_{\text{fft}}-k_{\text{fft}}}$. Meanwhile, the integral can be evaluated numerically. Note that the Gaussian Heuristic is necessary here, as $q$-ary lattices only behave approximately like random lattices.

Finally, under Model 4.7, $P_{\text{wrong}}$ is the convolution product of the probability density function of the normal distribution $N(0, N/2)$ and the survival function of $\mathcal{D}$, that is given by

$$ \mathbb{P}(\mathcal{D} > T) = \int_{0}^{\infty} \psi_{\text{lsc}}(d_{\text{lsc}}) \cdot \mathbb{P}(\mathcal{D} > T | d_{\text{lsc}}) dd_{\text{lsc}} $$

**Validating our Analysis Through Simulations.** We verify here the soundness of Approximation 4.9 for $P_{\text{wrong}}$, which is crucial for estimating the number of false candidates. To this end, we implemented and ran Algorithm 3.1, computing an experimental value for $P_{\text{wrong}}$, namely

$$ \frac{|\{z \in \mathbb{Z}_q^{k_{\text{fft}}} : F_0^{(\text{lsc})}(z) \ge T\}|}{q^{k_{\text{fft}}}} $$ for different values of $T$. We plotted it against its theoretical approximation in Figure 4.1. Notably, we found that the experimental and theoretical estimates are in agreement, though the plot on the right suggests that our analysis may be slightly optimistic.

We used the g6k library [ADH$^{+19}$] to generate short vectors in a lattice and used polar codes, along with the decoder described in Section 3.3, for the auxiliary code $C_{\text{lsc}}$. We provide the program used to generate Figure 4.1 in the GitHub repository$^{13}$.

<footnote n="13">13 https://github.com/kevin-carrier/CodedDualAttack/tree/main/verifyModel</footnote>
analysis of [BDGL16] assumes an ideal case, underestimating the decoding cost and overlooking the suboptimal rate-distortion of product codes. Specifically, [Duc22] estimates that for a sieving dimension of 380, the complexity of the nearest-neighbor search increases by a factor of about $2^6$. Here we kept the same way of computing the costs as in Matzov's paper [MAT22] to keep a fair comparison with their work. Delving further into this topic and replacing for instance the simple product codes with a better approach is outside the scope of this work.

For the same reasons, we only consider the classical RAM model. Adapting our analysis to a more realistic memory access model, such as the one presented in [Jaq24], is left as future work. Furthermore, we do not compare our results with the state-of-the-art primal attacks. A fair comparison would require substantial effort, as it involves accounting for many confounding factors, such as those listed in [DP23b, Appendix A]. Achieving a more precise estimate – down to the gate count level, as done for instance in [SAB+20] – would demand a significantly more in-depth analysis, which we leave as future work given the already considerable length of this paper. Once again, our goal here is to provide a proof of concept for dual lattice attacks and to help resolve the controversy surrounding them. In line with this objective, we deliberately chose to work with a relatively simple and likely suboptimal dual attack algorithm. There are several potential avenues for improving it, including: (i) allowing false positives and adding a verification step to filter them out, (ii) combining modulus switching with our technique, as it would enable computations in characteristic 2, thereby allowing for a much more efficient fast Fourier transform, (iii) replacing the naive product code in the sieving procedure by a better quantizer... We leave these improvements for future work, as they fall outside the scope of this paper.

**Evaluating the Complexity of our Dual Attack.** We optimize the time complexity of Algorithm 3.1, as established in Theorem 4.1, under the assumptions outlined in Lemma 3.2. We assume that $1 - \mu \approx 1$, and we constrain the parameters $N$ and $T$ such that $\varepsilon := R P_{\text{wrong}} q^{k_{\text{ft}}}$ remains close to 1; in particular, in our setting, $\eta$ is always greater than 0.62. Additionally, we select $T$ following Approximation 4.8, ensuring that $P_{\text{good}} \approx \frac{1}{2}$. At the same time, we ensure that $\varepsilon$ remains close to 0. These choices guarantee that the overall success probability<fnref n="14" /> of our algorithm is lower-bounded by approximately $0.31 - \varepsilon \approx 0.31$.

Our complexity results are summarized in the last three columns of Table 5.1. The associated parameters are given in Appendix C, Table C.1 and some relevant intermediate quantities are summarized in Appendix C, Table C.2. Note that the quantity $d_{\text{lat}}$ is defined from the other parameters as in Lemma 2.8. The mean $\mu_{\text{lsc}}$ of the decoding distance $d_{\text{lsc}}$ and its standard deviation $\sigma_{\text{lsc}}$ are computed by choosing an $[n_{\text{fft}}, k_{\text{fft}}]_q$ polar code and by decoding many (a thousand) random words of $Z_q^{n_{\text{fft}}}$. For all instances of KYBER, we used a list size of $L = 1$ in the decoder (see Section 3.3, Lemma 3.3). This list size allows us to achieve a decoding distance close enough to the optimal decoding distance $d_{\text{GV}} \triangleq \sqrt{\frac{n_{\text{fft}}}{2\pi e}} q^{1 - \frac{k_{\text{fft}}}{n_{\text{fft}}}}$ without incurring additional cost in the complexity. Finally, we provide in the GitHub repository<fnref n="15" /> a file verifying that our parameters achieve the complexity claims and verify all the constraints.

## Acknowledgment

We would like to thank Léo Ducas for helpful discussions and for pointing out, in an older version of the paper, that we made an error by overlooking the fact that MATZOV sieving is performed on a sublattice rather than the full lattice.

<footnote n="14">¹⁴ Note that in [MAT22], this success probability was approximately 0.25.</footnote>

<footnote n="15">¹⁵ https://github.com/kevin-carrier/CodedDualAttack/tree/main/OptimizeCodedDualAttack</footnote>
<table><caption>Table 5.1: The LWE parameters for KYBER, the security level required by NIST, the claimed $log_2$ complexity of MATZOV attack as given in [AS22, Table 2], and the $log_2$ complexity of our dual attack Algorithm 3.1.</caption><thead><tr><th rowspan="2">Scheme</th><th colspan="3">LWE parameters</th><th rowspan="2">Security level required by NIST</th><th colspan="3">MATZOV Complexity</th><th colspan="3">Complexity of our Algorithm 3.1</th></tr><tr><th>q</th><th>n</th><th>α</th><th>C0</th><th>CC</th><th>CN</th><th>C0</th><th>CC</th><th>CN</th></tr></thead><tbody><tr><td>KYBER-512</td><td>3329</td><td>512</td><td>3</td><td>AES-128 (143 bits)</td><td>115.4</td><td>139.2</td><td>134.4</td><td><b>121.8</b></td><td><b>139.5</b></td><td><b>134.5</b></td></tr><tr><td>KYBER-768</td><td>3329</td><td>768</td><td>2</td><td>AES-192 (207 bits)</td><td>173.7</td><td>196.1</td><td>190.6</td><td><b>173.0</b></td><td><b>195.1</b></td><td><b>189.8</b></td></tr><tr><td>KYBER-1024</td><td>3329</td><td>1024</td><td>2</td><td>AES-256 (272 bits)</td><td>241.8</td><td>262.4</td><td>256.1</td><td><b>239.0</b></td><td><b>259.7</b></td><td><b>254.6</b></td></tr></tbody></table>

## References

AD221. *Lattice Attacks on NTRU and LWE: A History of Refinements*, page 15–40. London Mathematical Society Lecture Note Series. Cambridge University Press, 2021.

ADH$^{+}$19. Martin R. Albrecht, Léo Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W. Postlethwaite, and Marc Stevens. The general sieve kernel and new records in lattice reduction. In Yuval Ishai and Vincent Rijmen, editors, *Advances in Cryptology - EUROCRYPT 2019*, pages 717–746, Cham, 2019. Springer International Publishing.

ADPS16. Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum key exchange - A new hope. In Thorsten Holz and Stefan Savage, editors, *USENIX Security 2016*, pages 327–343. USENIX Association, August 2016.

AFFP14. Martin R. Albrecht, Jean-Charles Faugère, Robert Fitzpatrick, and Ludovic Perret. modulus switching for the BKW algorithm on LWE. In Hugo Krawczyk, editor, *PKC 2014*, volume 8383 of LNCS, pages 429–445, Heidelberg, March 2014. Springer.

AGPS20a. Martin Albrecht, Vlad Gheorghiu, Eamonn Postlethwaite, and John Schanck. *Estimating Quantum Speedups for Lattice Sieves*, pages 583–613. 12 2020.

AGPS20b. Martin R. Albrecht, Vlad Gheorghiu, Eamonn W. Postlethwaite, and John M. Schanck. Estimating quantum speedups for lattice sieves. In Shiho Moriai and Huaxiong Wang, editors, *ASIACRYPT 2020, Part II*, volume 12492 of LNCS, pages 583–613. Springer, Heidelberg, December 2020.

Alb17. Martin R. Albrecht. On dual lattice attacks against small-secret LWE and parameter choices in HElib 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.

AS22. Martin R. Albrecht and Yixin Shen. Quantum augmented dual attack. Cryptology ePrint Archive, Paper 2022/656, 2022. https://eprint.iacr.org/2022/656.

BDGL16. Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. In Robert Krauthgamer, editor, *Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016*, pages 10–24. SIAM, 2016.

BV11. Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. In Rafail Ostrovsky, editor, *IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011*, pages 97–106. IEEE Computer Society, 2011.

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.

CDMT24. Kévin Carrier, Thomas Debris-Alazard, Charles Meyer-Hilfiger, and Jean-Pierre Tillich. Reduction from sparse LPN to LPN, dual attack 3.0. In Marc Joye and Gregor Leander, editors, *Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part VI*, volume 14656 of LNCS, pages 286–315. Springer, 2024.
CE01. Henry Cohn and Noam Elkies. New upper bounds on sphere packings i. *Annals of Mathematics*, 157, 10 2001.

Che13. Yuanmi Chen. Réduction de réseau et sécurité concrète du chiffrement complètement homomorphe. 2013.

Chi14. Mao-Ching Chiu. Non-binary polar codes with channel symbol permutations. In *2014 International Symposium on Information Theory and its Applications*, pages 433–437, 2014.

CS88. John H. Conway and Neil J. A. Sloane. *Sphere Packings, Lattices and Groups*, volume 290 of *Grundlehren der mathematischen Wissenschaften*. Springer, 1988.

DM90. Dan E. Dudgeon and Russell M. Mersereau. *Multidimensional Digital Signal Processing*. Prentice Hall Professional Technical Reference, 1990.

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.

Duc18. Léo Ducas. Shortest vector from lattice sieving: A few dimensions for free. In Jesper Buus Nielsen and Vincent Rijmen, editors, *Advances in Cryptology - EUROCRYPT 2018*, pages 125–145, Cham, 2018. Springer International Publishing.

Duc22. Léo Ducas. Estimating the hidden overheads in the bdgl lattice sieving algorithm. In *Post-Quantum Cryptography: 13th International Workshop, PQCrypto 2022, Virtual Event, September 28–30, 2022, Proceedings*, page 480–497, Berlin, Heidelberg, 2022. Springer-Verlag.

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.

FJ05. M. Frigo and S.G. Johnson. The design and implementation of ftftw3. *Proceedings of the IEEE*, 93(2):216–231, 2005.

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.

GJS15. Qian Guo, Thomas Johansson, and Paul Stankovski. Coded-BKW: Solving LWE using lattice codes. In *Advances in Cryptology - CRYPTO 2015*, volume 9215 of LNCS, pages 23–42, Santa Barbara, CA, USA, August 2015. Springer.

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.

Jaq24. Samuel Jaques. Memory adds no cost to lattice sieving for computers in 3 or more spatial dimensions. *IACR Communications in Cryptology*, 10 2024.

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.

LPR10. Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In *Advances in Cryptology - EUROCRYPT 2010*, volume 6110 of LNCS, pages 1–23. Springer, 2010.

MAB<sup>+22</sup>. Matzov, Daniel Apon, Daniel J. Bernstein, Carl Mitchell, Léo Ducas, Martin Albrecht, and Chris Peikert. Improved Dual Lattice Attack. https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Fm4cDfsx65s, 2022.

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

MR09. Daniele Micciancio and Oded Regev. Lattice-based cryptography. In *Post-quantum cryptography*, pages 147–191. Springer, 2009.

MT23. Charles Meyer-Hilfiger and Jean-Pierre Tillich. Rigorous foundations for dual attacks in coding theory. In *Theory of Cryptography Conference, TCC 2023*, volume 14372 of LNCS, pages 3–32. Springer Verlag, December 2023.

PS24. Amaury Pouly and Yixin Shen. Provable dual attacks on learning with errors. In Marc Joye and Gregor Leander, editors, *Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich*,
Switzerland, May 26-30, 2024, Proceedings, Part VI, volume 14656 of LNCS, pages 256-285.
Springer, 2024.

Reg05. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 84-93, 2005.

SAB+20. Peter Schwabe, Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, and Damien Stehlé. CRYSTALS-KYBER. Technical report, National Institute of Standards and Technology, 2020. available at https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions.

Sav21. Valentin Savin. Non-binary polar codes for spread-spectrum modulations. In 2021 11th International Symposium on Topics in Coding (ISTC), pages 1-5, 2021.

Sch03. Claus Peter Schnorr. Lattice reduction by random sampling and birthday methods. In Helmut Alt and Michel Habib, editors, STACS 2003, pages 145-156, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.

ŞTA09. Eren Şasoğlu, Emre Telatar, and Erdal Arıkan. Polarization for arbitrary discrete memoryless channels. In Proc. IEEE Inf. Theory Workshop- ITW, pages 144-149, October 2009.

ZF96. Ram Zamir and Meir Feder. On lattice quantization noise. IEEE Trans. Inform. Theory, 42(4):1152-1159, 1996.
# Appendix
## A Quantizers, Lossy Source Coding and Polar Codes

In this section we give more details about the construction of polar codes over $\mathbb{Z}_q$ that is mentioned in Subsection 3.3. We then verify that, when decoding random words, it is possible, to achieve a typical decoding distance which is very close to the lattice analogue of the Gilbert-Varshamov distance that we recall to be

$$ \omega \approx \sqrt{\frac{n}{2\pi e}} q^{1-\frac{k}{n}}. \qquad (A.1) $$

where $n$ and $k$ are respectively the length and the dimension of the polar code.

**Construction of Polar Codes over $\mathbb{Z}_q$**. Let assume a codeword in $\mathbb{Z}_q^n$ of which each symbol is transmitted through a Gaussian channel of standard deviation $\sigma \triangleq \frac{\omega}{\sqrt{n}}$. The polar code construction basically consists of transforming those $n$ Gaussian channels into $n$ virtual channels that are, for most of them, either of maximal or minimal entropy. The idea then is to fix (or in other words freeze) the information that will transit via the bad channels and involve the good channels for the $k$ symbols of useful information.

Our construction essentially follows the papers [ŞTA09,Chi14,Sav21]. We refer to those articles for more details about polar codes. It is a recursive construction which can be described as follows.

**Definition A.1** ((U+V, αU)-construction). Let $U$ and $V$ be two linear codes of the same length $n$ over $\mathbb{Z}_q$ and let $\alpha \in \mathbb{Z}_q^*$ be an invertible scalar. The $(U+V, \alpha V)$ is a $\mathbb{Z}_q$-linear code of length $2n$ defined by

$$ (U + V, \alpha U) \triangleq \{ (\mathbf{u} + \mathbf{v}, \alpha \mathbf{u}) : \mathbf{u} \in U \text{ and } \mathbf{v} \in V \} \qquad (A.2) $$

A polar code of length $n \triangleq 2^m$ and dimension $k$ is then defined by

**Definition A.2 (polar code).** Let $F$ be a subset of $\{0, 1\}^m$ of size $2^m - k$ and let $\alpha$ be a function mapping the binary words of length $< m$ to $\mathbb{Z}_q^*$. The polar code of length $2^m$ associated to $F$ and $\alpha$ is defined recursively by

$$ C \triangleq U_{\varepsilon} \qquad (A.3) $$

where the $U_x$ are codes of length 1 for all $\mathbf{x} \in \{0, 1\}^m$ (we denote by $\varepsilon$ the empty binary word) and are given by

$$ U_x = \begin{cases} \{0\} & \text{if } \mathbf{x} \in F \\ \mathbb{Z}_q & \text{otherwise} \end{cases} \qquad (A.4) $$

and the other $U_x$'s where $\mathbf{x}$ is a binary word of length $< m$ are defined recursively by

$$ U_x \triangleq (U_{0||\mathbf{x}} + U_{1||\mathbf{x}}, \alpha(\mathbf{x})U_{0||\mathbf{x}}). \qquad (A.5) $$

Thus, a polar code is fully defined by the set $F$ of frozen positions and the $\alpha(\mathbf{x})$'s. In [Chi14], it is admitted that choosing the $\alpha(\mathbf{x})$'s uniformly at random in $\mathbb{Z}_q^*$ is good enough. However, in [Sav21], it is shown that those coefficients can be optimized. Thereafter, we do not use the optimization technique from [Sav21] but simply try several polar codes then choose the best of them. On another hand, we classically determine the optimal frozen positions $F$ using Monte-Carlo simulation: we run many times a genie-aided decoder for estimating the probability distribution of each virtual channel then selecting the worst of them; that are the $2^m - k$ virtual channels for which the error probabilities are the highest.
**Decoding Polar Codes over $\mathbb{Z}_q$**. The Successive Cancelation (SC) decoding algorithm (see [ŞTA09,Chi14,Sav21]) can be described as a recursive decoding algorithm. For each code $U_x \subseteq \mathbb{Z}_q^{2^{m-t}}$ such that $x \in \{0, 1\}^t$ and $t \in [0, m-1]$, we decode a noisy codeword in this code by using recursively the decoders of $U_{0||x}$ and $U_{1||x}$.

Let $\mathbf{c} \triangleq (c_1, \dots, c_{2^{m-t}}) \triangleq (\mathbf{u} + \mathbf{v}, \alpha(\mathbf{x})\mathbf{u})$ be a codeword in $U_x$; i.e.

$\mathbf{u} \triangleq (u_1, \dots, u_{2^{m-t}-1})$ and $\mathbf{v} \triangleq (v_1, \dots, v_{2^{m-t}-1})$ are respectively in $U_{0||x}$ and $U_{1||x}$. Let assume that $\mathbf{c}$ is transmitted through a channel $W^{(\mathbf{x})}$; let

$$ \mathbf{y} \triangleq (y_1, \dots, y_{2^{m-t}}) \triangleq (\mathbf{y}_\ell, \mathbf{y}_r) \in \mathbb{Z}_q^{2^{m-t}-1} \times \mathbb{Z}_q^{2^{m-t}-1} \qquad (A.6) $$

be the received word. We assume that for each position $i \in [1, 2^{m-t}]$ and symbol $s \in \mathbb{Z}_q$, we know the probability that the transmitted symbol is $s$ knowing that the received one is $y_i$:

$$ \Pi_i^{(\mathbf{x})}(s) \triangleq \mathbb{P}(c_i = s|y_i) \qquad (A.7) $$

Instead of decoding directly $\mathbf{y}$, we decode first $\mathbf{y}_\ell - \alpha(\mathbf{x})^{-1}\mathbf{y}_r$ expecting to find $\mathbf{v} \in U_{1||x}$. The virtual channel through which $\mathbf{v}$ has transited is then the serialization of two $W^{(\mathbf{x})}$ channels that we denote by $W^{(1||\mathbf{x})}$. Thus for each coordinate $i \in [1, 2^{m-t}-1]$ and symbol $s \in \mathbb{Z}_q$, we have the probability

$$ \Pi_i^{(1||\mathbf{x})}(s) \triangleq \mathbb{P}(v_i = s|y_i, y_{i+2^{m-t}-1}) \qquad (A.8) $$

$$ = \sum_{s' \in \mathbb{Z}_q} \Pi_i^{(\mathbf{x})}(s+s') \cdot \Pi_{i+2^{m-t}-1}^{(\mathbf{x})}(\alpha(\mathbf{x}) \cdot s') \qquad (A.9) $$

$$ = \sum_{s' \in \mathbb{Z}_q} \Pi_i^{(\mathbf{x})}(s-s') \cdot \Pi_{i+2^{m-t}-1}^{(\mathbf{x})}(-\alpha(\mathbf{x}) \cdot s') \qquad (A.10) $$

$$ = \left( \Pi_i^{(\mathbf{x})} * \overline{\Pi}_{i+2^{m-t}-1}^{(\mathbf{x})} \right) (s) \qquad (A.11) $$

where $\overline{\Pi}_i^{(\mathbf{x})}(s) \triangleq \Pi_i^{(\mathbf{x})}(-\alpha(\mathbf{x}) \cdot s)$.

On another hand, let us assume that the decoding of $\mathbf{y}_\ell - \alpha(\mathbf{x})^{-1}\mathbf{y}_r$ has led us to the vector $\tilde{\mathbf{v}}$ that we expect to be $\mathbf{v}$ (for the genie-aided decoder used for the construction of the code, we actually take $\tilde{\mathbf{v}} = \mathbf{v}$, regardless of the result of the decoding of $\mathbf{y}_\ell - \alpha(\mathbf{x})^{-1}\mathbf{y}_r$). We now have two independent noisy versions of the same vector $\mathbf{u}$ that are $\alpha(\mathbf{x})^{-1}\mathbf{y}_r$ and $\mathbf{y}_\ell - \tilde{\mathbf{v}}$. In other words, supposing $\tilde{\mathbf{v}} = \mathbf{v}$, the vector $\mathbf{u}$ has been sent twice through the channel $W^{(\mathbf{x})}$; we denote by $W^{(0||\mathbf{x})}$ the resulting channel and for each coordinate $i \in [1, 2^{m-t}-1]$ and symbol $s \in \mathbb{Z}_q$, we have the probability

$$ \Pi_i^{(0||\mathbf{x})}(s) \triangleq \mathbb{P}(u_i = s|y_i, y_{i+2^{m-t}-1}) \qquad (A.12) $$

$$ = \frac{1}{\eta} \cdot \Pi_i^{(\mathbf{x})}(s + \tilde{v}_i) \cdot \Pi_{i+2^{m-t}-1}^{(\mathbf{x})}(\alpha(\mathbf{x}) \cdot s) \qquad (A.13) $$

where $\eta \triangleq \sum_{s' \in \mathbb{Z}_q} \Pi_i^{(\mathbf{x})}(s' + \tilde{v}_i) \cdot \Pi_{i+2^{m-t}-1}^{(\mathbf{x})}(\alpha(\mathbf{x}) \cdot s')$ is a normalization factor.

Finally, for decoding a received word $\mathbf{y} \in \mathbb{Z}_q^{2^m}$ in the code $U_\epsilon$ that has been sent through a Gaussian channel of standard deviation $\sigma$, one essentially has to compute recursively the vector probabilities $\Pi_i^{(\mathbf{x})}$ for all $t \in [1, m]$, $\mathbf{x} \in \{0, 1\}^t$ and $i \in [1, 2^{m-t}]$ using the Equations (A.11) and (A.13). Note that the initial channel $W^{(\epsilon)}$ is the original Gaussian channel; so for all $i \in [1, 2^m]$ and $s \in \mathbb{Z}_q$, we have

$$ \Pi_i^{(\epsilon)}(s) = \mathbb{P}(G_{\mathbb{Z}_q, \sigma} = y_i - s) \qquad (A.14) $$

where $G_{\mathbb{Z}_q, \sigma}$ is the modular Gaussian distribution defined as follows:
**Definition A.3 (Discrete Gaussian Distribution).** Let $\sigma > 0$ and let $S \subset \mathbb{R}$ be a discrete set. The discrete Gaussian distribution $G_{S,\sigma}$ over $S$ is defined by:

$$ \mathbb{P}(G_{S,\sigma} = x) \triangleq \frac{\rho_{\sigma}(x)}{\sum_{y \in S} \rho_{\sigma}(y)} \qquad (A.15) $$

where $\rho_{\sigma}(x) \triangleq \exp(-x^2/2\sigma^2)$ is the probability density function of the normal distribution $N(0, \sigma^2)$.

In particular, if $S \triangleq \mathbb{Z}_q$ then we speak of modular Gaussian distribution and for all $x \in \mathbb{Z}_q$, we have

$$ \mathbb{P}(G_{\mathbb{Z}_q, \sigma} = x) = \mathbb{P}(G_{\mathbb{Z}, \sigma} \in x + q\mathbb{Z}) = \frac{\sum_{u \in x + q\mathbb{Z}} \rho_{\sigma}(u)}{\sum_{y \in \mathbb{Z}} \rho_{\sigma}(y)} \qquad (A.16) $$

where $x$ is assimilated to any of its representatives.

When arriving to the codes on the leaves – that are the codes $U_x$ such that $x \in \{0, 1\}^m$ – then we can exhaustively decode $U_x$:

1. if $x \in F$ (meaning the corresponding symbol is frozen) then the only possible codeword in $U_x$ is the symbol 0,

2. if $x \notin F$, then we choose the maximum likelihood codeword in $U_x$ that is the symbol $s$ for which $\Pi_1^{(x)}(s)$ is the greatest.

The running time of Successive Cancelation decoding is given by the following lemma:

**Lemma A.4 (Complexity of the SC decoder).** Assuming $q$ is a power of 2. The running time for decoding a word in a polar code of length $2^m$ and dimension $k$ over $\mathbb{Z}_q$ is:

$$ T_{\text{SC}} \le 3 \cdot \left( C_{\text{add}} \cdot N_{\text{FFT}}^{(\text{add})}(q) + C_{\text{mul}} \cdot N_{\text{FFT}}^{(\text{mul})}(q) \right) \cdot m \cdot 2^m \qquad (A.17) $$

where $C_{\text{add}}$ and $C_{\text{mul}}$ are the costs of an addition and a multiplication, respectively, and $N_{\text{FFT}}^{(\text{add})}(q)$ and $N_{\text{FFT}}^{(\text{mul})}(q)$ are the number of additions and multiplications needed to achieve a discrete Fourier transform over $\mathbb{Z}_q$ (Proposition 2.11 provides those numbers for $q = 3329$, which were computed using the FFTW software [FJ05]).

*Proof.* For all $t \in [1, m]$, $x \in \{0, 1\}^t$ and $i \in [1, 2^{m-t}]$ – i.e. for $m \cdot 2^m$ triplets $(t, x, i)$ – we can compute the vector of probabilities $\Pi_i^{(x)}$ with at most $3 \cdot q \cdot \log_2(q)$ multiplications. Indeed, we either have to compute Equation (A.11) or Equation (A.13). In the first case, it is a convolution; this can be done with the help of three fast Fourier transforms, with each FFT requiring $N_{\text{FFT}}^{(\text{add})}(q)$ additions and $N_{\text{FFT}}^{(\text{mul})}(q)$ multiplications. In the second case, we only have to do $2 \cdot q$ multiplications and $q$ additions, which is less than the cost of a convolution.

*Remark A.5.* We could reduce the cost of the SC decoder by considering the vectors of LLR (Log Likelihood Ratio) instead of the vectors of probabilities. This trick allows to transform multiplications into additions.

**List Decoding Using Probabilistic SC Decoder.** We can modify the above SC decoder to obtain a probabilistic decoder. To this end, when decoding non-frozen symbols in the codes on the leaves $U_x$ where $x \in \{0, 1\}^m \setminus F$, then output the symbol $s$ according to the distribution $\Pi_1^{(x)}$ instead of returning the one with the best probability. Note that as $m$ tends to infinity and $k/2^m$ remains constant, for $x \in \{0, 1\}^m \setminus F$, the channels $W^{(x)}$'s have capacity very close to 1 and for $x \in F$, they have capacity very close to 1. Because of this polarization phenomenon, we can prove similarly to [KU10] that our probabilistic SC decoder achieves an average decoding distance

$$ d = \sqrt{\frac{2^m}{2\pi e}} \cdot q^{1-\frac{k}{2^m}} \cdot (1 + o(1)) \qquad (A.18) $$
when decoding a random vector in $\mathbb{Z}_q^{2m}$.

To turn this probabilistic SC decoder into a list decoder, one only has to running it $L$ times then choosing the codeword that minimizes the decoding distance. The complexity of a such algorithm is essentially $L$ times the complexity of the SC decoder given by Lemma A.4. Note that, contrary to some more classical list decoders of polar codes, the $L$ decoding procedures of our algorithm can be trivially parallelized.

**Punctured Polar Code.** The polar codes construction above is about codes of length that are a power of 2. In our case, we may require codes of other length. A simple way for reducing the length of a code without changing its dimension is to puncture it. Let $n, k$ be two positive integers. We build a linear code of length $n$ and dimension $k$ by puncturing a polar code of length $2^m$ and dimension $k$ where $m \triangleq \lceil \log_2(n) \rceil$. Let denote by $\ell \triangleq 2^m - n$ the number of symbol to puncture. The puncturing operation essentially consists of ignoring the $\ell$ first symbols of the codeword; that is equivalent to suppose that the $\ell$ first physical channels through which transit the codewords are of maximal entropy:

$$ \Pi_i^{(\varepsilon)}(s) \triangleq \frac{1}{q} \quad \forall i \in [1, \ell] \qquad (A.19) $$

Note that we made this assumption both for the decoder and also for the genie-aided decoder used to determine the frozen positions.
## B An Intuition about the Distinguishability of the Good Guess.

An important insight from Approximation 4.6 is that the score $F_{s_{enu}}^{(lsc)}(G^\top \tilde{s}_{fft})$ depends on the length enumerator of the vectors in the coset $q\Lambda(B_{global})^\vee + \mathbf{r}_{proj}$. Specifically, for the good guess $(\tilde{s}_{enu}, \tilde{s}_{fft}) = (s_{enu}, s_{fft})$, this lattice coset contains a particularly short vector $\mathbf{r}_{proj} = (\mathbf{P}(e, s_{lat}), s_{fft})$ where $\mathbf{P} \triangleq \mathbf{B}'(\mathbf{B}'^\top \mathbf{B}')^{-1} \mathbf{B}'^\top$ is the orthogonal projection onto span($\mathbf{B}'$). In contrast, for wrong guesses where $(\tilde{s}_{enu}, \tilde{s}_{fft}) \neq (s_{enu}, s_{fft})$, the shortest vector is no longer $\mathbf{r}_{proj}$. This observation provides a preliminary answer to the indistinguishability question posed in [DP23b]. Indeed, we cannot distinguish the good guess from the wrong ones if the length of $(\mathbf{P}(e, s_{lat}), s_{fft})$ is greater than the length of the shortest vector in $q\Lambda(B_{global})^\vee + \mathbf{r}_{proj}$. Given that the coordinates of $(e, s_{lat}, s_{fft})$ are i.i.d. random variables following a centered binomial distribution with parameter $\alpha$, we estimate the length of $(\mathbf{P}(e, s_{lat}), s_{fft})$ to be

$$ \| (\mathbf{P}(e, s_{lat}), s_{fft}) \| \approx \sqrt{\frac{\alpha(\beta_{sieve} + n_{fft})}{2}}. \qquad (B.1) $$

On the other hand, if $\Lambda(B_{global})$ is treated as a random lattice with volume $V_{global} \triangleq \mathrm{Vol}(\Lambda(B_{global})) = \mathrm{Vol}(\Lambda(B')) \cdot \mathrm{Vol}(\Lambda(B_{lsc}))$, then, using the Gaussian Heuristic, we can estimate the length of the shortest vector in the lattice coset to be

$$ \lambda_1 (q\Lambda(B_{global})^\vee + \mathbf{r}_{proj}) \approx \frac{q}{V_{global}^{\frac{1}{\beta_{sieve} + n_{fft}}}} \cdot \sqrt{\frac{\beta_{sieve} + n_{fft}}{2\pi e}}. \qquad (B.2) $$

However, we don't consider just one such coset, but rather $M \triangleq R \cdot q^{k_{fft}}$. Therefore, the probability of having an even smaller shortest vector in one of the cosets is not negligible. In [DP23b, Section 4.3], the shortest vector, across all cosets, is estimated to be

$$ \approx \frac{\lambda_1 (q\Lambda(B_{global})^\vee + \mathbf{r}_{proj})}{M^{\frac{1}{\beta_{sieve} + n_{fft}}}}. \qquad (B.3) $$

Table B.1 compares (B.1) and (B.3) for the parameters derived for KYBER in Section 5.

<table><caption>Table B.1: Comparison between the estimated length of $(\mathbf{P}(e, s_{lat}), s_{fft})$ and the estimated length of the shortest vector in all the cosets $q\Lambda(B_{global})^\vee + \mathbf{r}_{proj}$, based on the parameters provided in Table C.1 (Appendix C). We are outside the contradictory regime raised in [DP23b] as soon as $Eq.(B.1) < Eq.(B.3)$.</caption><thead><tr><th rowspan="2">Scheme</th><th colspan="2">C0</th><th colspan="2">CC</th><th colspan="2">CN</th></tr><tr><th>Eq. (B.1)</th><th>Eq.(B.3)</th><th>Eq. (B.1)</th><th>Eq.(B.3)</th><th>Eq. (B.1)</th><th>Eq.(B.3)</th></tr></thead><tbody><tr><td>KYBER-512</td><td>25.42</td><td>26.61</td><td>25.66</td><td>27.21</td><td>25.57</td><td>26.58</td></tr><tr><td>KYBER-768</td><td>25.63</td><td>26.70</td><td>25.82</td><td>27.23</td><td>25.75</td><td>27.19</td></tr><tr><td>KYBER-1024</td><td>30.25</td><td>31.17</td><td>30.38</td><td>31.99</td><td>30.48</td><td>32.34</td></tr></tbody></table>

In Subsection 4.2, we refine these calculations to provide an accurate approximation of $F_{s_{enu}}^{(lsc)}(G^\top \tilde{s}_{fft})$, which we validate through simulations. In particular, we no longer assume that $\Lambda(B_{global})$ is a random lattice of volume $V_{global}$; instead, we separately analyze the first $\beta_{sieve}$ coordinates and the last $n_{fft}$ coordinates.
## C Parameters Tables Related to the Complexities Given In Table 5.1.

<table><caption>Table C.1: Parameters to obtain Table 5.1.</caption><thead><tr><th></th><th>m</th><th>β<sub>bkz</sub></th><th>β<sub>sieve</sub></th><th>n<sub>enu</sub></th><th>n<sub>fft</sub></th><th>k<sub>fft</sub></th><th>n<sub>lat</sub></th><th>d<sub>lat</sub></th><th>μ<sub>lsc</sub></th><th>σ<sub>lsc</sub></th><th>log<sub>2</sub>(N)</th><th>log<sub>2</sub>(T)</th></tr></thead><tbody><tr><td rowspan="3">CO:</td><td>KYBER-512</td><td>488</td><td>393</td><td>393</td><td>1</td><td>38</td><td>8</td><td>473</td><td>2882.14</td><td>975.17</td><td>42.11</td><td>81.55</td><td>43.82</td></tr><tr><td>KYBER-768</td><td>667</td><td>588</td><td>588</td><td>6</td><td>69</td><td>12</td><td>693</td><td>4401.02</td><td>1741.80</td><td>48.28</td><td>122.02</td><td>64.69</td></tr><tr><td>KYBER-1024</td><td>920</td><td>815</td><td>815</td><td>9</td><td>100</td><td>17</td><td>915</td><td>5190.00</td><td>2134.08</td><td>45.25</td><td>169.13</td><td>88.47</td></tr><tr><td rowspan="3">CC:</td><td>KYBER-512</td><td>475</td><td>384</td><td>387</td><td>5</td><td>52</td><td>9</td><td>455</td><td>2706.86</td><td>1528.73</td><td>47.38</td><td>80.31</td><td>43.31</td></tr><tr><td>KYBER-768</td><td>636</td><td>581</td><td>574</td><td>6</td><td>93</td><td>14</td><td>669</td><td>4015.56</td><td>2410.56</td><td>46.47</td><td>119.12</td><td>63.01</td></tr><tr><td>KYBER-1024</td><td>802</td><td>811</td><td>792</td><td>10</td><td>131</td><td>19</td><td>883</td><td>4683.71</td><td>2956.65</td><td>50.05</td><td>164.35</td><td>85.86</td></tr><tr><td rowspan="3">CN:</td><td>KYBER-512</td><td>457</td><td>384</td><td>388</td><td>4</td><td>48</td><td>9</td><td>460</td><td>2830.06</td><td>1292.55</td><td>39.26</td><td>80.51</td><td>43.42</td></tr><tr><td>KYBER-768</td><td>682</td><td>583</td><td>577</td><td>8</td><td>86</td><td>13</td><td>674</td><td>4083.09</td><td>2309.88</td><td>57.72</td><td>119.74</td><td>63.50</td></tr><tr><td>KYBER-1024</td><td>782</td><td>816</td><td>797</td><td>6</td><td>132</td><td>19</td><td>886</td><td>4678.80</td><td>2997.51</td><td>46.56</td><td>165.39</td><td>86.37</td></tr></tbody></table>

<table><caption>Table C.2: Intermediate results for Table 5.1. We recall that $P_{good} \approx 0.5$. $\eta$ and $\epsilon$ are defined in Lemma 3.2.</caption><thead><tr><th></th><th>log<sub>2</sub>(P<sub>wrong</sub>)</th><th>log<sub>2</sub>(R)</th><th>log<sub>2</sub>(T<sub>sample</sub>)</th><th>log<sub>2</sub>(N · T<sub>dec</sub>)</th><th>log<sub>2</sub>(T<sub>FFT</sub>)</th><th>η</th><th>log<sub>2</sub>(ε)</th></tr></thead><tbody><tr><td rowspan="3">CO:</td><td>KYBER-512</td><td>-103.25</td><td>2.84</td><td>115.76</td><td>118.95</td><td>112.13</td><td>0.91</td><td>-6.81</td></tr><tr><td>KYBER-768</td><td>-220.73</td><td>9.49</td><td>172.70</td><td>160.64</td><td>159.52</td><td>0.69</td><td>-70.83</td></tr><tr><td>KYBER-1024</td><td>-295.30</td><td>13.74</td><td>238.98</td><td>207.75</td><td>218.53</td><td>0.62</td><td>-82.65</td></tr><tr><td rowspan="3">CC:</td><td>KYBER-512</td><td>-119.57</td><td>9.39</td><td>139.51</td><td>117.71</td><td>124.00</td><td>0.66</td><td>-4.87</td></tr><tr><td>KYBER-768</td><td>-177.79</td><td>9.49</td><td>194.81</td><td>157.74</td><td>183.15</td><td>0.73</td><td>-4.49</td></tr><tr><td>KYBER-1024</td><td>-244.03</td><td>15.15</td><td>259.35</td><td>204.17</td><td>242.09</td><td>0.63</td><td>-6.57</td></tr><tr><td rowspan="3">CN:</td><td>KYBER-512</td><td>-120.51</td><td>7.71</td><td>143.30</td><td>117.91</td><td>124.00</td><td>0.71</td><td>-7.49</td></tr><tr><td>KYBER-768</td><td>-225.52</td><td>12.32</td><td>189.78</td><td>158.36</td><td>171.34</td><td>0.63</td><td>-61.09</td></tr><tr><td>KYBER-1024</td><td>-240.59</td><td>9.49</td><td>254.44</td><td>205.21</td><td>242.09</td><td>0.76</td><td>-8.78</td></tr></tbody></table>