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

HAL
open science

# Avengers assemble! Supervised learning meets lattice reduction

Pierre-Alain Fouque, Damien Marion, Quyen Nguyen, Alexandre Wallet

► To cite this version:

Pierre-Alain Fouque, Damien Marion, Quyen Nguyen, Alexandre Wallet. Avengers assemble! Supervised learning meets lattice reduction. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2025, 2025, pp.409 - 436. 10.46586/tches.v2025.i4.409-436. hal-05455454

HAL Id: hal-05455454

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

Submitted on 13 Jan 2026

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

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

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Avengers assemble!
Supervised learning meets lattice reduction

A single power trace attack against CRYSTALS-KYBER Key Generation

Pierre-Alain Fouque<fnref n="1" />, Damien Marion<fnref n="1" />, Quyen Nguyen<fnref n="2" /> and Alexandre Wallet<fnref n="3" />

**Abstract.** In this paper, we attack KYBER's key-generation algorithm using power analysis and lattice reduction. More specifically, we target the Centered Binomial Distribution (CBD) sampler which generates the secret data of the underlying Learning With Error (LWE) instance. From a side-channel perspective, our attack uses a single trace, leveraging classifiers developed through supervised learning. We enhance the classification with the AdaBoost strategy, which provides more reliable results and exploitable statistics, enabling the identification of error-free classified samples. In optimal scenarios, our classifiers, combined with the outputted statistics, allow us to recover up to 68% of the secret key's coefficients from the trace, ensuring that these recovered coefficients are error-free. In such cases, we show that the secret keys can be recovered by Gaussian elimination over a finite field in a few seconds. For less advantageous cases, we assess the block-size in lattice reduction that would complete the key recovery, providing a fine-grained trade-offs between the correctly guessed proportion and the block-size, based on standard estimates. Finally, we conducted large-scale experiments, from power traces to secret key recovery (for most of the instances) under a threshold of 18 hours, targeting all three KYBER's security levels. Our average rate of success across all security level is more than 96%.

**Keywords:** KYBER · Post-quantum security · Side-channel attack · Single trace analysis · Deep learning

# 1 Introduction

CRYSTALS-KYBER is a post-quantum key-encapsulation mechanism (KEM) recently standardized by the NIST as ML-KEM [oSN23]. At its core, this KEM relies on a public-key encryption (PKE) founded on the hardness of the (Module) Learning With Errors ((M)LWE) problem. The assumption is that, given a “noisy” linear system<fnref n="1" />, $(\mathbf{A}, \mathbf{b} = \mathbf{A}\mathbf{s}+\mathbf{e})$ over a finite field $\mathbb{Z}_q$, it is difficult to recover $\mathbf{s}$ or the noise vector $\mathbf{e}$. Since its presentation to the community [BDK+17], the scheme has been at the center of attention from all aspects of cryptographic security: cryptanalysis, side-channel analysis, fault injection,... and many of its components have been subjected to concrete attacks with various degrees of success (e.g. [PP19, PPM17, RRCB20, XPR+21]). As far as side-channel attacks go against KYBER, the data extracted from side-channel often give *partial* information on the secret data $(\mathbf{s}, \mathbf{e})$, which may or may not be enough to claim a complete key recovery. Formally, this relates to a variant of LWE “with side information” – coincidentally attracting a lot of

<footnote n="1">¹ Univ Rennes, CNRS, Inria, IRISA, Rennes, France
{pierre-alain.fouque,damien.marion}@irisa.fr</footnote>

<footnote n="2">² IDEMIA Secure Transactions, Courbevoie, France, thi.nguyen@idemia.com</footnote>

<footnote n="3">³ PQShield Ltd., Oxford, United Kingdom, alexandre.wallet@pqshield.com</footnote>

<footnote n="1">¹More precisely, the term “module” refers to the strong structure in the matrix **A**.</footnote>
attention recently in theoretical cryptography [LKK$^{+}$18, CKK$^{+}$21, KLSS23]. As formalized in [DSDGR20], in a side-channel context one can represent these partial information as *hints* on $(\mathbf{s}, \mathbf{e})$, and many of such hints should make the life of an attacker easier. However, while side-channel analysis can provide the attacker with such hints, they often need to resort to *lattice reduction* techniques to finalize the key recovery, and [DSDGR20, DGHK23] provided a (rather theoretical) framework to describe this situation. In any case, this means that a combination of cryptanalysis techniques and side-channel analysis is often needed to practically break KYBER. Our work continues in this direction and provides an (often) successful set of key recovery attacks, for all security parameters of KYBER and a large number of instances.

The LWE instance in KYBER is generated by resorting to a Centered Binomial Distribution (CBD) sampler, outputting vectors of length $n = 256k, k \in \{2, 3, 4\}$ with coordinates distributed binomially (as the name suggests) in small integer intervals $[-\eta, \eta], \eta \in \{2, 3\}$. The CBD algorithm intervenes in the key-generation algorithm for the PKE but also in the Encaps algorithm, as a mean of sampling “small randomness”. To the best of our knowledge, this algorithm was never targeted by any side-channel attacks, and in some implementations, it is not protected$^2$. While there can be supporting arguments in favor of whether or not this particular step should be protected from side-channel adversaries depending on the context, our attack combines a *single* trace power analysis against the CBD in the key-generation algorithm with the lattice reduction (or sometimes, just the elementary Gaussian elimination) to fully recover the secret key in short time, with modest computing resources. Although we did not extend our attack to the Encaps algorithm, the side-channel aspect of our attack – relying on classifiers developed through supervised learning to exploit CBD leakage in power traces – could also be applied to the CBD calls in the Encaps algorithm.

**Lattice reduction to attack Kyber.** Underlying KYBER is a LWE instance $(\mathbf{A}, \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}) \mod q) \in \mathbb{Z}_q^{n \times n} \times \mathbb{Z}_q^n$ with small secret $\mathbf{s}$ and error $\mathbf{e}$. The usual approach to recover $\mathbf{s}$, known as the *primal attack*, is to find the short vector $\mathbf{x} = (\mathbf{e}^t, \mathbf{s}^t, 1) \in \mathbb{Z}^{2n+1}$ in the lattice constructed from $(\mathbf{A}, \mathbf{b})$ via lattice block-reduction algorithms (such as BKZ or one of its many variants$^3$). Namely, the lattice of interest is generated from the rows of the following matrix

$$ \mathbf{B} = \begin{bmatrix} q\mathbf{I}_n & \mathbf{0} & \mathbf{0} \\ -\mathbf{A}^t & \mathbf{I}_n & \mathbf{0} \\ -\mathbf{b}^t & \mathbf{0} & \mathbf{1} \end{bmatrix} \in \mathbb{Z}_q^{2n+1} \times \mathbb{Z}_q^{2n+1}. $$

From the LWE equation, we can verify that $\mathbf{x}$ is a short vector of the lattice. If the block-size $\beta$ is large enough, BKZ – $\beta$ can gradually reduce the input basis $\mathbf{B}$ until $\mathbf{x}$ appears as a row vector in the reduced basis. The larger the dimension and the block-size are, the longer time the algorithm needs to finish$^4$. The parameter $\beta$ is usually predicted following a cost-model for BKZ against LWE, summed up by a nowadays standard inequality (recalled in Section 2.4).

Now if the attacker is given *hints* on $(\mathbf{s}, \mathbf{e})$, such as many inner products of the shape $h = \langle \mathbf{s}, \mathbf{v} \rangle$ with known $\mathbf{v}$ and $h$, this should intuitively reduce the difficulty of solving this LWE-with-hints instance.

**From guesses of the classifier to LWE hints.** More precisely, as defined in [DSDGR20], a hint relates to an inner product $h = \langle (\mathbf{s}, \mathbf{e}), \mathbf{v} \rangle$, for a known $\mathbf{v}$: if $h$ is known exactly, we

<footnote>$^2$A possible argument supporting this decision, quoting Joppe W. Bos et al. [BGR$^{+}$21], is that the key generation often happens once-and-for-all, and that masking “is commonly aimed at mitigating multi-trace attacks”.</footnote>

<footnote>$^3$Typically, one can use fplll's implementation [dt23] of BKZ or the corresponding SAGEMATH module.</footnote>

<footnote>$^4$Parameters of LWE schemes are set to make such computations infeasible in human time — see also Section 2.4 for more details.</footnote>
say that it is a *perfect* hint; if $h$ is known only modulo another integer $q'$, it is a *modular* hint; lastly, if a noisy version of $h$ is known, it is called a *noisy* hint (or an approximate hint). From [DSDGR20], perfect and modular hints are clearly interesting: the former reduces the dimension of the instance, and the latter implies that the lattice reduction can be performed instead in a lattice that has a larger volume<fnref n="5" /> than the one underlying KYBER. In this work, the typical example of a hint is a value of a coordinate $\mathbf{s}_i = \langle \mathbf{s}, \mathbf{b}_i \rangle$ (where $\mathbf{b}_i$ is a canonical basis vector), guessed by the trained classifier after monitoring one execution of the key generation algorithm. If the confidence in this error-free guess is high, we consider it as a perfect hint and process it: this means that we modify the basis $\mathbf{B}$ to include this new information before starting lattice reduction.

If the confidence is smaller, due to Hamming weight leakage modeling (see Section 3.5), our classifier gives us more than one possible guess; then the likelihood of the classifier guessing wrongly makes the hint rather a noisy one. Generally, such approximate hints are common in side-channel attacks. Although this situation can be modelled geometrically [DSDGR20, DGHK23], we do not consider such hints in this work (in particular, we do not process them or try to estimate their impact on the hardness of secret recovering). To sum-up, our classifier gives us many perfect and noisy hints from the side-channel attack, however, in this work, we are only interested in exploiting perfect hints, whose quantity is practically enough for almost all of our later secret recoveries via linear algebra or lattice reduction. We now describe our methodology and results in more details.

## 1.1 Contributions

**Main contribution: a full key recovery with a single power trace.** The process is first summarized as follows, and then detailed item by item.

1. Our side-channel attack targets a single power trace of the CBD sampler during the execution of KYBER's key generation. The trace is fed to a simple supervised learning model, resulting in high-accuracy classifiers for KYBER key's coefficient signs. Comparing different approaches regarding the trust in the outputted statistics, we discover that the AdaBoost strategy gives the best results in terms of highly-trustable, high-accuracy classifiers to distinguish coefficients of the same sign group.

2. Depending on the proportion of coefficients in $(\mathbf{s}, \mathbf{e})$ that is guessed by our classifier, we identify two regimes. If more than half of $(\mathbf{s}, \mathbf{e})$ are guessed, we recover the remaining values by Gaussian elimination. If more than ≈ 37% are guessed, standard lattice reduction tools with small computational power complete the recovery.

3. We provide theoretical and experimental estimates (Figure 10) of the required lattice reduction block-size as a function of the proportion of guessed values in $(\mathbf{s}, \mathbf{e})$. Following these models, we demonstrate experimentally a large number of successful key recoveries.

4. These steps yields a *complete* practical attack, from training to key recovery. It is, to our knowledge, the first single-trace side-channel attack that combines hints extracted from real power traces with lattice reduction. Our attack achieves a very high success rate (more than 96% in average), against all KYBER's security levels – see Figure 11.

### 1.1.1 Conducting the training phase and improving trust

In our supervised learning phase, we train models on a learning dataset and then apply these models to a separate testing dataset. We collected the data from four different

<footnote n="5">⁵As we recall in Section 2.4, a larger volume implies an easier primal attack.</footnote>
chips of the same model to test the portability of our attack. It is commonly accepted
in side-channel attacks that a real-world attack often involves having full control over
a clone of the target device, as demonstrated in [RLMI21]. In our context of targeting
software implementations, the resulting power traces have a good signal-to-noise ratio, so
the main challenge was not achieving high accuracy but building distinguishers that we
can “trust”. In fact, for the remaining lattice reduction, we must be sure of our results
since we do not tolerate errors. To achieve this, we end up with decision tree classifiers
(composed of multiple trees) with the AdaBoost strategy. Compared to one of the most
commonly used methods in side-channel analysis, Templates [CRR02], which we directly
compare against, as well as classical decision trees (without boosting), our approach allows
us to take advantage of the outputted statistics to ensure the classification. In this way,
the side-channel step of our attack results in guesses for all coefficients. These guesses
can be perfect, meaning that the coefficient is recovered accurately (there is only one
guessed possibility for the coefficient), or they can indicate two, three or four possibilities
(only for KYBER-512, where $\eta_1 = 3$). Furthermore, we open-source our data and code$^6$,
encompassing side-channel analysis methodologies and reduction techniques.

1.1.2 Formalizing the impact of hints on the hardness of key recovery

Formally, the integration of perfect hints on (s, e) into the LWE instance is related to the
intersections between lattices or hyperplanes as shown in [DSDGR20, MN23]. "Processing"
these hints means building another matrix B'; if originally we would have needed to
run BKZ-β on B, now we expect that running BKZ-β' on B' with β' < β is enough
to recover the missing part of the secret. In our case, where the perfect hints resulted
from the side-channel attack are actual coordinates of (s, e), the processing firstly involves
removing h<sub>s</sub> columns (corresponding to h<sub>s</sub> recovered coordinates of s) and keeping h<sub>e</sub> rows
 corresponding to h<sub>e</sub> recovered coordinates of e) in A. This yields a new system of h<sub>e</sub>
linear equations with n - h<sub>s</sub> remaining unknown coordinates of s over Z<sub>q</sub> - see Figure 8
for pictorial description. For the sake of re-usability, we formalize these observations in
Section 4 and provide mathematical proofs in Appendix A. Next, we observe different
regimes which lead to different attacks:

* "Way too many hints:" if $h_e \ge n - h_s$, the system can be directly solved by Gaussian elimination ("Linear algebra") over $\mathbb{Z}_q$ (Section 4.1).

* Else we have $h_e + h_s < n$ (Section 4.2). Then, Gaussian elimination transforms the system into another LWE instance with a smaller $(n - (h_s + h_e))$-dimensional secret, and an associated matrix $\mathbf{B}'$. The dimension reduction makes the predicted block-size $\beta'$ smaller.

We note that our classifiers often lead to the “Way too many hints” regime for KYBER-768 and KYBER-1024. A reason is that the smaller $\eta_1 = 2$ means fewer different values to distinguish between. For the other regime, a starting value for $\beta'$ is predicted following standard cost-models. This value may be optimistic; we provide experimental evidence that the effective $\beta''$ is not far from the predicted value. When the dimension reduction is large (i.e. many perfect hints), BKZ-$\beta''$ over $\mathbf{B}'$ completes the recovery in short time.

1.1.3 Concrete results and breaks

To assess the concreteness of the above study, we compared data obtained from 4 different
chips (STM32F4 Arm® Cortex®-M4), collecting 20000 executions for each parameter sets
of KYBER. We note that our pre-processing (see Section 3.3) could perfectly separate
negative and positive values, but we focused on trying to exploit the perfect hints. About

<footnote>$^6$https://gitlab.inria.fr/capsule/avengers-assemble</footnote>
20% of the executions were kept for testing purposes, and provided guesses of a proportion $\rho$ of the coordinates of $\mathbf{x} = (\mathbf{s}, \mathbf{e})$ as described in Figure 7, Section 3.6. We sum-up the successful results of Figure 10 in Table 1 below.

<table><caption>**Table 1:** Key-recovery, worst and best cases, for the three security levels; a block-size of 0 means instead Gaussian elimination.</caption><thead><tr><th>KYBER version</th><th>η<sub>1</sub></th><th>worst ρ</th><th>largest β</th><th>worst time</th><th>smallest β</th><th>best time</th></tr></thead><tbody><tr><td>512</td><td>3</td><td>≈ 37%</td><td>65</td><td>&lt; 18h</td><td>0</td><td>&lt;1s</td></tr><tr><td>768</td><td>2</td><td>≈ 43%</td><td>23</td><td>&lt; 18h</td><td>0</td><td>&lt;1s</td></tr><tr><td>1024</td><td>2</td><td>≈ 46%</td><td>25</td><td>&lt; 18h</td><td>0</td><td>&lt;1s</td></tr></tbody></table>

For the remaining cases when $\eta_1 = 3$, the proportion of good guesses was too low ($\rho < 35\%$), and we did not finish the experiment due to a too large estimated running time. We additionally conducted large-scale experiments for KYBER-512, 768 and 1024, targeting respectively $16 \times 1000$, $16 \times 666$, and $16 \times 500$ LWE instances (16 standing for the number of testing/training chip combinations). For all these instances, we obtained the hints, built the associated hinted LWE instance, then run either Gaussian elimination, or BKZ with block sizes up to 65 to solve it. For lattice reduction we used in a black-box way the public implementation of BKZ from fplll [dt23], available in sagemath. This algorithm was fed as input the matrices obtained from our pre-processing of the classifier's guesses and the resulting predicted block-size. In almost all cases, we recovered the secret key under the time threshold of 18 hours we set for our attack. We provide the success rates against every security level in Table 2. Detailed results are gathered in Figure 11.

<table><caption>**Table 2:** Worst, average and best success rate, depending on the security level.</caption><thead><tr><th>KYBER</th><th>Worst</th><th>Average</th><th>Best</th></tr></thead><tbody><tr><td>512</td><td>56.9%</td><td>96.71%</td><td>100%</td></tr><tr><td>768</td><td>99.85%</td><td>99.98%</td><td>100%</td></tr><tr><td>1024</td><td>100%</td><td>100%</td><td>100%</td></tr></tbody></table>

## 1.2 Related works

**Other side-channel attacks against Kyber.** In the realm of side-channel analysis, KYBER has not been spared; numerous papers propose side-channel attacks. Most of these papers target the encapsulation to recover the ephemeral key or the decryption to recover the secret key. In [RBRC22], the authors focus on decrypting using a chosen ciphertext attack combined with side-channel information. The Number Theoretic Transform (NTT) function within KYBER has also been extensively targeted, as seen in e.g. [QLZ$^{+}$23, BBB$^{+}$24], where authors exploit side-channel information from the NTT computation. Elena Dubrova and her co-authors have published several side-channel attacks against secure implementations of KYBER [WD23, BNGD23, JNWD24]. However, we have not found any work that specifically focused on attacking KYBER's sampler with a single power trace which leads to a full secret key recovery.

From a more general perspective, samplers of other lattice-based cryptographic schemes have been targeted by side-channel attacks. For example, in [KAA21], the authors proposed single power trace attacks on small polynomial sampling of NTRU, NTRU-Prime, and CRYSTALS-DILITHIUM. A template attack was used to recover secret coefficients from a small set of possibilities ({-1, 0} for NTRU-HPS and {-1, 1} for CRYSTALS-DILITHIUM), thus reducing the security of the algorithms but without fully compromising the key. Another template attack against the Gaussian sampler of the homomorphic encryption algorithm SEAL [SEA19] was introduced in [AKP$^{+}$22a], claiming that if all
the identified vulnerabilities are exploited during the attack, the key can be completely
recovered according to the estimator proposed in [DSDGR20]. Recently in TCHES-2024, a
similar approach was used to target the discrete Gaussian sampler of HAWK's [DPPvW22]
in [GR24]. The authors employed a template attack, performing the analysis on the first
sampled coefficient (first element of nested loop) before generalizing. This attack resulted
in full key recovery only when the template reached 100% accuracy. However, the problem
of identifying correctly classified samples when accuracy is lower remains unresolved.

During the evaluation of our work, another single trace attack on the CBD sampler
appeared [PK25]. Their approach targets all CBD calls, that is, during key-generation like
ours but also those during encapsulation/decapsulation. It provides a strong classifier of
the values for the coordinates of (s, e) – contrasting with our classifier on the Hamming
weight. Their approach results in better accuracies but lower average success rates than
ours; their methodology only based on accuracies has low tolerance to noise, while thanks
to our dual methodology, our approach is more resilient. Additionally, they target only
KYBER-768, and they require the exact determination of all coefficients. The authors
note however that the case where some coefficients are not found could be handled by
lattice reduction, but they do not investigate further this approach. Our work confirm
their observation.

**Other works about “LWE with hints”**. On a more theoretical side, several “LWE with side information” variants have been introduced in cryptography [OPW11, AP12, LKK<sup>+</sup>18, CKK<sup>+</sup>21] as a security assumption for scheme design. In these formal variants, a hint is not obtained by side-channel, but rather revealed to an attacker due to the scheme design. In some context (typically, approximate hints with relatively large variance), it is proven that Hint-LWE reduces to LWE [KLSS23]. On the cryptanalysis side of LWE with additional hints, the notion of hints has been formalized in [DSDGR20], and the analysis pushed forward in [DGHK23]. There are to the best of our knowledge no attack so far that could successfully break KYBER using only approximate hints (even if they are of good quality). While our classifiers strongly constrain the *a posteriori* distribution of (s, e), it is a challenging but interesting task to design an acceptably efficient cryptanalytic algorithm that could extend the scope of our attack — we hope to tackle it in the future.

Nonetheless, the recent work of [MN23] showed experimentally that, for about *n*/*2 random and large* perfect hints, the LLL algorithm could be enough to recover a KYBER key. More precisely, in this context the hints are not obtained by side-channel analysis. Rather, they are additional inner products ⟨s, vᵢ⟩ given with the LWE instance; experimentally, the authors selected vᵢ's with entries being uniformly random modulo *q*. Note that compared to the perfect hints obtained from side-channel which are typically coordinates of (s, e) and thus quite small, the expected scalar product is now quite large.

This difference is more impactful than it may seem at first sight. Indeed, the authors
of [MN23] observe in Remark 4.7 that the instances they consider could often be solved by
running the LLL algorithm over a matrix different than (but related to) the one in the
primal attack. That is, they consider the matrix [V|I<sub>n+m+1</sub>], where V's columns are hint
vectors v<sub>i</sub>. If there would be one hint, this corresponds to a so-called *Knapsack problem*;
since v<sub>i</sub> is uniform modulo *q*, we can expect its largest entry to be rather large, leading
a *low density* Knapsack. For more hints, we could call it a low-density multi-Knapsack,
and the volume of the lattice spanned by V is also going to be expectedly large. In
cryptography, such problems have been solved in many regimes of parameters using LLL
(and additional tricks, see e.g. Odlyzko's survey [Odl90]). The work of [MN23] seems to
support that low-density multi-Knapsacks are not much harder than their single vector
version, at least in the case of V being uniform modulo a rather large *q*.

In contrast, the perfect hints we obtain are exact coordinates, or in other words, **V** is a
canonical basis and the density of the corresponding multi-Knapsack is much higher: **s** is
no longer the shortest solution, and running their attack did not work in our case. An
interesting future work could be to reconcile these two approaches.

2 Preliminaries and notation

**2.1 Notation**

**Bytes and byte arrays.** Inputs and outputs to all API functions of KYBER are byte
arrays. We denote by $\mathcal{B}$ the set $\{0, ..., 255\}$, i.e. the set of 8-bit unsigned integers (bytes),
by $\mathcal{B}^l$ the set of byte arrays of length $l$ and by $\mathcal{B}^*$ the set of byte arrays of arbitrary length.
**Sets and Distributions.** We denote by $[n]$ the set $\{1, ..., n\}$, $\bar{S}$ the complement of a
subset $S$, and $|S|$ its cardinality. For a set $S$, we write $s \leftarrow S$ to denote that $s$ is chosen
uniformly at random from $S$. If $S$ is a probability distribution, then this denotes that $s$ is
chosen according to the distribution $S$. We denote $[n]$ the set of integers from 1 to $n$.

**Matrices and vectors.** By default, all vectors are column vectors. Bold upper-case letters are matrices. We denote by $\mathbf{I}_n$ the identity matrix of dimension $n$. For a vector $\mathbf{v}$ (or matrix $\mathbf{A}$), we denote by $\mathbf{v}^t$ (or $\mathbf{A}^t$) its transpose. For a vector $\mathbf{v}$ we write $\mathbf{v}_i$ to denote it's $i$-th entry (with indexing starting at one); for a matrix $\mathbf{A}$ we write $\mathbf{A}_i$ to denote its $i$-th row and $\mathbf{A}_{i,j}$ to denote the entry in row $i$, column $j$ (again, with indexing starting at one). Write $\mathbf{M}_{[S:S']}$ the sub-matrix of $\mathbf{M}$ obtained by taking the rows with indices in the set $S$ and the columns with indices in the set $S'$. Similarly, write $\mathbf{v}_I$ for the vector of length $|I|$ obtained by taking the coordinates with indices in $I$ in $\mathbf{v}$.

**Polynomials and rings.** We let $q$ be a prime and $\mathbb{Z}_q$ be the finite field with $q$ elements. Let $R$ be the ring $\mathbb{Z}[X]/(X^n + 1)$ and $R_q$ be the ring $\mathbb{Z}_q[X]/(X^n + 1)$. Unless mentioned otherwise, we always identify an element $a = \sum_i a_i x^i \in R$ or $R_q$ to its vector of coordinates $(a_0, \dots, a_{n-1}) \in \mathbb{Z}$ or $\mathbb{Z}_q$. We do the same “component-wise” for vectors $\mathbf{a} \in \mathbb{R}^k$, for $k \ge 2$. Apart from when defining formally KYBER, we actually never really need to consider $R$ as the ring, but rather through its coefficient identification above.

**Binomial distribution.** KYBER uses the centered binomial distribution (CBD) $B_\eta$ for $\eta \in \{2,3\}$ to generate its secret and noise. Let $u = \sum_1^\eta (a_i - b_i) \in \mathbb{Z}$ where $(a_1, \dots, a_\eta, b_1, \dots, b_\eta) \leftarrow \{0,1\}^{2\eta}$ be a random variable then $u \leftarrow B_\eta$. When we write that a polynomial $f \in R_q$ or a vector of such polynomials is sampled from $B_\eta$, we mean that each coefficient is sampled from $B_\eta$.

**2.2 Learning with errors and variants**

The Learning With Errors problem (LWE, [Reg09]) and its module version MLWE [BGV14, LS15] are computational problems that are believed to be hard to solve for both classical and quantum computers. Their computational hardness are currently ones of the pillars in the construction of quantum-safe public-key cryptosystems. They are defined as follows.

**Definition 1.** (Search LWE[Reg09]) Let $m \ge n$ and $q$ be positive integers, $q \ge 2$, $\chi$ is a distribution on $\mathbb{Z}$. The search-LWE$_{m,n,q,\eta}$ is defined as: Let $\mathbf{s} \in \mathbb{Z}_q^n$ sampled from $\chi$ be the secret and $\mathbf{e} \in \mathbb{Z}_q^m$ sampled from $\chi$ be the noise. Given the pair $(\mathbf{A} \leftarrow \mathbb{Z}_q^{m \times n}, \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e} \in \mathbb{Z}_q^n)$, find $\mathbf{s}$.

Formally, KYBER's formal security relies on the MLWE variant (M standing for “module”). We omit the definition as it is not used in this work. Moreover, just as $\mathbf{s}, \mathbf{e} \in \mathbb{R}_q^k$ can be identified to vectors in $\mathbb{Z}_q^{kn}$, the matrix $\mathbf{A} \in \mathbb{R}_q^{k \times k}$ can be equivalently seen as a (structured) matrix $\mathbf{A} \in \mathbb{Z}_q^{nk \times nk}$: search-MLWE reduces to search-LWE. In our setting where we will also be given hints on $(\mathbf{s}, \mathbf{e})$, attacking KYBER will mean to try to solve a variant of LWE. We define it below as (also a variant of) Hint-LWE (or, LWE with side information).
**Definition 2.** (Coord-LWE) Let $\kappa \ge 0$ be an integer. The Coord$^{\kappa}$-LWE$_{m,n,q,\eta}$ problem is defined as: given $(\mathbf{A}, \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e})$ a search-LWE$_{m,n,q,\eta}$ instance, a subset $I \times J \subset [n] \times [m]$ with $|I \times J| = \kappa$ and the values $\{\mathbf{s}_i\}_{i \in I}, \{\mathbf{e}_j\}_{j \in J}$, find $\mathbf{s}$.

## 2.3 CRYSTALS-Kyber

CRYSTALS-KYBER [BDK$^{+}$17] is a MLWE-based public-key encryption algorithm and underlies the first post-quantum standard for key-encapsulation (ML-KEM). As such, it gathers much attention on all aspects of its practical resilience. As any PKE, it is formally composed of three main subroutines: the key generation, the encryption and the decryption. In this paper we focus on the key generation described in Algorithm 1, and more precisely, we look at the sampling of $\mathbf{s}$ and $\mathbf{e}$ highlighted in light blue. These two private values are derived using the function CBD (for “centered binomial distribution”) described in Algorithm 2. The CBD function depends on the security level, specifically on the value of $\eta_1$, which defines the range of the sampled value of the secret key. In fact, for KYBER-512 $\eta_1$ is equal to 3, meaning that the coefficients are sampled over $\ll -3, 3 \gg$, for KYBER-768 and KYBER-1024, $\eta_1$ is equal to 2, sampling the coefficient over $\ll -2, 2 \gg$. The security level also influences the number of times CBD is called for each key-generation execution. For KYBER-512, $\mathbf{s}$ and $\mathbf{e}$ have $k=2$ components, resulting in two calls per secret, while for KYBER-768 and KYBER-1024, $k=3$ and $k=4$ respectively. The overall parameters of the different versions of KYBER are reproduced for completeness in the Table 3. Note that $\eta_2$ is only use for ephemeral secrets and is not relevant to our study.

<table><caption>**Algorithm 1:** CRYSTALS-Kyber key generation algorithm from [BDK$^{+}$17].</caption><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>d &larr; B<sup>32</sup></td><td>// get random</td></tr><tr><td>2</td><td>(&rho;, &sigma;) = G(d)</td><td>// G is a hash function</td></tr><tr><td>3</td><td>(&#x0102;<sub>j,i</sub> = Parse(XOF(&rho;, i, j)))<sub>i&lt;k-1, j&lt;k-1</sub></td><td>// &#x0102; &isin; R<sub>q</sub><sup>k&times;k</sup> in the NTT domain</td></tr><tr><td>4</td><td>{s<sub>i</sub> = CBD<sub>&eta;<sub>1</sub></sub>(PRF(&sigma;, i))}<sub>i&lt;k</sub></td><td>// Sample s &isin; R<sub>q</sub><sup>k</sup></td></tr><tr><td>5</td><td>{e<sub>i</sub> = CBD<sub>&eta;<sub>1</sub></sub>(PRF(&sigma;, i + k))}<sub>i&lt;k</sub></td><td>// Sample e &isin; R<sub>q</sub><sup>k</sup></td></tr><tr><td>6</td><td>&#x0102;, &#x0103; = NTT(e), NTT(s)</td><td></td></tr><tr><td>7</td><td>t&#x0302; = &#x0102; &circ; &#x0103; + &#x0102;</td><td></td></tr><tr><td>8</td><td>pk = Encode<sub>12</sub>(t&#x0302; mod<sup>q</sup>)||&rho;</td><td>// pk = As + e</td></tr><tr><td>9</td><td>sk = Encode<sub>12</sub>(&#x0103; mod<sup>q</sup>)</td><td>// sk = s</td></tr><tr><td>10</td><td>return pk, sk</td><td></td></tr></tbody></table>

<table><caption>**Algorithm 2:** CRYSTALS-Kyber CBD function from [BDK$^{+}$17].</caption><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>(&beta;<sub>0</sub>, ..., &beta;<sub>512&eta;<sub>-1</sub></sub>) = BytesToBits(B)</td><td></td></tr><tr><td>2</td><td>for ( i = 0; i &lt; 256; i++ ) {</td><td></td></tr><tr><td>3</td><td>a = &sum;<sub>j=0</sub><sup>&eta;<sub>-1</sub></sup> &beta;<sub>2i&eta;+j</sub></td><td></td></tr><tr><td>4</td><td>b = &sum;<sub>j=0</sub><sup>&eta;<sub>-1</sub></sup> &beta;<sub>2i&eta;+&eta;+j</sub></td><td></td></tr><tr><td>5</td><td>f<sub>i</sub> = a - b</td><td></td></tr><tr><td>6</td><td>}</td><td></td></tr><tr><td>7</td><td>return &sum;<sub>0</sub><sup>255</sup> (f<sub>i</sub>X<sup>i</sup>)</td><td></td></tr></tbody></table>
<table><caption>**Table 3:** Parameter sets for KYBER from [BDK$^{+}$17].</caption><thead><tr><th></th><th>n</th><th>k</th><th>q</th><th>η<sub>1</sub></th><th>η<sub>2</sub></th><th>(d<sub>u</sub>, d<sub>v</sub>)</th><th>δ</th></tr></thead><tbody><tr><td>KYBER-512</td><td>256</td><td>2</td><td>3329</td><td>3</td><td>2</td><td>(10, 4)</td><td>2<sup>-139</sup></td></tr><tr><td>KYBER-768</td><td>256</td><td>3</td><td>3329</td><td>2</td><td>2</td><td>(10, 4)</td><td>2<sup>-164</sup></td></tr><tr><td>KYBER-1024</td><td>256</td><td>4</td><td>3329</td><td>2</td><td>2</td><td>(11, 5)</td><td>2<sup>-174</sup></td></tr></tbody></table>

## 2.4 Lattices, primal attack

A lattice $\Lambda$ of dimension $d$ and rank $r$ is a discrete additive subgroup of $\mathbb{R}^d$ generated as the set of all linear integer combinations of $r$ linearly independent vectors $\mathbf{v}_1, \dots, \mathbf{v}_r \subset \mathbb{R}^d$. That is, $\Lambda = \{\sum_{j=1}^r z_j \mathbf{v}_j : z_j \in \mathbb{Z}\} = \mathcal{L}(\mathbf{V})$, and $\mathbf{V} = [\mathbf{v}_1 \cdots \mathbf{v}_r]^t \in \mathbb{R}^{r \times d}$ is called a basis of $\Lambda$. Being discrete, a lattice $\Lambda$ has shortest (non-zero) vectors of length $\lambda_1(\Lambda)$. Although $\Lambda$ admits many bases other than $\mathbf{V}$, its volume, denoted by $\det(\Lambda)$, is independent from the choice of the basis, i.e. $\det(\Lambda) = \sqrt{\det(\mathbf{V} \cdot \mathbf{V}^t)}$ for an arbitrary basis $\mathbf{V}$ of $\Lambda$. While KYBER's security formally relates to MLWE, for our purpose, it is enough to consider the corresponding unstructured version of LWE. The public data of interest consists in a matrix $\mathbf{A} \in \mathbb{Z}_q^{m \times n}$ with $m \ge n$ and $\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e} \in \mathbb{Z}_q^m$. The so-called primal attack consists in rewriting this instance as $[\mathbf{I}_m | \mathbf{A}| \mathbf{b}] \cdot (\mathbf{e}^t, \mathbf{s}^t, -1) = 0$, and realizing that $(\mathbf{e}^t, \mathbf{s}^t, -1)$ is an unusually short vector in a $q$-ary lattice $\Lambda = \mathcal{L}(\mathbf{B})$ with a known basis

$$ \mathbf{B} = \begin{bmatrix} q\mathbf{I}_m & \mathbf{0} & \mathbf{0} \\ -\mathbf{A}^t & \mathbf{I}_n & \mathbf{0} \\ -\mathbf{b}^t & \mathbf{0} & \mathbf{1} \end{bmatrix} \in \mathbb{Z}^{(n+m+1) \times (n+m+1)}, $$

on which lattice reduction is performed. A reason why $(\mathbf{e}^t, \mathbf{s}^t, -1)$ is called unusually short comes from the Gaussian heuristic which predicts that $\lambda_1(\Lambda) \approx \sqrt{d(2\pi e)^{-1}} \cdot \det(\Lambda)^{1/d}$, where $d = \text{rank} \Lambda = n+m+1$. Indeed, in the context of LWE, we expect that $\| (\mathbf{e}^t, \mathbf{s}^t, -1) \| = \gamma \cdot \sqrt{d} = \lambda_1(\Lambda)$ for some small constant $\gamma$ while $\det(\Lambda)^{1/d}$ is quite larger in practice. A measure of deviation from this prediction can be encoded in the gap of the lattice, taking ratio of the prediction and the expected shortest vector:

$$ G(\gamma, \Lambda) := \frac{\det(\Lambda)^{1/d}}{\gamma \cdot \sqrt{2\pi e}}. $$

More precisely, in the primal attack an attacker runs the lattice reduction algorithm BKZ with a large block-size $\beta$ on $\mathbf{B}$, and for large enough $\beta$ they expect to recover $(\mathbf{e}^t, \mathbf{s}^t, -1)$ during its execution. The estimation of $\beta$ at which BKZ $-\beta$ solves such instances is traditionally done following the analyses in [ADPS16, AGVW17], which involves the so-called Root-Hermite-Factor$^7$ $\delta_\beta$ of BKZ $-\beta$. From these sources, the inequality driving the concrete hardness of the primal attack can be written as

$$ \sqrt{\beta} \cdot \delta_{\beta}^{1+d-2\beta} \le \sqrt{2\pi e} \cdot G(\gamma, \Lambda), \quad (1) $$

and the larger the gap (the smaller $\gamma$), the easier the instance gets. The smallest $\beta$ such that this inequality is satisfied corresponds to the input block-size for a plausibly successful BKZ run. This is how parametrization of a LWE instance is done in practice, and how one can understand the power of a lattice reduction attack. From the expression of the gap, we see that the main contributors are $\gamma$ and the normalized volume $\det(\Lambda)^{1/d}$. Typically, integrating perfect or modular hints decreases the rank $d$ and increases the determinant, so that as expected it would lead to a more efficient attack.

<footnote>$^7$Experimentally, it is $\delta_\beta = ((\pi\beta)^{\frac{1}{\beta}} \cdot \frac{\beta}{2\pi e})^{1/2\beta-2}$.</footnote>
<figure><img src="image_3.png" /><figcaption>**Figure 1:** ChipWhisperer CW1200 (in gray), the UFO baseboard (in red) and the four CW308T target boards A, B, C and D (respectively 1, 2, 3 and 4 on the picture) with STMicroelectronics STM32F4 Arm® Cortex®-M4 chips (in blue).</figcaption></figure>

```c
static void cbd2(poly *r,
               const unsigned char *buf){
    unsigned int i, j;
    uint32_t t, d;
    int16_t a, b;

    for (i = 0; i < n/8; i++) {
        t = load32_littleendian(buf + 4 * i);
        d = t & 0x55555555;
        d += (t >> 1) & 0x55555555;

        for (j = 0; j < 8; j++) {
            // in {0, 1, 2}
            a = (d >> (4 * j + 0)) & 0x3;
            // in {0, 1, 2}
            b = (d >> (4 * j + 2)) & 0x3;
            // in {-2, -1, 0, 1, 2}
            r->coeffs[8 * i + j] = a - b;}
        }
    }
```

**Code 1:** pqm4 open source implementation [KPR$^+$] of Algorithm 2 for $\eta_1 = 2$.

```c
void cbd3(poly *r, int add,
          const unsigned char *buf) {
    unsigned int i,j;
    uint32_t t,d;
    int16_t a,b;

    for(i = 0; i < n/4; i++) {
        t = load24_littleendian(buf + 3 * i);
        d = t & 0x00249249;
        d += (t >> 1) & 0x00249249;
        d += (t >> 2) & 0x00249249;

        for(j=0; j<4; j++) {
            // in {0, 1, 2, 3}
            a = (d >> (6 * j + 0)) & 0x7;
            // in {0, 1, 2, 3}
            b = (d >> (6 * j + 3)) & 0x7;
            // in {-3, -2, -1, 0, 1, 2, 3}
            r->coeffs[4 * i + j] = a - b;}
        }
    }
```

**Code 2:** pqm4 open source implementation [KPR$^+$] of Algorithm 2 for $\eta_1 = 3$.

# 3 Side-channel attack

## 3.1 Adversary model

Targeting the private key generation, more precisely the sampling of $s$ and $e$, we have to mount an attack that works using only one execution of Algorithm 1. This means that we have to analyze $2k$ executions of Algorithm 2, where $k$ is the number of components of $s \in R_q$. In other words, we need to be able to recover the secret coefficients of $s$ and $e$ using only one power trace, that we can process to extract the $2k$ calls to the CBD sampler. To prove this capability, we first have to collect power traces of CBD executions.

## 3.2 Setup

We acquire the power traces using the ChipWhisperer-Pro kit displayed in Figure 1. It is composed of a ChipWhisperer CW1200 (in grey) which is connected to a computer and makes the acquisition dialoguing with the UFO baseboard (in red) and the target (in blue). In order to verify the portability of our analysis, we used four different targets. For each of them we recorded $20K^8$ power traces resulting from the $CBD_{\eta_1=2}$ and $CBD_{\eta_1=3}$, for which

<footnote>$^8$Kilo, $10^3$</footnote>
<figure><img src="image_4.png" /><figcaption>**Figure 2:** Averaged power consumption resulting from the execution of Code 1 (top) and 2 (bottom). Both executions are composed of two nested loops. The vertical dashed lines delimit each round of the outer loop. The squares on the right zoom in a round of the outer loop, and in red, we highlight one round of the inner loop.</figcaption></figure>

the code is available in Code 1 and 2 respectively. We compiled the targeted codes using the Arm GNU toolchain<fnref n="9" /> with -Os<fnref n="10" /> as optimization which is usual for embedded codes.

## 3.3 Pre-processing

Once we recorded the power traces, the first step is to identify when the computation of each coefficient occurs, mapping the highlighted part of Code 1 and 2 on the power traces. For $η_1 = 2$, there are 32 rounds in the outer loop and 8 rounds in the inner loop, while for $η_1 = 3$, there are 64 rounds in the outer loop and 4 in the inner loop. In both cases, this results in the generation of 256 coefficients. On a first look at the averaged traces in Figure 2, we can visually identify repeated patterns. Using a simple peak detection algorithm based on thresholds, we can identify each round of the outer loop patterns, 32 resp. 64 for $η_1 = 2$ resp. $η_1 = 3$. Then, using a similar algorithm, we identify the 256 rounds of the inner loop, splitting the patterns of the outer loop into 8 and 4 for $η_1 = 2$ and $η_1 = 3$, respectively. This process is highlighted on Figure 2. Now, given a power trace resulting from the execution of Code 1 or 2, we are able to extract 256 subtraces, each corresponding to the computations of one secret coefficient highlighted in blue.

As mentioned in Section 3.2, we collected 20K traces per chip (4) and per CBD algorithm (2). The power consumption from the computations of one secret coefficient (extracted as described above) is composed of 104 and 100 features (points) for $η_1 = 2$ and $η_1 = 3$, respectively. We end up with 4 × 2 = 8 datasets composed of 5120K (256 × 20K) subtraces. Each dataset is then split into two, one for training and one for testing, composed of 80% and 20% of the samples, respectively.

Next, we analyze how the computation of the secret coefficients leaks and select points of interest (PoIs). To do so, we use the Pearson correlation coefficient on the extracted subtraces of the training dataset, a well-known method in side-channel analysis introduced in [BCO04]. The results are displayed on the left part of Figure 3. We compute the correlation between extracted subtraces (for each of its feature independently) and various distributions across all samples. The distributions include *a*, *b*, and $a-b^{11}$; their Hamming

<footnote n="9">⁹https://developer.arm.com/Tools%20and%20Software/GNU%20Toolchain</footnote>

<footnote n="10">¹⁰https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html</footnote>

<footnote n="11">¹¹The notation refer to those in Code 1 and Code 2, where $a-b$ is the computation of the secret</footnote>
<figure><img src="image_5.png" /><figcaption>**Figure 3:** On the left, Pearson coefficients between power traces and modeled distributions. On the right, the distribution of each sample for the features indicated by "+" on the left. Plots in the same column share the legend.</figcaption></figure>

weights<fnref n="12" /> $hw(a)$, $hw(b)$ and $hw(a-b)$; and finally the binary distribution $a-b \ge 0$, labeled as “pos vs neg” in Figure 3 (0 coefficients are labeled as positive).

The main observation is that we achieve a very high correlation score, near 1, for the models $hw(a-b)$ and “pos vs neg”. Using feature pointed by the highest correlation value obtained using the “pos vs neg” model allows us to separate samples of positive coefficients and samples of negative coefficients simply by examining with a threshold. Indeed, in the right part of Figure 3, we plot the histogram distribution values of this point-of-interest for all samples, symbolized by a cross on the left. We can see that leakage resulting from the manipulation of negative or positive coefficients is perfectly distinguishable. This is illustrated by the green hatched path, which highlights the distance between the highest feature value for the positive coefficient manipulation and the lowest feature value for the negative coefficient manipulation samples.

## 3.4 Learning phase

As we have seen, we are able to perfectly distinguish samples from positive and negative coefficients. We can actually go further. Indeed, Figure 3 suggests that given the level of correlation we observed, we should be able to construct a classifier that can at least distinguish the Hamming weights of $a-b$. To do so, we use trained classifiers for $\eta_1 = 2$ and $\eta_1 = 3$, for each chip A, B, C and D and for positive and negative samples, ending up with 16 classifiers. The classes are the Hamming weights. Before training, the data are balanced so that all classes contain the same number of samples, and within a class, all values are equidistributed. In fact, in order to avoid overfitting classes, we downsample the secret coefficients from the binomial distribution, as shown in Figure 4.

<footnote>coefficient.</footnote>

<footnote n="12">¹²The Hamming weight $hw$ is the sum of the bits, and is here computed using *two's complement* format over 16-bit integers (e.g. $-1 = 0xffff$, $-2 = 0xffff$).</footnote>
<figure><img src="image_6.png" /><figcaption>Figure 4: Balancing process by downsampling, original on the left and downsampled on the right.</figcaption></figure>

Furthermore, we also select specific features, called points of interest (PoIs), in the training dataset. To do so, we use the previously computed Pearson correlation coefficients, and only keep the features (32) with the highest absolute scores.

## 3.5 Hints construction

Regarding the classifier, we tried one of the most commonly used classifiers in side-channel analysis for supervised learning (meaning with a learning phase): templates [CRR02], especially for single-traces setups [YK21, GR24]. With this classifier, we achieved very high-accuracy scores (between 89.94% and 98.80%) as summarized in Figure 6(a). This was expected, given the high dependency we observed between the power traces and the HW of the secret coefficient in Figure 3. However, we face two obstacles: we do not tolerate errors and we cannot acquire new traces in order to avoid classification mistakes (an otherwise commonly used technique in side-channel attacks). These obstacles were already noticed by Guerreau et al. in [GR24], without being solved. So the question becomes: how to be sure of the results of our classifier, or how to identify when it is wrong? To do so, we take a look at the probabilities outputted by the classifiers. Let us first formalize the classification process: let $\mathcal{X}$ be the input space and $\mathcal{Y} = \{1, 2, \dots, C\}$ be the set of C classes. A classifier is a function $\text{clf}: \mathcal{X} \to \Delta^C$, where $\Delta^C$ is the C-dimensional simplex, defined as:

$$ \Delta^C = \{ (p_1, p_2, \dots, p_C) \in \mathbb{R}^C \mid p_i \ge 0 \ \forall j \text{ and } \sum_{j=1}^C p_j = 1 \} $$

For a given input sample $x \in \mathcal{X}$, the classifier $\text{clf}(x)$ outputs a probability distribution over the C classes:

$$ \text{clf}(x) = (p_1, p_2, \dots, p_C), $$

where $p_j$ represents the probability that the input sample $x$ belongs to the class $j$, and $\sum_{j=1}^C p_j = 1$. The classifier $\text{clf}$ is typically obtained through a training process, where it learns to map input samples to probability distributions over classes using a training dataset $\mathcal{D}_{\text{train}} = \{(x_i, y_i)\}_{i=1}^N$, where $x_i \in \mathcal{X}$ and $y_i \in \mathcal{Y}$. Define also the prediction function

$$ \text{pred}: \begin{array}{r} \mathcal{X} \\ x \end{array} \longrightarrow \begin{array}{r} \mathcal{Y} \\ \text{pred}(x) = \text{argmax}(\text{clf}(x)). \end{array} $$

Now to classify, let us first assume that we are given:
* a classifier $\text{clf}: \mathcal{X} \to \Delta^C$ that outputs a probability distribution over $C$ classes;

* a testing dataset $\mathcal{D}_{\text{test}} = \{(x_i, y_i)\}_{i=1}^N$ composed of samples $\mathcal{X}_{\text{test}} = \{x_1, x_2, \dots, x_N\}$ ($x_i \in \mathcal{X}$) with true class labels $\mathcal{Y}_{\text{test}} = \{y_1, y_2, \dots, y_N\}$ ($y_i \in \mathcal{Y}$);

* the output $\text{clf}(x_i) = (p_{i,1}, p_{i,2}, \dots, p_{i,C})$ of the classifier for each sample $x_i$, where $p_{i,j}$ is the probability that $x_i$ belongs to class $j$.

Then, we use the following process:

1. **Identify the highest incorrect class-specific probabilities.** For each $(x_i, y_i) \in \mathcal{D}_{\text{test}}$ with predicted class $j$ (i.e., $\text{pred}(x_i) = j$), let $p_{i,j}$ be the probability of the predicted class $j$. Let $p_{j,\max}^{\text{wrong}}$ be the highest probability wrongly assigned to $j$:

$$p_{j,\max}^{\text{wrong}} = \max_{i \le N} \{p_{i,j} | \text{pred}(x_i) = j \text{ and } j \ne y_i\}$$

2. **From highest incorrect class-specific probabilities to error-free recovered labels.** Based on $\{p_{j,\max}^{\text{wrong}}\}_{j \le C}$, we can construct the set of incomplete error-free recovered labels $\mathcal{Y}_{\text{e-f}}$, composed of unknowns $(-1)$ and true labels $(y_i)$:

$$\mathcal{Y}_{\text{e-f}} = \{(y'_i)\}_{i \le N} \text{ with } y'_i = \begin{cases} y_i & \text{if } p_{i,\text{pred}(x_i)} > p_{\text{pred}(x_i),\max}^{\text{wrong}} \\ -1 & \text{otherwise} \end{cases}$$

3. **From error-free recovered labels to hints.** Based on $\mathcal{Y}_{\text{e-f}}$, we can partially reconstruct the coefficient vector, but due to our HW models, not all coefficients can be directly recovered. This is summarized in Table 4.

<table><caption>**Table 4:** Table of correspondence between labels, HW and coefficient values for $\eta_1 = 2$ and $\eta_1 = 3$. Perfects hints used in Section 4.2 are written in bold fonts.</caption><thead><tr><th rowspan="2"></th><th colspan="4">η<sub>1</sub> = 2</th></tr><tr><th colspan="2">clf<sub>pos</sub></th><th colspan="2">clf<sub>neg</sub></th></tr></thead><tbody><tr><th>labels</th><th>a</th><th>b</th><th>a</th><th>b</th></tr><tr><th>HW</th><td>0</td><td>1</td><td>15</td><td>14</td></tr><tr><th>values</th><td><b>0</b></td><td>1, 2</td><td><b>-1</b></td><td><b>-2</b></td></tr></tbody></table>

<table><thead><tr><th colspan="5">η<sub>1</sub> = 3</th></tr><tr><th colspan="3">clf<sub>pos</sub></th><th colspan="2">clf<sub>pos</sub></th></tr><tr><th>a</th><th>b</th><th>c</th><th>a</th><th>b</th></tr></thead><tbody><tr><td>0</td><td>1</td><td>2</td><td>15</td><td>14</td></tr><tr><td><b>0</b></td><td>1, 2</td><td><b>3</b></td><td><b>-1</b></td><td>-2, -3</td></tr></tbody></table>

We illustrate our hint construction through an example. The setting is the training of chip A, and testing on chip B, for $\eta_1 = 2$ (KYBER-768 and KYBER-1024). First, we consider the two trained classifiers (decision tree with AdaBoost) $\text{clf}_{\text{pos}}$ and $\text{clf}_{\text{neg}}$ and compute their probabilities on the testing set. Figure 5 displays in four histograms the outputted probabilities for each of their two possible classes, as in Table 4. Then, for each histogram, we compute the highest probability for a wrongly classified label ($p_{j,\max}^{\text{wrong}}$). This threshold value is displayed with a dashline on each of the four histograms. We then consider all classified labels associated with a probability lower than this threshold as unknown: this does not mean that the classifier is wrong for all these labels, but we cannot trust it at this level. These labels are not included in the next phase (lattice reduction). On the other hand, when labels are classified with a probability higher than this threshold value, their Hamming weight is considered as known. Looking at Table 4, the next step is to convert these "known" labels (with HW predicted as 0, -1, and -2) into perfect hints. For example, say a label $\ell_i$ is known with value -1; it corresponds to a coordinate $\mathbf{x}_i$ of $\mathbf{x} = (\mathbf{s}, \mathbf{e})$, and "known" means we consider that the classifier has guessed correctly its value -1. In other words, we have a perfect hint $\mathbf{x}_i = \ell_i = -1 = \langle \mathbf{x}, \mathbf{b}_i \rangle$, where $\mathbf{b}_i$ is the i-th canonical basis vector. All such known labels are listed and they proceed to the lattice reduction phase described in Section 4.
<figure><img src="image_7.png" /><figcaption>**Figure 5:** Outputted probabilities of the two classifiers with AdaBoost, trained on chip A and targeting chip B, with $\eta_1 = 2$ for all different classes. The displayed probabilities are only the highest between the two labels (in other words, we plot the probabilities of the predicted labels).</figcaption></figure>

Using this process with templates, we observe a low and insufficient number of error-free recovered labels. In fact, with templates, in the best case, we can only recover 12.97% of the coefficients as shown in Figure 7(b).

Consequently, we empirically tried different classifiers and ultimately opted for an AdaBoostClassifier [SB97] with decision tree. AdaBoostClassifier [SB97] is a popular ensemble learning method that combines the predictions of multiple weak classifiers, to create a strong classifier. In our case, the weak classifiers are decision trees, typically trees with limited depth. The AdaBoost algorithm works by iteratively training these decision trees, each time focusing more on the instances that were misclassified by previous trees. The final prediction is made by combining the weighted predictions of all the decision trees, resulting in improved accuracy and robustness compared to using a single classifier. We chose a large number of estimators (number of trees): 500 and a small depth: 4 as parameters for our decision tree. This results in relatively quick computation training (a few minutes) and robust outputted statistics during the testing phase.

We do not claim any optimality regarding our classifiers. In [GR24], the problem of error identification is also raised but not solved. Previous works have used decision tree classifiers and compared with template attacks [LPMS18], but only in term of the accuracy. Similarly, optimisation techniques, including AdaBoost, have also been used before for side channel attacks, as in [ZBHV21, XWZ18], but again only focusing on accuracy. Another alternative could have been the usage of enumeration techniques [Gro18] but hardly scalable with our (2 × 256 × k)-secret coefficients to recover.

**Comparison between classifiers.** We present in Figure 6 the accuracies obtained using templates, an AdaBoostClassifier with a decision tree, and decision trees (alone) tested across the four different chips and the two values of $\eta$. The source chip of the traces used for training is indicated at the beginning of each row, while the origin of the traces used for testing is shown at the bottom of each column. As expected, given the high level of leakage observed in Figure 3, we achieve high accuracy scores for all classifiers. The lowest accuracy achieved across all experiments is 89.94%, obtained with template classifier with $\eta_1 = 2$, learning on chip A, and targeting chip C. We observe generally good portability of the models across devices, with a small notable loss of accuracy when training on device C and targeting Devices A and B. This trend is consistent across all classifiers; in fact, model learning on chip C always performs the worst on traces from chips A and B. Lower scores are specifically observed when training on chip C and testing on chips A or B, or vice-versa. This trend is consistent across all classifiers, indicating a potential
portability difficulty between the models across different chips under these conditions. We also note that CNN and MLP achieved slightly lower accuracy scores (around 10% less) with models trained on chip B for $η_1 = 3$ compared to the other classifiers. In terms of accuracy, the decision tree combined with AdaBoost consistently performs as the best classifier accuracy-wise. However, since our goal is to obtain error-free values, we also computed the “highest incorrect class-specific probabilities” (see Step 1 of the classifying process) for each classifier and class. This allowed us to determine error-free recovered labels (see Step 2). From this analysis, we computed the number of recovered coefficients (see Step 3), with results being displayed in Figure 7. Despite their high accuracy, decision tree classifiers allow to recover only very few coefficients. This indicates that even when misclassified, some incorrect predictions are assigned probabilities just as high as correctly classified ones. The template attack achieves significantly better results, recovering up to 12.97% of the coefficients when both the attack and training are performed on the same chip (B) with $η_1 = 3$. However, the number of recovered coefficients is still too low to enable a full key recovery — see also Section 4. Due to the Hamming weight model, perfectly recovered coefficients can only be 0, -1 or -2 for $η_1 = 2$ and 0, -1 or 3 for $η_1 = 3$, see Table 4.

<figure><img src="image_8.png" /><figcaption>**Figure 6:** Accuracies of all tested classifiers for the four different chips and the two different values of $η_1$. Each row corresponds to the chip used for training, while each column indicates the chip used for testing. For each individual figure, left presents the results for $η_1 = 3$ and the right side presents the case for $η_1 = 2$.</figcaption></figure>

## 3.6 Attack phase with decision tree and AdaBoost

Our results are displayed on Figure 7. Training on chip A is shown in the first row, chip B in the second row, chip C in the third row, and chip D in the last row. Results for $η_1 = 3$ are on the left and on the right for $η_1 = 2$. In each subplot, we present the percentages of coefficients recovered perfectly (top left), with 2 possibilities (top right), with 3 possibilities (bottom left), and with 4 possibilities (bottom right, only for $η_1 = 3$). Training and testing on the same device allowed us to recover more than half of the coefficients. Additionally, portability between chip A, B and D showed good results, with once again more than half of the coefficients recovered. In all these cases, it results in successful key recovery
<figure><img src="image_9.png" /><figcaption>**Figure 7:** Results of our classifiers, trained and tested on power traces from four different chips (all of the same model): A, B, C and D. For each subfigure, the left side presents the case for $\eta_1 = 3$, and the right side presents the case for $\eta_1 = 2$. Each experiment shows four percentages: the top left indicates the percentage of recovered coefficients; the top right, bottom left, and bottom right indicate the percentages of coefficients reduced to two guesses, three guesses, and four possibilities, respectively. Legend appears at the top-right of the figure.</figcaption></figure>

as described in Section 4.3. For $\eta_1 = 2$, training on chip C and targeting chip B, and vice versa, does not always find enough coefficients to recover the secret key. A way to improve the portability of the interaction with the chip C could have been to use transfer learning techniques, as proposed in [GHG21]. However, this can not be done trivially with our chosen classifier. We also conducted multi-chip learning experiments using the same datasets. The results are available in Appendix B.

# 4 Key recovery

We now study the finalization of the attack, that is, how to complete the key recovery. For reusability, we provide formal proofs and descriptions. Recall that, in the primal attack, one rewrites the LWE instance ($\mathbf{A}, \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e} \bmod q$) as $[\mathbf{I}_m | \mathbf{A}| \mathbf{b}] \cdot (\mathbf{e}^t, \mathbf{s}^t, -1) = 0 \bmod q$. The principle for integrating the hints built from labels is depicted in Figure 8. In words, having $h_e$ hints on the coordinates of $\mathbf{e}$ give $h_e$ error-free (exact) equations, while $h_s$ hints for $\mathbf{s}$ amounts to removing columns in $\mathbf{A}$ and yields a system with $n - h_s$ unknowns. In the figure, at the step after “Reduce variables”, two regimes can be distinguished. If $h_e \ge n - h_s$ (“Way too many hints”), the system is determined and solved directly by matrix inversion. Else, the system can be reduced to a LWE-instance of smaller dimension (Section 4.2). If the dimension is low enough, we solve it using lattice reduction.
<figure><img src="image_10.png" /><figcaption>**Figure 8:** New LWE instance created from hints.</figcaption></figure>

## 4.1 "Way too many hints"

A $[m, n, q]$-linear code is a linear subspace $\mathcal{C}$ of $\mathbb{Z}_q^m$ with dimension $n$. Any subspace of the shape $\mathbf{a} + \mathcal{C}$ for $\mathbf{a} \in \mathbb{Z}_q^m$ and a $[m, n, q]$-linear code $\mathcal{C}$ is called an affine $[m, n, q]$-code of dimension $n$. With this description, one can see that a reasonable LWE instance $(\mathbf{A}, \mathbf{A}\mathbf{s} + \mathbf{e})$ implies that $(\mathbf{e}^t, \mathbf{s}^t, -1)$ is a word in an $n$-dimensional affine code. For the sake of reusability we gather this (certainly folklore) observation in the next lemma.

**Lemma 1.** Let $(\mathbf{A}, \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}) \in \mathbb{Z}_q^{m \times n} \times \mathbb{Z}_q^m$ be a LWE instance where $\mathbf{e}, \mathbf{s}$ have been sampled from distributions with support in $\mathbb{Z} \cap [-\eta, \eta]$, for some integer $\eta < \frac{q}{2}$. Then $(\mathbf{e}^t, \mathbf{s}^t, -1)$ is a word in a $[n+m+1, n, q]$-affine code.

We provide a proof for completeness, deferred to Appendix A. A direct application of this lemma is that if $n$ linearly independent perfect hints of $(\mathbf{s}, \mathbf{e}) \in \mathbb{Z}^{n+m}$ are given, then this completely determines the entire vector, which should then be computable by linear algebra over $\mathbb{Z}_q$- that is, inverting a matrix over $\mathbb{Z}_q$. Equivalently, the $\text{Coord}^n$-LWE$_{n,m,q,\eta}$ is easy. Two extreme but simple examples are: if $\mathbf{s}$ is entirely known, then $\mathbf{e} = \mathbf{b} - \mathbf{A}\mathbf{s}$, or if $n$ components of $\mathbf{e}$ are given, then we have $n$ noise-free linear equations in $\mathbf{s}$. Specifically for KYBER, we have $n = m$ and so getting half of the coordinates of $(\mathbf{s}, \mathbf{e})$ is enough to break the instance by linear algebra – this corresponds to $h_{\mathbf{s}} + h_{\mathbf{e}} \ge n$. From Figure 7, a single trace from our classifier often gives us more coordinates than this threshold.

## 4.2 Dimension reduction from perfect hints on coordinates

In this section, our classifiers gives us $h_{\mathbf{s}} + h_{\mathbf{e}} = n - \kappa$ perfect hints (from this amount of known labels, as explained in Section 3.5), with $\kappa > 0$. The next lemma (stated for reusability) and its proof shows how to turn this information into a new LWE instance of smaller dimension. Interpreted more formally, it is a reduction from $\text{Coord-LWE}_{n,m,q}$ to $\text{LWE}_{\kappa,h_{\mathbf{e}},q}$. The proof (in Appendix A) amounts to rewriting the assumptions. Its steps are depicted in Figure 8.

**Lemma 2.** Let $(\mathbf{A} \leftarrow \mathbb{Z}_q^{m \times n}, \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e} \in \mathbb{Z}_q^m)$ be a LWE instance. For an integer $0 < \kappa < n$, assume that $n - \kappa$ coordinates of the vector $(\mathbf{s}, \mathbf{e})$ are known, with $h_{\mathbf{s}}$ the number of known coordinates in $\mathbf{s}$ and $h_{\mathbf{e}}$ the number of known coordinates in $\mathbf{e}$, i.e. $n - \kappa = h_{\mathbf{s}} + h_{\mathbf{e}}$. Then recovering fully $(\mathbf{s}, \mathbf{e})$ reduces to solving a LWE instance with "secret" in $\mathbb{Z}^\kappa$ and ambient dimension $h_{\mathbf{e}}$.

The primal attack against the resulting instance from Lemma 2 is summarized by
Equality (3), and so an attacker would run lattice reduction over the basis matrix

$$ \mathbf{B}'' = \begin{bmatrix} q\mathbf{I}_{h_e} & \mathbf{0} & \mathbf{0} \\ -(\mathbf{A}'')^t & \mathbf{I}_\kappa & \mathbf{0} \\ -(\mathbf{b}'')^t & \mathbf{0} & \mathbf{1} \end{bmatrix} \in \mathbb{Z}^{(h_e+\kappa+1) \times (h_e+\kappa+1)}. \quad (2) $$

Note that in our side-channel attack, we usually obtain $h_s \approx h_e$. We can obtain a theoretical estimate of the number of hints we are allowed to lose while maintaining the feasibility of a full key recovery. Indeed, a prediction for $\beta$ is obtained using the inequality (1) for the lattice $\Lambda''$ with $\dim(\Lambda'') = h_e + \kappa + 1 = n - h_s + 1$, $\det(\Lambda'') = q^{h_e}$ and $\lambda_1(\Lambda'') = \|(e'')^t, (s'')^t, -1)\| = \|(s_i^t, 1)\|$. Figure 10 also displays the concrete blocksize $\beta$ required for a successful attack on this new LWE instance $(\mathbf{A}'', \mathbf{b}'')$ from Equality (3).

## 4.3 Concrete results and full attack

At a high-level description, there are two main phases in our attack: the training/classification phase, and then the actual attack. The whole flow is depicted in Figure 9. The training phase is done as described in Section 3, so in this section we will focus rather on detailing how the attack is concluded.

After training, our classifier is ready, and we are mimicking the execution of the implementation of KYBER on a target chip, taking $2 \times k$ traces of CBD executions. After analysing the captured power trace (as described in Section 3), we obtain a list of guesses for each coefficient of $\mathbf{x} = (\mathbf{s}, \mathbf{e})$. Each list contains one, two, three or four guesses. If the list contains only one guess, then this guess is surely the value of the corresponding coefficient. Next, we looked at the total proportion of recovered coefficients in $\mathbf{x}$. From Figure 7 (a) (top left corners of the squares), with the Decision Tree + AdaBoost method, these proportions are often large (sometimes more than 68%). Our worst results being about 37% of recovered coefficients.

The next step is to process these perfect hints on the secret $\mathbf{x}$. Concretely, our code attached in Supplementary Material generates from these hints a Coord-LWE instance (represented by matrix as $\mathbf{B}'$), following Figure 8. In KYBER, we have $n = m$; depending

<figure><img src="image_11.png" /><figcaption>**Figure 9:** End-to-end process illustration from power traces acquisition to key recovery.</figcaption></figure>
<figure><img src="image_12.png" /><figcaption>**Figure 10:** The x-axis represents the ratio between the number of hint on the secret (or equivalently on the error in our context, i.e. $h_s = h_e$) of the initial LWE instance and its dimension $n$. The y-axis represents the corresponding predicted blocksize $\beta$ required for a key recovery with BKZ-$\beta$. The closer $h_s \approx h_e$ is to $n/2$, the smaller $\beta$ is needed, the easier the primal attack becomes. Dots display the blocksize we used to recover the keys.</figcaption></figure>

on the proportion $\frac{h_s+h_e}{2n}$, we then select a method to solve the instance. If the proportion is higher than $\frac{n}{n+m} = \frac{1}{2}$, Section 4.1 shows that “Linear Algebra” (Gaussian elimination) over $\mathbb{Z}_q$ will recover the rest of the coefficients. Else, we use lattice reduction (LLL or BKZ) from the public implementation of fplll in sagemath. A starting blocksize is predicted from Equation (1). As seen on Figure 10, while reasonably accurate, the prediction can be too optimistic in practice. If lattice reduction does not find the key (we can check this efficiently with the public key), we re-run with a larger blocksize. This whole process is almost always successful, as shown in Figure 11. Ultimately, there are rare cases where we could not recover the key. This may be either because the blocksize was too small (we set a time threshold for how long we try lattice reduction), or because there were errors in our guesses in the end.

## 4.4 Countermeasure

We found two references to secure implementations of KYBER against side-channel attacks in the literature. In the first one, Joppe et al. [BGR$^{+21}$] proposed a masked implementation of the encryption and decryption but not the key generation. In fact, they write: “since the key generation only processes the secret key once, and masking is commonly aimed at mitigating multi-trace attacks, we omit its description here”. Furthermore, in their code, the CBD is called to sample shares, so they do not need a masked implementation for the encryption or the decryption.

In the second one, Heinz et al. [HKL$^{+22}$] proposed a full open-source masked implementation of KYBER. This time, they proposed a masked implementation of the CBD functions. But, as in [BGR$^{+21}$], they do not include in their threat model the attack that uses only one power trace of the key generation. In fact, in their code, the key generation does not use the masked implementation of the CBD but the usual one.

We show that recovering enough information about the secret coefficients using only one power trace is feasible and leads to secret key recovery. Therefore, the CBD functions must be secured against side-channel attacks not only during the encryption or decryption but also during the key generation.
<figure><img src="image_13.png" /><figcaption>**Figure 11:** Key recovery percentages for the three security levels and our four models (one per chip). Bottom-right square explains the content of all subsquares; top-left value is the percentage of key we can not recover. Other values are the percentages of keys recovered using each method.</figcaption></figure>

# 5 Conclusion

We proposed an end-to-end methodology to recover the secret key of KYBER using profiled power side-channel leakage from the key generation process. Since this step is done only once, our attack requires only a single trace. We conducted a side-channel analysis of KYBER's CBD sampler, followed by either linear algebra or lattice reduction techniques. Our analysis covered both samplers, at all security levels. We also assessed the portability of our attack across four different chips, acquiring a large number of traces (20k per chip, resulting in 5120k coefficients). Finally, we proposed a technique to select error-free results from the outputted statistics of a decision tree classifier with the AdaBoost strategy, addressing a problem left open in [GR24].

We focused exclusively on KYBER's CBD sampler, but similar samplers exist in other lattice-based cryptographic algorithms (e.g. HAWK and SEAL, analyzed in [GR24] and [AKP+22b]). Our method can be applied to these two samplers to enhance their attacks. Generally, our approach is suitable for single-trace power analysis attacks, especially when the manipulated data must be learned and errors are not tolerated.

Given the high average success rate of our attack, protecting the CBD sampler in KYBER at any security level is imperative. While this is especially true for the higher security levels where $\eta_1 = 2$, we have demonstrated high success rates as well against KYBER-512. It is likely that our attack could be extended to the calls to CBD during encapsulation/decapsulation – in any case, the recent [PK25] targets these calls as well, with already strong results. In other words, any call to CBD must be protected. Masking is the most common countermeasure to defeat side-channel attacks. It is less efficient in a single-trace setup than in a multi-trace one; however, it still increases the difficulty of
mounting the attack. Therefore, we recommend to combine shuffling with masking.

We identified a good classifier (decision tree classifier with the AdaBoost strategy) and compared it with other conventional side-channel methods: Gaussian template and decision tree classifier. Another avenue for future research is its enhancement. A natural approach would be to combine our work with the adaptive template strategy from [PK25], towards achieving the best of both world: further improving our error-free selection, reducing their requirement on accuracy. However, there is a possibility that new distinguishers [ZBC<sup>+</sup>23, SM23] could outperform our methods, not necessarily in terms of accuracy but in achieving error-free identification.

## Acknowledgments

We thank the reviewers and our shepherd for their constructive remarks and helpful suggestions. We thank Jawed Khelif for his assistance during the early stage of our research. This work was supported by the French National Research Agency (ANR) under grant agreements ANR-20-CE39-0010 (IDROMEL) and ANR-22-PETQ-0008 (PQ-TLS).

## References

[ADPS16] Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum key {Exchange—A} new hope. In *25th USENIX Security Symposium (USENIX Security 16)*, pages 327–343, 2016.

[AGVW17] Martin R Albrecht, Florian Göpfert, Fernando Virdia, and Thomas Wunderer. Revisiting the expected cost of solving usvp and applications to lwe. In *Advances in Cryptology–ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I 23*, pages 297–322. Springer, 2017.

[AKP<sup>+</sup>22a] Furkan Aydin, Emre Karabulut, Seetal Potluri, Erdem Alkim, and Aydin Aysu. RevEAL: Single-trace side-channel leakage of the SEAL homomorphic encryption library. Cryptology ePrint Archive, Paper 2022/204, 2022.

[AKP<sup>+</sup>22b] Furkan Aydin, Emre Karabulut, Seetal Potluri, Erdem Alkim, and Aydin Aysu. Reveal: Single-trace side-channel leakage of the SEAL homomorphic encryption library. In Cristiana Bolchini, Ingrid Verbauwhede, and Ioana Vatajelu, editors, *2022 Design, Automation & Test in Europe Conference & Exhibition, DATE 2022, Antwerp, Belgium, March 14-23, 2022*, pages 1527–1532. IEEE, 2022.

[AP12] Jacob Alperin-Sheriff and Chris Peikert. Circular and KDM security for identity-based encryption. In Marc Fischlin, Johannes Buchmann, and Mark Manulis, editors, *Public Key Cryptography - PKC 2012 - 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, May 21-23, 2012. Proceedings*, volume 7293 of *Lecture Notes in Computer Science*, pages 334–352. Springer, 2012.

[BBB<sup>+</sup>24] Estuardo Alpirez Bock, Gustavo Banegas, Chris Brzuska, Lukasz Chmielewski, Kirthivaasan Puniamurthy, and Milan Sorf. Breaking dpa-protected kyber via the pair-pointwise multiplication. In Christina Pöpper and Lejla Batina, editors, *Applied Cryptography and Network Security - 22nd International Conference, ACNS 2024, Abu Dhabi, United Arab Emirates, March 5-8, 2024,*
*Proceedings, Part II*, volume 14584 of *Lecture Notes in Computer Science*, pages 101–130. Springer, 2024.

[BCO04] Eric Brier, Christophe Clavier, and Francis Olivier. Correlation power analysis with a leakage model. In Marc Joye and Jean-Jacques Quisquater, editors, *Cryptographic Hardware and Embedded Systems - CHES 2004: 6th International Workshop Cambridge, MA, USA, August 11-13, 2004. Proceedings*, volume 3156 of *Lecture Notes in Computer Science*, pages 16–29. Springer, 2004.

[BDK$^{+}$17] Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. Crystals - kyber: a cca-secure module-lattice-based kem. Cryptology ePrint Archive, Paper 2017/634, 2017. https://eprint.iacr.org/2017/634.

[BGR$^{+}$21] Joppe W. Bos, Marc Gourjon, Joost Renes, Tobias Schneider, and Christine van Vredendaal. Masking kyber: First- and higher-order implementations. *IACR Trans. Cryptogr. Hardw. Embed. Syst.*, 2021(4):173–214, 2021.

[BGV14] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. *ACM Transactions on Computation Theory (TOCT)*, 6(3):1–36, 2014.

[BNGD23] Linus Backlund, Kalle Ngo, Joel Gärtner, and Elena Dubrova. Secret key recovery attack on masked and shuffled implementations of crystals-kyber and saber. In Jianying Zhou, Lejla Batina, Zengpeng Li, Jingqiang Lin, Eleonora Losiouk, Suryadipta Majumdar, Daisuke Mashima, Weizhi Meng, Stjepan Picek, Mohammad Ashiqur Rahman, Jun Shao, Masaki Shimaoka, Ezekiel O. Soremekun, Chunhua Su, Je Sen Teh, Aleksei Udovenko, Cong Wang, Leo Yu Zhang, and Yury Zhauniarovich, editors, *Applied Cryptography and Network Security Workshops - ACNS 2023 Satellite Workshops, ADSC, AIBlock, AIHWS, AIoTS, CIMSS, Cloud S&P, SCI, SecMT, SiMLA, Kyoto, Japan, June 19-22, 2023, Proceedings*, volume 13907 of *Lecture Notes in Computer Science*, pages 159–177. Springer, 2023.

[CKK$^{+}$21] Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim, Joohee Lee, Junbum Shin, and Yongsoo Song. Lattice-based secure biometric authentication for hamming distance. In Joonsang Baek and Sushmita Ruj, editors, *Information Security and Privacy - 26th Australasian Conference, ACISP 2021, Virtual Event, December 1-3, 2021, Proceedings*, volume 13083 of *Lecture Notes in Computer Science*, pages 653–672. Springer, 2021.

[CRR02] Suresh Chari, Josyula R. Rao, and Pankaj Rohatgi. Template attacks. In Burton S. Kaliski Jr., Çetin Kaya Koç, and Christof Paar, editors, *Cryptographic Hardware and Embedded Systems - CHES 2002, 4th International Workshop, Redwood Shores, CA, USA, August 13-15, 2002, Revised Papers*, volume 2523 of *Lecture Notes in Computer Science*, pages 13–28. Springer, 2002.

[DGHK23] Dana Dachman-Soled, Huijing Gong, Tom Hanson, and Hunter Kippen. Revisiting security estimation for LWE with hints from a geometric perspective. In Helena Handschuh and Anna Lysyanskaya, editors, *Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part V*, volume 14085 of *Lecture Notes in Computer Science*, pages 748–781. Springer, 2023.
[DPPvW22] Léo Ducas, Eamonn W. Postlethwaite, Ludo N. Pulles, and Wessel P. J. van Woerden. Hawk: Module LIP makes lattice signatures fast, compact and simple. In Shweta Agrawal and Dongdai Lin, editors, *Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part IV*, volume 13794 of Lecture Notes in Computer Science, pages 65-94. Springer, 2022.

[DSDGR20] Dana Dachman-Soled, Léo Ducas, Huijing Gong, and Mélissa Rossi. Lwe with side information: attacks and concrete security estimation. In *Annual International Cryptology Conference*, pages 329-358. Springer, 2020.

[dt23] The FPLLL development team. fplll, a lattice reduction library, Version: 5.5.0. Available at https://github.com/fplll/fplll, 2023.

[GHG21] Christophe Genevey-Metat, Annelie Heuser, and Benoît Gérard. Train or adapt a deeply learned profile? In Patrick Longa and Carla Ràfols, editors, *Progress in Cryptology - LATINCRYPT 2021 - 7th International Conference on Cryptology and Information Security in Latin America, Bogotá, Colombia, October 6-8, 2021, Proceedings*, volume 12912 of Lecture Notes in Computer Science, pages 213-232. Springer, 2021.

[GR24] Morgane Guerreau and Mélissa Rossi. A not so discrete sampler: Power analysis attacks on HAWK signature scheme. *IACR Trans. Cryptogr. Hardw. Embed. Syst.*, 2024(4):156-178, 2024.

[Gro18] Vincent Grosso. Scalable key rank estimation (and key enumeration) algorithm for large keys. In Begül Bilgin and Jean-Bernard Fischer, editors, *Smart Card Research and Advanced Applications, 17th International Conference, CARDIS 2018, Montpellier, France, November 12-14, 2018, Revised Selected Papers*, volume 11389 of Lecture Notes in Computer Science, pages 80-94. Springer, 2018.

[HKL$^{+22}$] Daniel Heinz, Matthias J. Kannwischer, Georg Land, Thomas Pöppelmann, Peter Schwabe, and Amber Sprenkels. First-order masked kyber on ARM cortex-m4. *IACR Cryptol. ePrint Arch.*, page 58, 2022.

[JNWD24] Sönke Jendral, Kalle Ngo, Ruize Wang, and Elena Dubrova. Breaking sca-protected crystals-kyber with a single trace. In *IEEE International Symposium on Hardware Oriented Security and Trust, HOST 2024, Tysons Corner, VA, USA, May 6-9, 2024*, pages 70-73. IEEE, 2024.

[KAA21] Emre Karabulut, Erdem Alkim, and Aydin Aysu. Single-trace side-channel attacks on $\omega$-small polynomial sampling: With applications to ntru, NTRU prime, and CRYSTALS-DILITHIUM. In *IEEE International Symposium on Hardware Oriented Security and Trust, HOST 2021, Tysons Corner, VA, USA, December 12-15, 2021*, pages 35-45. IEEE, 2021.

[KLSS23] Duhyeong Kim, Dongwon Lee, Jinyeong Seo, and Yongsoo Song. Toward practical lattice-based proof of knowledge from hint-mlwe. In Helena Handschuh and Anna Lysyanskaya, editors, *Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part V*, volume 14085 of Lecture Notes in Computer Science, pages 549-580. Springer, 2023.
[KPR+] Matthias J. Kannwischer, Richard Petri, Joost Rijneveld, Peter Schwabe, and Ko Stoffelen. PQM4: Post-quantum crypto library for the ARM Cortex-M4. https://github.com/mupq/pqm4.

[LKK$^{+}$18] Joohee Lee, Dongwoo Kim, Duhyeong Kim, Yongsoo Song, Junbum Shin, and Jung Hee Cheon. Instant privacy-preserving biometric authentication for hamming distance. *IACR Cryptol. ePrint Arch.*, page 1214, 2018.

[LPMS18] Liran Lerman, Romain Poussier, Olivier Markowitch, and François-Xavier Standaert. Template attacks versus machine learning revisited and the curse of dimensionality in side-channel analysis: extended version. *J. Cryptogr. Eng.*, 8(4):301–313, 2018.

[LS15] Adeline Langlois and Damien Stehlé. Worst-case to average-case reductions for module lattices. *Designs, Codes and Cryptography*, 75(3):565–599, 2015.

[MN23] Alexander May and Julian Nowakowski. Too many hints–when lll breaks lwe. In *International Conference on the Theory and Application of Cryptology and Information Security*, pages 106–137. Springer, 2023.

[Odl90] Andrew M Odlyzko. The rise and fall of knapsack cryptosystems. *Cryptology and computational number theory*, 42(2), 1990.

[OPW11] Adam O'Neill, Chris Peikert, and Brent Waters. Bi-deniable public-key encryption. In Phillip Rogaway, editor, *Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings*, volume 6841 of *Lecture Notes in Computer Science*, pages 525–542. Springer, 2011.

[oSN23] National Institute of Standards and Technology (NIST). Module-lattice-based keyencapsulation mechanism standard, 2023.

[PK25] Eric Chun-Yu Peng and Markus G. Kuhn. Adaptive template attacks on the kyber binomial sampler. *IACR Transactions on Cryptographic Hardware and Embedded Systems*, 2025(3):470–492, Jun. 2025.

[PP19] Peter Pessl and Robert Primas. More practical single-trace attacks on the number theoretic transform. In *Progress in Cryptology-LATINCRYPT 2019: 6th International Conference on Cryptology and Information Security in Latin America, Santiago de Chile, Chile, October 2-4, 2019, Proceedings 6*, pages 130–149. Springer, 2019.

[PPM17] Robert Primas, Peter Pessl, and Stefan Mangard. Single-trace side-channel attacks on masked lattice-based encryption. In *Cryptographic Hardware and Embedded Systems-CHES 2017: 19th International Conference, Taipei, Taiwan, September 25-28, 2017, Proceedings*, pages 513–533. Springer, 2017.

[QLZ$^{+}$23] Zehua Qiao, Yuejun Liu, Yongbin Zhou, Mingyao Shao, and Shuo Sun. When NTT meets SIS: efficient side-channel attacks on dilithium and kyber. *IACR Cryptol. ePrint Arch.*, page 1866, 2023.

[RBRC22] Prasanna Ravi, Shivam Bhasin, Sujoy Sinha Roy, and Anupam Chattopadhyay. On exploiting message leakage in (few) NIST PQC candidates for practical message recovery attacks. *IEEE Trans. Inf. Forensics Secur.*, 17:684–699, 2022.

[Reg09] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. *Journal of the ACM (JACM)*, 56(6):1–40, 2009.
[RLMI21] Thomas Roche, Victor Lomné, Camille Mutschler, and Laurent Imbert. A side journey to titan. In Michael D. Bailey and Rachel Greenstadt, editors, *30th USENIX Security Symposium, USENIX Security 2021, August 11-13, 2021*, pages 231–248. USENIX Association, 2021.

[RRCB20] Prasanna Ravi, Sujoy Sinha Roy, Anupam Chattopadhyay, and Shivam Bhasin. Generic side-channel attacks on cca-secure lattice-based pke and kems. *IACR transactions on cryptographic hardware and embedded systems*, pages 307–335, 2020.

[SB97] Holger Schwenk and Yoshua Bengio. Adaboosting neural networks: Application to on-line character recognition. In Wulfram Gerstner, Alain Germond, Martin Hasler, and Jean-Daniel Nicoud, editors, *Artificial Neural Networks - ICANN '97, 7th International Conference, Lausanne, Switzerland, October 8-10, 1997, Proceedings*, volume 1327 of *Lecture Notes in Computer Science*, pages 967–972. Springer, 1997.

[SEA19] Microsoft SEAL (release 3.2). https://github.com/Microsoft/SEAL, February 2019. Microsoft Research, Redmond, WA.

[SM23] Marvin Staib and Amir Moradi. Deep learning side-channel collision attack. *IACR Trans. Cryptogr. Hardw. Embed. Syst.*, 2023(3):422–444, 2023.

[WD23] Ruize Wang and Elena Dubrova. A side-channel secret key recovery attack on crystals-kyber using k chosen ciphertexts. In Said El Hajji, Sihem Mesnager, and El Mamoun Souidi, editors, *Codes, Cryptology and Information Security - 4th International Conference, C2SI 2023, Rabat, Morocco, May 29-31, 2023, Proceedings*, volume 13874 of *Lecture Notes in Computer Science*, pages 109–128. Springer, 2023.

[XPR+21] Zhuang Xu, Owen Pemberton, Sujoy Sinha Roy, David Oswald, Wang Yao, and Zhiming Zheng. Magnifying side-channel leakage of lattice-based cryptosystems with chosen ciphertexts: The case study of kyber. *IEEE Transactions on Computers*, 71(9):2163–2176, 2021.

[XWZ18] Mengmeng Xu, Liji Wu, and Xiangmin Zhang. Power analysis on sm4 with boosting methods. In *2018 12th IEEE International Conference on Anti-counterfeiting, Security, and Identification (ASID)*, pages 188–191, 2018.

[YK21] Shih-Chun You and Markus G. Kuhn. Single-trace fragment template attack on a 32-bit implementation of kecckak. In Vincent Grosso and Thomas Pöppelmann, editors, *Smart Card Research and Advanced Applications - 20th International Conference, CARDIS 2021, Lübeck, Germany, November 11-12, 2021, Revised Selected Papers*, volume 13173 of *Lecture Notes in Computer Science*, pages 3–23. Springer, 2021.

[ZBC+23] Gabriel Zaid, Lilian Bossuet, Mathieu Carbone, Amaury Habrard, and Alexandre Venelli. Conditional variational autoencoder based on stochastic attacks. *IACR Trans. Cryptogr. Hardw. Embed. Syst.*, 2023(2):310–357, 2023.

[ZBHV21] Gabriel Zaid, Lilian Bossuet, Amaury Habrard, and Alexandre Venelli. Efficiency through diversity in ensemble models applied to side-channel attacks - A case study on public-key algorithms -. *IACR Trans. Cryptogr. Hardw. Embed. Syst.*, 2021(3):60–96, 2021.
## A Additional proofs for Section 4

*Proof of Lemma 1.* The matrix $[\mathbf{I}_m|\mathbf{A}|\mathbf{b}]$ has row-rank $m$ and is thus the parity-check matrix of a linear code $\mathcal{C}$ of dimension $n+m+1$ and length $n+1$. More precisely, $\mathcal{C}$ is the set of word $\mathbf{w} \in \mathbb{Z}_q^{n+m+1}$ such that $[\mathbf{I}_m|\mathbf{A}|\mathbf{b}] \cdot \mathbf{w} = 0$. By assumption on the distributions, we have $(\mathbf{e}^t \mod q, \mathbf{s}^t \mod q, -1) = (\mathbf{e}^t, \mathbf{s}^t, -1)$ (equality “over the integers”). As the last coordinate is fixed, this means that the word $(\mathbf{e}^t, \mathbf{s}^t, -1)$ belongs to the affine code $\mathcal{C} \cap (\mathbf{c} + H)$, where $\mathbf{c}$ is the last “canonical basis” vector of $\mathbb{Z}_q^{n+m+1}$ and $H$ is the linear subspace of vectors having a 0 as last coordinate. Having non-empty intersection, this affine code can be written $\mathbf{x} + (\mathcal{C} \cap H)$, for any $\mathbf{x}$ in the intersection, so it remains to prove that $\dim \mathcal{C} \cap H = n$. This comes from the fact that $\mathcal{C} \not\subseteq H$, as e.g. $(\mathbf{b}, 0, \dots, 0, -1)^t \in \mathcal{C} \setminus H$. This implies that $\mathcal{C} + H = \mathbb{Z}_q^{n+m+1}$, and we conclude with Grassmann’s formula $\dim(\mathcal{C} + H) = \dim \mathcal{C} + \dim H - \dim(\mathcal{C} \cap H)$. $\square$

*Proof of Lemma 2.* Let $I$, resp. $J$ be subsets of $[n]$, resp. $[m]$ of cardinality $h_s$, resp. $h_e$ corresponding to the indices of the known coordinates of $\mathbf{s}$ resp. $\mathbf{e}$. Let $\mathbf{e}'$ be the vector of known coordinates of $\mathbf{e}$, and 0 everywhere else, and let $\mathbf{b}' = \mathbf{b} - \mathbf{e}'$. Then we have a noise-free linear system $\mathbf{A}_{[J, \bar{I}]s_I} = \mathbf{b}'_J$. Let $\mathbf{A}' := \mathbf{A}_{[J, \bar{I}]}$, then $\mathbf{A}' \in \mathbb{Z}_q^{h_e \times (n-h_s)}$. Since $h_e + h_s < n$, $\mathbf{A}'$ is a “long” or “fat” matrix, and of rank $h_e$ since $\mathbf{A}$ is full-rank. We compute its row-reduced echelon form $[\mathbf{I}_{h_e}|\mathbf{A}'']$, with transformation matrix $\mathbf{T}$, and let $\mathbf{b}'' := \mathbf{T}\mathbf{b}'$. Parsing properly the coordinates of $\mathbf{s}_I$ as $(\mathbf{s}'', \mathbf{e}'') \in \mathbb{Z}_q^{\kappa} \times \mathbb{Z}_q^{h_e}$, this gives us

$$ (\mathbf{I}_{h_e} \| \mathbf{A}'') \cdot \left( \frac{\mathbf{e}''}{\mathbf{s}''} \right) = \mathbf{b}'' \mod q, \qquad (3) $$

and we obtain the LWE instance $(\mathbf{A}'', \mathbf{b}'' = \mathbf{A}''\mathbf{s}'' + \mathbf{e}'')$, with $\mathbf{s}'' \in \mathbb{Z}_q^{\kappa}$ and $\mathbf{e}'' \in \mathbb{Z}_q^{h_e}$ as claimed. $\square$

## B Experimental results on multi-chip training (complement for Section 3)

We conducted additional experiments to study the effects of multi-chip training on our approach. The principle is to use traces from multiple chips during the training phase of a classifier. In our case, we used the three non-targeted chips. As for all the other experiments, even when traces come from the same chips, a trace can be used only for training or testing, never for both phases. The overall results are displayed in Figures 12 and 13 in the same manner as in Figures 6 and 7, respectively. However this time we only display the decision tree classifier with AdaBoost. In Figure 12, we display the accuracies we obtained, and in Figure 13 the percentage of identified hints. For both, on the left we have the chips we learned from, and at the bottom the chip we used for testing. We observe that the accuracies and the percentages of recovered hints are better in the multi-chip training setting than with single-chips. This leads to recovering 100% keys once the hinted instances are built and given to our post-processing. For most of the instances, linear algebra (Gaussian elimination) was enough, and the remaining ones were solved using LLL (BKZ was no more needed; for simplicity one can consider LLL as BKZ-2). This results in a speedup of this phase. Additionally, this shows that portability could be increased using a multi-chip setting, with a computation overhead at the training phase multiplied by the number of used chips. Furthermore, it could also serve as a potential solution in cases of lower signal-to-noise ratio.
<figure><img src="image_14.png" /><figcaption>**Figure 12:** Accuracies in multi-chips setting</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>**Figure 13:** Percentages of recovered hints in multi-chips setting</figcaption></figure>