# Exploiting ROLLO's constant-time implementations with a single-trace analysis

Agathe Cheriere, Lina Mortajine, Tania Richmond, Nadia El Mrabet

► To cite this version:

Agathe Cheriere, Lina Mortajine, Tania Richmond, Nadia El Mrabet. Exploiting ROLLO's constant-time implementations with a single-trace analysis. Designs, Codes and Cryptography, 2023, Coding and Cryptography 2022, pp.1-26. 10.1007/s10623-023-01227-3. hal-04166638

HAL Id: hal-04166638

https://hal.science/hal-04166638

Submitted on 1 Mar 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Exploiting ROLLO's constant-time implementations with a single-trace analysis

Agathe Cheriere, Lina Mortajine, Tania Richmond, Nadia El Mrabet

► To cite this version:

Agathe Cheriere, Lina Mortajine, Tania Richmond, Nadia El Mrabet. Exploiting ROLLO's constant-time implementations with a single-trace analysis. Designs, Codes and Cryptography, 2023, Coding and Cryptography 2022, pp.1-26. 10.1007/s10623-023-01227-3. hal-04166638

HAL Id: hal-04166638

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

Submitted on 1 Mar 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
Exploiting ROLLO's Constant-Time
Implementations with a Single-Trace Analysis

Agathe Cheriere¹*, Lina Mortajine²,³*, Tania Richmond⁴,⁵*
and Nadia El-Mrabet³*

¹*CAPSULE, CNRS, IRISA, 263 Avenue Général Leclerc,
Rennes, 35000, France.

2* Wisekey Semiconductors, Arteparc de Bachasson, Bâtiment A,
Meyreuil, 13590, France.

3\* SAS, Mines Saint-Etienne, CEA-Tech, 880, route de Mimet,
Gardanne, 13541, France.

4\* DGA - Maîtrise de l'Information, BP7, Rennes, 35998, France.

5\* Institute of Exact and Applied Sciences, University of New
Caledonia, BP R4, Nouméa Cedex, 98851, France.

*Corresponding author(s). E-mail(s): agathe.cheriere@irisa.fr; lina.mortajine@gmail.com; tania.richmond@unc.nc; nadia.el-mrabet@emse.fr;

**Abstract**

ROLLO, for Rank-Ouroboros, LAKE and LOCKER, was a candidate to the second round of the National Institute of Standards and Technology (NIST) Post-Quantum Cryptography (PQC) standardization process. In the lastest update in April 2020, there was a key-encapsulation mechanism (ROLLO-I) and a public-key encryption scheme (ROLLO-II). In this paper, we propose a side-channel attack to recover the syndrome during the decapsulation process of ROLLO-I. From this syndrome, we explain how to recover the private key. We target two constant-time implementations: the C reference implementation and a C implementation available on *GitHub*. By capturing power measurements during the execution of the Gaussian elimination function, we are able to extract from a single trace each element of the syndrome. This attack can also be applied to the decryption process of ROLLO-II. Finally, we give countermeasures based on masking and randomization to protect future implementations. We also provide their impact regarding the execution time.
Exploiting ROLLO's Constant-Time
Implementations with a Single-Trace Analysis

Agathe Cheriere¹*, Lina Mortajine²,³*, Tania Richmond⁴,⁵*
and Nadia El-Mrabet³*

¹*CAPSULE, CNRS, IRISA, 263 Avenue Général Leclerc,
Rennes, 35000, France.

2* Wisekey Semiconductors, Arteparc de Bachasson, Bâtiment A,
Meyreuil, 13590, France.

3* SAS, Mines Saint-Etienne, CEA-Tech, 880, route de Mimet,
Gardanne, 13541, France.

4\* DGA - Maîtrise de l'Information, BP7, Rennes, 35998, France.

5\* Institute of Exact and Applied Sciences, University of New
Caledonia, BP R4, Nouméa Cedex, 98851, France.

*Corresponding author(s). E-mail(s): agathe.cheriere@irisa.fr; lina.mortajine@gmail.com; tania.richmond@unc.nc; nadia.el-mrabet@emse.fr;

Abstract

ROLLO, for Rank-Ouroboros, LAKE and LOCKER, was a candidate to the second round of the National Institute of Standards and Technology (NIST) Post-Quantum Cryptography (PQC) standardization process. In the lastest update in April 2020, there was a key-encapsulation mechanism (ROLLO-I) and a public-key encryption scheme (ROLLO-II). In this paper, we propose a side-channel attack to recover the syndrome during the decapsulation process of ROLLO-I. From this syndrome, we explain how to recover the private key. We target two constant-time implementations: the C reference implementation and a C implementation available on *GitHub*. By capturing power measurements during the execution of the Gaussian elimination function, we are able to extract from a single trace each element of the syndrome. This attack can also be applied to the decryption process of ROLLO-II. Finally, we give countermeasures based on masking and randomization to protect future implementations. We also provide their impact regarding the execution time.
## 2 Side-Channel Attack on ROLLO PQC scheme

**Keywords:** Side-Channel Attack, Power Consumption Analysis, ROLLO, Key-Recovery Attack, Rank Metric, LRPC Codes

# 1 Introduction

Nowadays number theory based cryptography, like RSA [17] or ECDSA [11], is efficient but weak against the Shor's quantum algorithm [19]. The existence of quantum algorithms pushed the National Institute of Standards and Technology (NIST) to anticipate the time when an efficient quantum computer will be able to execute these algorithms and break commonly used public-key cryptography. In late 2016, NIST started the Post-Quantum Cryptography (PQC) standardization process to get signatures and, key encapsulation mechanisms (KEM) or public-key encryption schemes (PKE), resisting to both classical and quantum attacks. Among the historical schemes, as McEliece [14] or NTRU [10], there are recent proposals based on rank metric. Error-correcting codes in rank metric allow to reduce some drawbacks of Hamming metric, like the key-sizes. In the second round of this standardization process, there were two proposals in rank metric, namely ROLLO [1] and RQC [15]. Both were not selected for the third round due to some algebraic attacks [5, 6]. Nonetheless, NIST encouraged the community to study rank metric cryptosystems: "NIST believes rank-based cryptography should continue to be researched" [16]. Rank-metric based cryptosystems seem to be a good alternative to cryptosystems in Hamming metric, but were not studied enough at that point regarding side-channel analysis and embedded implementations. Indeed, public-key cryptosystems are commonly used in embedded systems. Thus it is essential to identify potential leakage to improve their resistance against side-channel attacks and ensure their security in practice. Kocher introduced side-channel attacks in 1996 [12]. An attacker can use information provided by a side-channel to extract secret data from a device executing a cryptographic primitive. The information leakage is exploited without having to tamper with the device. The first side-channel attack against a code-based cryptosystem was proposed in 2008 [20] and targeted McEliece cryptosystem in rank metric. It was then followed by numerous others in more than a decade of research, with timing or power consumption attacks. More recently, there were two papers combining physical attacks with algebraic properties [8, 13]. We do not detail more those attacks since they are out of scope.

## Related work.

Two recent papers related to side-channel attacks on code-based cryptography in rank metric have been published [4, 18]. Both exploit timing leakage from the decoding failure rate of LRPC codes [9]. In this work, we focus on constant-time implementations of schemes using LRPC codes. We target two constant-time implementations of ROLLO, and in particular the Gaussian elimination function. The first one is provided by the authors of ROLLO's proposal to
## 2 Side-Channel Attack on ROLLO PQC scheme

**Keywords:** Side-Channel Attack, Power Consumption Analysis, ROLLO, Key-Recovery Attack, Rank Metric, LRPC Codes

# 1 Introduction

Nowadays number theory based cryptography, like RSA [17] or ECDSA [11], is efficient but weak against the Shor's quantum algorithm [19]. The existence of quantum algorithms pushed the National Institute of Standards and Technology (NIST) to anticipate the time when an efficient quantum computer will be able to execute these algorithms and break commonly used public-key cryptography. In late 2016, NIST started the Post-Quantum Cryptography (PQC) standardization process to get signatures and, key encapsulation mechanisms (KEM) or public-key encryption schemes (PKE), resisting to both classical and quantum attacks. Among the historical schemes, as McEliece [14] or NTRU [10], there are recent proposals based on rank metric. Error-correcting codes in rank metric allow to reduce some drawbacks of Hamming metric, like the key-sizes. In the second round of this standardization process, there were two proposals in rank metric, namely ROLLO [1] and RQC [15]. Both were not selected for the third round due to some algebraic attacks [5, 6]. Nonetheless, NIST encouraged the community to study rank metric cryptosystems: "NIST believes rank-based cryptography should continue to be researched" [16]. Rank-metric based cryptosystems seem to be a good alternative to cryptosystems in Hamming metric, but were not studied enough at that point regarding side-channel analysis and embedded implementations.

Indeed, public-key cryptosystems are commonly used in embedded systems. Thus it is essential to identify potential leakage to improve their resistance against side-channel attacks and ensure their security in practice. Kocher introduced side-channel attacks in 1996 [12]. An attacker can use information provided by a side-channel to extract secret data from a device executing a cryptographic primitive. The information leakage is exploited without having to tamper with the device. The first side-channel attack against a code-based cryptosystem was proposed in 2008 [20] and targeted McEliece cryptosystem in rank metric. It was then followed by numerous others in more than a decade of research, with timing or power consumption attacks. More recently, there were two papers combining physical attacks with algebraic properties [8, 13]. We do not detail more those attacks since they are out of scope.

## Related work.

Two recent papers related to side-channel attacks on code-based cryptography in rank metric have been published [4, 18]. Both exploit timing leakage from the decoding failure rate of LRPC codes [9]. In this work, we focus on constant-time implementations of schemes using LRPC codes. We target two constant-time implementations of ROLLO, and in particular the Gaussian elimination function. The first one is provided by the authors of ROLLO's proposal to
NIST [1]. The second one only provides an implementation of ROLLO-I for
128 bits of security [2].

***Our contribution.***

To the best of our knowledge, this is the first single trace attack against dif-
ferent versions of the constant-time Gaussian elimination for error-correcting
codes in rank metric. We show that the power consumption during the decapsu-
lation/decryption process can provide enough information to make an efficient
attack on ROLLO schemes. Our attack allows us to recover various secret data
such as:

* the private key in both cryptosystems via the syndrome recovery,

* the shared secret in ROLLO-I key encapsulation mechanism, or the encrypted message in ROLLO-II public-key encryption.

We finally present two countermeasures to make the implementations resistant to the proposed attack. Gaussian elimination is often used in coding theory to go from a dense parity-check matrix to a parity-check matrix in systematic form. With this work we want to point out that even recent implementations of this operation could be vulnerable to side-channel attacks. For instance, Gaussian elimination in constant-time is also used in Classic McEliece. Nonetheless the implementation differs from the one in ROLLO, and we have not investigated the leakage detection on Classic McEliece yet. But in case we are able to detect differences in power consumption for some values as presented in this paper, we could also apply our attack on this scheme to recover the parity-check matrix.

***Organization of the paper.***

In Section 2, we recall elementary notions of error-correcting codes in rank metric as well as ROLLO schemes. In Section 3, we detail attacks on both implementations: the reference one using *rbc_library* and the proposal on *GitHub*. We also provide some experimental results for ROLLO-I-128. We discuss two different countermeasures in Section 4. Finally, we conclude this paper in Section 5.

## 2 Background

ROLLO's submission is based on ideal Low-Rank Parity-Check (LRPC) codes.
The latter were introduced in 2013 [9]. In this section, we first give some
details on ideal LRPC codes, then recall the ROLLO proposal to NIST PQC
standardization process.

### 2.1 Rank metric codes

In the following sections, we denote by $q$ a power of a prime number, and let $m, n$, and, $k$ be positive integers such that $n > k$.

We also consider the isomorphism between the vector space $\mathbb{F}_{q^m}^n$ and the
NIST [1]. The second one only provides an implementation of ROLLO-I for
128 bits of security [2].

***Our contribution.***

To the best of our knowledge, this is the first single trace attack against dif-
ferent versions of the constant-time Gaussian elimination for error-correcting
codes in rank metric. We show that the power consumption during the decapsu-
lation/decryption process can provide enough information to make an efficient
attack on ROLLO schemes. Our attack allows us to recover various secret data
such as:

* the private key in both cryptosystems via the syndrome recovery,

* the shared secret in ROLLO-I key encapsulation mechanism, or the encrypted message in ROLLO-II public-key encryption.

We finally present two countermeasures to make the implementations resistant to the proposed attack. Gaussian elimination is often used in coding theory to go from a dense parity-check matrix to a parity-check matrix in systematic form. With this work we want to point out that even recent implementations of this operation could be vulnerable to side-channel attacks. For instance, Gaussian elimination in constant-time is also used in Classic McEliece. Nonetheless the implementation differs from the one in ROLLO, and we have not investigated the leakage detection on Classic McEliece yet. But in case we are able to detect differences in power consumption for some values as presented in this paper, we could also apply our attack on this scheme to recover the parity-check matrix.

***Organization of the paper.***

In Section 2, we recall elementary notions of error-correcting codes in rank metric as well as ROLLO schemes. In Section 3, we detail attacks on both implementations: the reference one using *rbc_library* and the proposal on *GitHub*. We also provide some experimental results for ROLLO-I-128. We discuss two different countermeasures in Section 4. Finally, we conclude this paper in Section 5.

## 2 Background

ROLLO's submission is based on ideal Low-Rank Parity-Check (LRPC) codes.
The latter were introduced in 2013 [9]. In this section, we first give some
details on ideal LRPC codes, then recall the ROLLO proposal to NIST PQC
standardization process.

### 2.1 Rank metric codes

In the following sections, we denote by $q$ a power of a prime number, and let $m, n$, and, $k$ be positive integers such that $n > k$.

We also consider the isomorphism between the vector space $\mathbb{F}_{q^m}^n$ and the
4 Side-Channel Attack on ROLLO PQC scheme

extension field $\mathbb{F}_{q^m}[Z]/(P_n)$ given by

$$ \phi : \mathbb{F}_{q^m}^n \rightarrow \mathbb{F}_{q^m}[Z]/(P_n) \\ (x_1, \dots, x_n) \mapsto \sum_{i=1}^n x_i Z^i $$

with $P_n$ an irreducible polynomial of degree $n$ and $(P_n)$ the ideal of $\mathbb{F}_{q^m}[Z]$ generated by $P_n$. Note that the vector space $\mathbb{F}_{q^m}$ is isomorphic to $\mathbb{F}_q[Z]/(P_m)$, with $P_m$ an irreducible polynomial of degree $m$ over $\mathbb{F}_q$.

A linear code $\mathcal{C}$ over $\mathbb{F}_{q^m}$ of length $n$ and dimension $k$ is a subspace of $\mathbb{F}_{q^m}^n$. It is denoted by $[n, k]_{q^m}$, and can be represented by a parity-check matrix $\mathbf{H} \in \mathbb{F}_{q^m}^{(n-k) \times n}$ such that

$$ \mathcal{C} = \{ \mathbf{x} \in \mathbb{F}_{q^m}^n, \mathbf{H} \cdot \mathbf{x}^T = 0 \}. $$

An element $\mathbf{x} = (x_1, \dots, x_n) \in \mathcal{C}$ is called a codeword. Since $\mathbf{x} \in \mathbb{F}_{q^m}^n$, each of its coordinate $x_i$, for $1 \le i \le n$, can be associated to a vector $(x_{i,1}, \dots, x_{i,m})$. Thus an element $\mathbf{x} \in \mathbb{F}_{q^m}^n$ can also be represented by a matrix as follows:

$$ M(\mathbf{x}) = (x_{i,j})_{\substack{1 \le i \le n \\ 1 \le j \le m}} \in \mathbb{F}_q^{n \times m}. $$

For an element $\mathbf{x} \in \mathbb{F}_{q^m}^n$, the syndrome of $\mathbf{x}$ is defined as the vector $\mathbf{s} = \mathbf{H} \cdot \mathbf{x}^T$. Considering the rank metric, the distance between two vectors $\mathbf{x}$ and $\mathbf{y}$ in $\mathbb{F}_{q^m}^n$ is defined by

$$ d(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\| = \|\mathbf{v}\| = \mathrm{rank}(M(\mathbf{v})) $$

with $\mathbf{v} = \mathbf{x} - \mathbf{y}$.

The support of a vector $\mathbf{x} = (x_1, \dots, x_n) \in \mathbb{F}_{q^m}^n$ is defined as the subset of $\mathbb{F}_{q^m}$ spanned over $\mathbb{F}_q$. Namely, the support of $\mathbf{x}$ is given by

$$ \mathrm{Supp}(\mathbf{x}) = \langle x_1, \dots, x_n \rangle_{\mathbb{F}_q}. $$

W.l.o.g., the support of $(\mathbf{x}, \mathbf{y})$ is $\mathrm{Supp}(\mathbf{x}, \mathbf{y}) = \langle x_1, \dots, x_n, y_1, \dots, y_n \rangle_{\mathbb{F}_q}$. The ideal LRPC codes base their structure on ideal codes.

Given a polynomial $P_n \in \mathbb{F}_q[Z]$ of degree $n$ and a vector $\mathbf{v} \in \mathbb{F}_{q^m}^n$, an ideal matrix generated by $\mathbf{v}$ is a $n \times n$ matrix defined by

$$ \mathcal{IM}(\mathbf{v}) = \begin{pmatrix} \mathbf{v}(Z) & \mod P_n \\ Z \cdot \mathbf{v}(Z) & \mod P_n \\ \vdots & \\ Z^{n-1} \cdot \mathbf{v}(Z) & \mod P_n \end{pmatrix}. $$
4 Side-Channel Attack on ROLLO PQC scheme

extension field $\mathbb{F}_{q^m}[Z]/(P_n)$ given by

$$ \phi : \mathbb{F}_{q^m}^n \rightarrow \mathbb{F}_{q^m}[Z]/(P_n) \\ (x_1, \dots, x_n) \mapsto \sum_{i=1}^n x_i Z^i $$

with $P_n$ an irreducible polynomial of degree $n$ and $(P_n)$ the ideal of $\mathbb{F}_{q^m}[Z]$ generated by $P_n$. Note that the vector space $\mathbb{F}_{q^m}$ is isomorphic to $\mathbb{F}_q[Z]/(P_m)$, with $P_m$ an irreducible polynomial of degree $m$ over $\mathbb{F}_q$.

A linear code $\mathcal{C}$ over $\mathbb{F}_{q^m}$ of length $n$ and dimension $k$ is a subspace of $\mathbb{F}_{q^m}^n$. It is denoted by $[n, k]_{q^m}$, and can be represented by a parity-check matrix $\mathbf{H} \in \mathbb{F}_{q^m}^{(n-k) \times n}$ such that

$$ \mathcal{C} = \{ \mathbf{x} \in \mathbb{F}_{q^m}^n, \mathbf{H} \cdot \mathbf{x}^T = 0 \}. $$

An element $\mathbf{x} = (x_1, \dots, x_n) \in \mathcal{C}$ is called a codeword. Since $\mathbf{x} \in \mathbb{F}_{q^m}^n$, each of its coordinate $x_i$, for $1 \le i \le n$, can be associated to a vector $(x_{i,1}, \dots, x_{i,m})$. Thus an element $\mathbf{x} \in \mathbb{F}_{q^m}^n$ can also be represented by a matrix as follows:

$$ M(\mathbf{x}) = (x_{i,j})_{\substack{1 \le i \le n \\ 1 \le j \le m}} \in \mathbb{F}_q^{n \times m}. $$

For an element $\mathbf{x} \in \mathbb{F}_{q^m}^n$, the syndrome of $\mathbf{x}$ is defined as the vector $\mathbf{s} = \mathbf{H} \cdot \mathbf{x}^T$. Considering the rank metric, the distance between two vectors $\mathbf{x}$ and $\mathbf{y}$ in $\mathbb{F}_{q^m}^n$ is defined by

$$ d(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\| = \|\mathbf{v}\| = \mathrm{rank}(M(\mathbf{v})) $$

with $\mathbf{v} = \mathbf{x} - \mathbf{y}$.

The support of a vector $\mathbf{x} = (x_1, \dots, x_n) \in \mathbb{F}_{q^m}^n$ is defined as the subset of $\mathbb{F}_{q^m}$ spanned over $\mathbb{F}_q$. Namely, the support of $\mathbf{x}$ is given by

$$ \mathrm{Supp}(\mathbf{x}) = \langle x_1, \dots, x_n \rangle_{\mathbb{F}_q}. $$

W.l.o.g., the support of $(\mathbf{x}, \mathbf{y})$ is $\mathrm{Supp}(\mathbf{x}, \mathbf{y}) = \langle x_1, \dots, x_n, y_1, \dots, y_n \rangle_{\mathbb{F}_q}$. The ideal LRPC codes base their structure on ideal codes.

Given a polynomial $P_n \in \mathbb{F}_q[Z]$ of degree $n$ and a vector $\mathbf{v} \in \mathbb{F}_{q^m}^n$, an ideal matrix generated by $\mathbf{v}$ is a $n \times n$ matrix defined by

$$ \mathcal{IM}(\mathbf{v}) = \begin{pmatrix} \mathbf{v}(Z) & \mod P_n \\ Z \cdot \mathbf{v}(Z) & \mod P_n \\ \vdots & \\ Z^{n-1} \cdot \mathbf{v}(Z) & \mod P_n \end{pmatrix}. $$
An $[ns, nt]_{q^m}$-code $\mathcal{C}$, generated by the vectors $(\mathbf{g}_{i,j})_{i \in [1, \dots, s-t]} \in \mathbb{F}_{q^m}^n$, is an ideal code if a generator matrix in systematic form is of the form

$$ \mathbf{G} = \begin{pmatrix} \mathcal{IM}(\mathbf{g}_{1,1}) & \cdots & \mathcal{IM}(\mathbf{g}_{1,s-t}) \\ \mathbf{I}_{nt} & \vdots & \vdots \\ \mathcal{IM}(\mathbf{g}_{t,1}) & \cdots & \mathcal{IM}(\mathbf{g}_{t,s-t}) \end{pmatrix}. $$

In [1], the authors restrain the definition of ideal LRPC (Low-Rank Parity Check) codes to (2, 1)-ideal LRPC codes that they used for all variants of ROLLO.

Let $F$ be a $\mathbb{F}_q$-subspace of $\mathbb{F}_{q^m}$ such that $dim(F) = d$. Let $(\mathbf{h}_1, \mathbf{h}_2)$ be a pair of two vectors in $\mathbb{F}_{q^m}^n$, such that Supp$(\mathbf{h}_1, \mathbf{h}_2) = F$, and $P_n \in \mathbb{F}_q[Z]$ be a polynomial of degree $n$. A $[2n, n]_{q^m}$-code $\mathcal{C}$ is an ideal LRPC code if it has a parity-check matrix of the form

$$ \mathbf{H} = \begin{pmatrix} \mathcal{IM}(\mathbf{h}_1)^T & \mathcal{IM}(\mathbf{h}_2)^T \end{pmatrix}. $$

## 2.2 ROLLO

ROLLO is a second round submission to the post-quantum standardization process launched by NIST in 2016. Since the last update in April 2020, it is composed of two cryptosystems: ROLLO-I, a Key-Encapsulation Mechanism (KEM), and ROLLO-II, a Public-Key Encryption (PKE). Both are described in Figure 1. We use the following notations:

* $A \stackrel{\$}{\leftarrow} \mathbb{F}_{q^m}^k$ denotes the operation of selecting randomly $k$ vectors from the vector space $\mathbb{F}_{q^m}$, then $A \in \mathbb{F}_{q^m}^k$.

* $(\mathbf{u}, \mathbf{v}) \stackrel{\$}{\leftarrow}_l A$ denotes the operation of selecting randomly $2n$ linear combinations from the element $A$, then $\mathbf{u}, \mathbf{v} \in \mathbb{F}_{q^m}^n$ and $\text{Supp}(\mathbf{u}, \mathbf{v}) = A$.

* RSR denotes the Rank Support Recovery algorithm given in the specification of ROLLO [1] to decode LRPC codes.

We unify tables of parameters from ROLLO's specification into Table 1. For the three security levels, $q = 2$. The name of each variant gives the targeted classical security level, e.g. ROLLO-I-128 is a classical 128-bit security level. The parameters $d$ and $r$ correspond respectively to the rank of the private key and the rank of the errors. The parameters $n$ and $m$ can respectively be obtained with the degrees of $P_n$ and $P_m$.
An $[ns, nt]_{q^m}$-code $\mathcal{C}$, generated by the vectors $(\mathbf{g}_{i,j})_{i \in [1, \dots, s-t]} \in \mathbb{F}_{q^m}^n$, is an ideal code if a generator matrix in systematic form is of the form

$$ \mathbf{G} = \begin{pmatrix} \mathcal{IM}(\mathbf{g}_{1,1}) & \cdots & \mathcal{IM}(\mathbf{g}_{1,s-t}) \\ \mathbf{I}_{nt} & \vdots & \vdots \\ \mathcal{IM}(\mathbf{g}_{t,1}) & \cdots & \mathcal{IM}(\mathbf{g}_{t,s-t}) \end{pmatrix}. $$

In [1], the authors restrain the definition of ideal LRPC (Low-Rank Parity Check) codes to (2,1)-ideal LRPC codes that they used for all variants of ROLLO.

Let $F$ be a $\mathbb{F}_q$-subspace of $\mathbb{F}_{q^m}$ such that $dim(F) = d$. Let $(\mathbf{h}_1, \mathbf{h}_2)$ be a pair of two vectors in $\mathbb{F}_{q^m}^n$, such that $Supp(\mathbf{h}_1, \mathbf{h}_2) = F$, and $P_n \in \mathbb{F}_q[Z]$ be a polynomial of degree $n$. A $[2n, n]_{q^m}$-code $\mathcal{C}$ is an ideal LRPC code if it has a parity-check matrix of the form

$$ \mathbf{H} = \begin{pmatrix} \mathcal{IM}(\mathbf{h}_1)^T & \mathcal{IM}(\mathbf{h}_2)^T \end{pmatrix}. $$

## 2.2 ROLLO

ROLLO is a second round submission to the post-quantum standardization process launched by NIST in 2016. Since the last update in April 2020, it is composed of two cryptosystems: ROLLO-I, a Key-Encapsulation Mechanism (KEM), and ROLLO-II, a Public-Key Encryption (PKE). Both are described in Figure 1. We use the following notations:

* $A \stackrel{\$}{\leftarrow} \mathbb{F}_{q^m}^k$ denotes the operation of selecting randomly $k$ vectors from the vector space $\mathbb{F}_{q^m}$, then $A \in \mathbb{F}_{q^m}^k$.

* $(\mathbf{u}, \mathbf{v}) \stackrel{\$}{\leftarrow}_l A$ denotes the operation of selecting randomly $2n$ linear combinations from the element $A$, then $\mathbf{u}, \mathbf{v} \in \mathbb{F}_{q^m}^n$ and $Supp(\mathbf{u}, \mathbf{v}) = A$.

* RSR denotes the Rank Support Recovery algorithm given in the specification of ROLLO [1] to decode LRPC codes.

We unify tables of parameters from ROLLO's specification into Table 1. For the three security levels, $q = 2$. The name of each variant gives the targeted classical security level, e.g. ROLLO-I-128 is a classical 128-bit security level. The parameters $d$ and $r$ correspond respectively to the rank of the private key and the rank of the errors. The parameters $n$ and $m$ can respectively be obtained with the degrees of $P_n$ and $P_m$.
## Side-Channel Attack on ROLLO PQC scheme

<table><caption>**Table 1:** ROLLO's parameters for each security level</caption><thead><tr><th>Instance</th><th>d</th><th>r</th><th>P<sub>n</sub></th><th>P<sub>m</sub></th></tr></thead><tbody><tr><td>ROLLO-I-128</td><td>8</td><td>7</td><td>Z<sup>83</sup> + Z<sup>7</sup> + Z<sup>4</sup> + Z<sup>2</sup> + 1</td><td>z<sup>67</sup> + z<sup>5</sup> + z<sup>2</sup> + z + 1</td></tr><tr><td>ROLLO-I-192</td><td>8</td><td>8</td><td>Z<sup>97</sup> + Z<sup>6</sup> + 1</td><td>z<sup>97</sup> + z<sup>9</sup> + 1</td></tr><tr><td>ROLLO-I-256</td><td>9</td><td>9</td><td>Z<sup>113</sup> + Z<sup>9</sup> + 1</td><td>z<sup>97</sup> + z<sup>6</sup> + 1</td></tr><tr><td>ROLLO-II-128</td><td>8</td><td>7</td><td>Z<sup>189</sup> + Z<sup>6</sup> + Z<sup>5</sup> + Z<sup>2</sup> + 1</td><td>z<sup>83</sup> + z<sup>7</sup> + z<sup>4</sup> + z<sup>2</sup> + 1</td></tr><tr><td>ROLLO-II-192</td><td>8</td><td>8</td><td>Z<sup>193</sup> + Z<sup>15</sup> + 1</td><td>z<sup>97</sup> + z<sup>6</sup> + 1</td></tr><tr><td>ROLLO-II-256</td><td>9</td><td>8</td><td>Z<sup>211</sup> + Z<sup>11</sup> + Z<sup>20</sup> + Z<sup>8</sup> + 1</td><td>z<sup>97</sup> + z<sup>6</sup> + 1</td></tr></tbody></table>

<figure><img src="image_2.png" /><figcaption>**Fig. 1:** ROLLO-I (KEM) and ROLLO-II (PKE) cryptosystems</figcaption></figure>

In the following, we will focus on the vulnerabilities of the implementations of Gaussian elimination process. The latter is used several times in ROLLO cryptosystems, namely to compute:

* the support $S$ of the syndrome $s$

* the support of the error $(e_1, e_2)$ letting us recover the shared secret in the case of ROLLO-I or encrypt/decrypt a message in the case of ROLLO-II;

* the intersections of two vector spaces during the decoding of the syndrome (RSR). These intersections determine the support $E$ of the error:

$$E \leftarrow \bigcap_{1 \le i \le d} f_i^{-1} \cdot S,$$
## Side-Channel Attack on ROLLO PQC scheme

<table><caption>**Table 1:** ROLLO's parameters for each security level</caption><thead><tr><th>Instance</th><th>d</th><th>r</th><th>P<sub>n</sub></th><th>P<sub>m</sub></th></tr></thead><tbody><tr><td>ROLLO-I-128</td><td>8</td><td>7</td><td>Z<sup>83</sup> + Z<sup>7</sup> + Z<sup>4</sup> + Z<sup>2</sup> + 1</td><td>z<sup>67</sup> + z<sup>5</sup> + z<sup>2</sup> + z + 1</td></tr><tr><td>ROLLO-I-192</td><td>8</td><td>8</td><td>Z<sup>97</sup> + Z<sup>6</sup> + 1</td><td>z<sup>9</sup> + z<sup>9</sup> + 1</td></tr><tr><td>ROLLO-I-256</td><td>9</td><td>9</td><td>Z<sup>113</sup> + Z<sup>9</sup> + 1</td><td>z<sup>97</sup> + z<sup>6</sup> + 1</td></tr><tr><td>ROLLO-II-128</td><td>8</td><td>7</td><td>Z<sup>189</sup> + Z<sup>6</sup> + Z<sup>5</sup> + Z<sup>2</sup> + 1</td><td>z<sup>83</sup> + z<sup>7</sup> + z<sup>4</sup> + z<sup>2</sup> + 1</td></tr><tr><td>ROLLO-II-192</td><td>8</td><td>8</td><td>Z<sup>193</sup> + Z<sup>15</sup> + 1</td><td>z<sup>97</sup> + z<sup>6</sup> + 1</td></tr><tr><td>ROLLO-II-256</td><td>9</td><td>8</td><td>Z<sup>211</sup> + Z<sup>11</sup> + Z<sup>20</sup> + Z<sup>8</sup> + 1</td><td>z<sup>97</sup> + z<sup>6</sup> + 1</td></tr></tbody></table>

<figure><img src="image_2.png" /><figcaption>**Fig. 1:** ROLLO-I (KEM) and ROLLO-II (PKE) cryptosystems</figcaption></figure>

In the following, we will focus on the vulnerabilities of the implementations of Gaussian elimination process. The latter is used several times in ROLLO cryptosystems, namely to compute:

* the support $S$ of the syndrome $s$

* the support of the error $(e_1, e_2)$ letting us recover the shared secret in the case of ROLLO-I or encrypt/decrypt a message in the case of ROLLO-II;

* the intersections of two vector spaces during the decoding of the syndrome (RSR). These intersections determine the support $E$ of the error:

$$E \leftarrow \bigcap_{1 \le i \le d} f_i^{-1} \cdot S,$$
with $F = \langle f_1, \dots, f_d \rangle$ the support of the private key.

Thus, the leakage coming from implementations of Gaussian elimination can allow a side-channel attacker to recover all the secret data. In the next section, we explain the attack on the syndrome. This analysis can be performed to recover the other mentioned data.

## 3 Side-channel attack on Gaussian elimination in constant-time

In the RSR algorithm [1], we first compute the support of the syndrome. For that, the Gaussian elimination is applied to the syndrome matrix $S = M(s) \in \mathcal{M}_{n,m}(\mathbb{F}_2)$ to calculate its support. We know that the syndrome is first computed as:

$$s(Z) = x(Z) \cdot c(Z) \mod P_n,$$

with $x, c, s \in \mathbb{F}_{q^m}[Z]/(P_n)$. Therefore, with the knowledge of the syndrome $s$ and the ciphertext $c$, we can compute $x$, a part of the private key as:

$$x(Z) = s(Z) \times c(Z)^{-1} \mod P_n.$$

Knowing $x$ can lead to a full recovery of the private key. First, we can get the second part of the private key $y$ by computing

$$y(Z) = pk(Z) \times x(Z) \mod P_n.$$

Then, the support of $y$ and $x$ gives the last part of the private key $F$.

The Gaussian elimination in constant-time requires to process each row in each column of the syndrome matrix. Thus, an attacker could be able to recover all values in this matrix. In case of a non constant-time Gaussian elimination, it is possible to treat only the rows under the pivot row. Therefore, the values in all rows above the pivot row remain unknown to the attacker. Consequently, constant-time provides an advantage to a side-channel attacker.

Secondly, the constant-time eases the detection of a pattern corresponding to the targeted operation inside the power trace. Once the attacker found the exact location of this pattern, it becomes straightforward to find the locations for each other iteration.

We analyzed two constant-time implementations of Gaussian elimination and discovered two possible leakages through power consumption. The first one has been provided as *Additionnal Implementations* in April 2020 for the second round of NIST PQC standardization process, and is available on the ROLLO candidate webpage [1]. We refer to it as the reference implementation. It uses the *rbc_library* [3], which provides different functions to implement schemes
with $F = \langle f_1, \dots, f_d \rangle$ the support of the private key.

Thus, the leakage coming from implementations of Gaussian elimination can allow a side-channel attacker to recover all the secret data. In the next section, we explain the attack on the syndrome. This analysis can be performed to recover the other mentioned data.

## 3 Side-channel attack on Gaussian elimination in constant-time

In the RSR algorithm [1], we first compute the support of the syndrome. For that, the Gaussian elimination is applied to the syndrome matrix $S = M(s) \in \mathcal{M}_{n,m}(\mathbb{F}_2)$ to calculate its support. We know that the syndrome is first computed as:

$$s(Z) = x(Z) \cdot c(Z) \mod P_n,$$

with $x, c, s \in \mathbb{F}_{q^m}[Z]/(P_n)$. Therefore, with the knowledge of the syndrome $s$ and the ciphertext $c$, we can compute $x$, a part of the private key as:

$$x(Z) = s(Z) \times c(Z)^{-1} \mod P_n.$$

Knowing $x$ can lead to a full recovery of the private key. First, we can get the second part of the private key $y$ by computing

$$y(Z) = pk(Z) \times x(Z) \mod P_n.$$

Then, the support of $y$ and $x$ gives the last part of the private key $F$.

The Gaussian elimination in constant-time requires to process each row in each column of the syndrome matrix. Thus, an attacker could be able to recover all values in this matrix. In case of a non constant-time Gaussian elimination, it is possible to treat only the rows under the pivot row. Therefore, the values in all rows above the pivot row remain unknown to the attacker. Consequently, constant-time provides an advantage to a side-channel attacker.

Secondly, the constant-time eases the detection of a pattern corresponding to the targeted operation inside the power trace. Once the attacker found the exact location of this pattern, it becomes straightforward to find the locations for each other iteration.

We analyzed two constant-time implementations of Gaussian elimination and discovered two possible leakages through power consumption. The first one has been provided as *Additionnal Implementations* in April 2020 for the second round of NIST PQC standardization process, and is available on the ROLLO candidate webpage [1]. We refer to it as the reference implementation. It uses the *rbc_library* [3], which provides different functions to implement schemes
using rank metric codes. The second implementation has been published on GitHub [2]. We refer to it as the GitHub implementation.

## Notations.

We denote by $\otimes$ the multiplication between a scalar and a row of a matrix and by $\oplus$ the bitwise XOR between two bits or two rows of a matrix. The bitwise AND is represented by $\land$ and the bitwise NOT by $\neg$. The term *mask* does not refer to a boolean masking but to a variable giving the additions on rows according to values obtained from coefficients of the processed column.

## 3.1 Information leakage of the reference implementation

The reference implementation is based on Algorithm 1, which was first introduced in [7].

<caption>**Algorithm 1** Gaussian elimination in constant time</caption>

Require: $S \in \mathcal{M}_{n,m}(\mathbb{F}_2)$
Ensure: $S \in \mathcal{M}_{n,m}(\mathbb{F}_2)$ in systematic form and $\text{rank} = \min(\text{dimension}, n)$
1: $\text{dimension} = 0$
2: **for** $j = 0, \dots, m-1$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;`pivot_row` = $\min(\text{dimension}, n-1)$
4: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 0, \dots, n-1$ **do**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`mask` = $s_{\text{pivot_row},j} \oplus s_{i,j}$
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`tmp` = `mask` $\otimes$ $s_i$
7: &nbsp;&nbsp;&nbsp;&nbsp;**if** $i > \text{pivot_row}$ **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`s_{\text{pivot_row}}` = $s_{\text{pivot_row}} \oplus \text{tmp}$
9: &nbsp;&nbsp;&nbsp;&nbsp;**else**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`dummy` = $s_{\text{pivot_row}} \oplus \text{tmp}$
11: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
12: **end for**
13: **for** $i = 0, \dots, n-1$ **do**
14: &nbsp;&nbsp;&nbsp;&nbsp;**if** $i \neq j$ **then**
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`mask` = $s_{i,j}$
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`tmp` = `mask` $\otimes$ `s_{\text{pivot_row}}$
17: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\text{dimension} < n$ **then**
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`s_i` = $s_i \oplus \text{tmp}$
19: &nbsp;&nbsp;&nbsp;&nbsp;**else**
20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`dummy` = $s_i \oplus \text{tmp}$
21: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
22: **end if**
23: **end for**
24: **end for**
25: $\text{dimension} = \text{dimension} + s_{\text{pivot_row},i}$
using rank metric codes. The second implementation has been published on GitHub [2]. We refer to it as the GitHub implementation.

### Notations.

We denote by $\otimes$ the multiplication between a scalar and a row of a matrix and by $\oplus$ the bitwise XOR between two bits or two rows of a matrix. The bitwise AND is represented by $\land$ and the bitwise NOT by $\neg$. The term *mask* does not refer to a boolean masking but to a variable giving the additions on rows according to values obtained from coefficients of the processed column.

## 3.1 Information leakage of the reference implementation

The reference implementation is based on Algorithm 1, which was first introduced in [7].

**Algorithm 1** Gaussian elimination in constant time

**Require:** $S \in \mathcal{M}_{n,m}(\mathbb{F}_2)$

**Ensure:** $S \in \mathcal{M}_{n,m}(\mathbb{F}_2)$ in systematic form and $\text{rank} = \min(\text{dimension}, n)$

1: $\text{dimension} = 0$

2: **for** $j = 0, \dots, m-1$ **do**

3: &nbsp;&nbsp;&nbsp;&nbsp;`pivot_row` = $\min(\text{dimension}, n-1)$

4: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 0, \dots, n-1$ **do**

5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`mask` = $s_{\text{pivot_row},j} \oplus s_{i,j}$

6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`tmp` = `mask` $\otimes$ $s_i$

7: &nbsp;&nbsp;&nbsp;&nbsp;**if** $i > \text{pivot_row}$ **then**

8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$s_{\text{pivot_row}} = s_{\text{pivot_row}} \oplus \text{tmp}$

9: &nbsp;&nbsp;&nbsp;&nbsp;**else**

10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`dummy` = $s_{\text{pivot_row}} \oplus \text{tmp}$

11: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

12: &nbsp;&nbsp;&nbsp;&nbsp;**end for**

13: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 0, \dots, n-1$ **do**

14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $i \neq j$ **then**

15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`mask` = $s_{i,j}$

16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`tmp` = `mask` $\otimes$ $s_{\text{pivot_row}}$

17: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\text{dimension} < n$ **then**

18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$s_i = s_i \oplus \text{tmp}$

19: &nbsp;&nbsp;&nbsp;&nbsp;**else**

20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`dummy` = $s_i \oplus \text{tmp}$

21: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

22: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

23: &nbsp;&nbsp;&nbsp;&nbsp;**end for**

24: &nbsp;&nbsp;&nbsp;&nbsp;**end for**

25: $\text{dimension} = \text{dimension} + s_{\text{pivot_row},i}$
The input matrix is composed of $n$ rows and $m$ columns. The algorithm outputs the matrix in systematic form and its rank. The first inner **for** loop (line 4) fixes the ones in the diagonal (corresponding to the pivots) and the second inner **for** loop (line 13) removes the ones in the pivot column. In both inner **for** loops in Algorithm 1, $mask \in \mathbb{F}_2$ is computed and multiplied with specific rows of the syndrome matrix. However, the multiplication of a 32-bit word $(u_0, \dots, u_{31})_2$ with zero or one provides information leakage in the power traces. This allows us to recover all the mask values computed during the process, then, the initial syndrome matrix.

Our attack consists in recovering the syndrome matrix

$$ \mathbf{S} = n \left| \begin{array}{c} \multicolumn{1}{c}{\overbrace{\hspace{2.5cm}}^{m}} \\ \left( \begin{array}{cccc} s_{0,0} & s_{0,1} & \cdots & s_{0,m-1} \\ s_{1,0} & s_{1,1} & \cdots & s_{1,m-1} \\ \vdots & \vdots & \ddots & \vdots \\ s_{n-1,0} & s_{n-1,1} & \cdots & s_{n-1,m-1} \end{array} \right), \end{array} \right| \quad (1) $$

where $s_{i,j} \in \mathbb{F}_2$ for $(i,j) \in [0, n-1] \times [0, m-1]$. We denote by $\mathbf{S}_j$ the matrix obtained after the treatment of the $j$-th column of $\mathbf{S}$ and, by $\mathbf{S}[k]$ the $k$-th column of the matrix $\mathbf{S}$. The recovered mask values from the two inner **for** loops lead to a system of linear equations. This system is obtained from two steps described below.

After the first inner **for** loop in Algorithm 1: we recover the mask values $s_{\text{pivot row},j} \oplus s_{i,j}$. If mask = 0, then the pivot row is unchanged. Otherwise, the $i$-th row is added to the pivot row. Then, the first loop provides the indices of rows XORed to the pivot row. We define

$$ \sigma_j = (\sigma_{0,j}, \sigma_{1,j}, \dots, \sigma_{n-1,j}), \quad \text{where } \sigma_{i,j} = \begin{cases} 0 & \text{if } mask = 0 \\ 1 & \text{if } mask = 1 \end{cases}, $$

the vector containing all mask values recovered after the $j$-th iteration. We also define the matrix

$$ \mathbf{J}_k = \left( \begin{array}{c|c} \begin{array}{cccc} 1 & \cdots & 0 & \cdots & 0 \\ \vdots & \ddots & \vdots & & \vdots \\ \sigma_{0,k} & \cdots & 1 & \cdots & \sigma_{n-1,k} \\ \vdots & & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & \cdots & 1 \end{array} & \leftarrow \text{k-th row,} \\ \uparrow & \\ \text{k-th column} \end{array} \right) $$
The input matrix is composed of $n$ rows and $m$ columns. The algorithm outputs the matrix in systematic form and its rank. The first inner **for** loop (line 4) fixes the ones in the diagonal (corresponding to the pivots) and the second inner **for** loop (line 13) removes the ones in the pivot column. In both inner **for** loops in Algorithm 1, $mask \in \mathbb{F}_2$ is computed and multiplied with specific rows of the syndrome matrix. However, the multiplication of a 32-bit word $(u_0, \dots, u_{31})_2$ with zero or one provides information leakage in the power traces. This allows us to recover all the mask values computed during the process, then, the initial syndrome matrix.

Our attack consists in recovering the syndrome matrix

$$ \mathbf{S} = n \left| \begin{array}{c} \frac{m}{\downarrow} \\ \left( \begin{array}{cccc} s_{0,0} & s_{0,1} & \cdots & s_{0,m-1} \\ s_{1,0} & s_{1,1} & \cdots & s_{1,m-1} \\ \vdots & \vdots & \ddots & \vdots \\ s_{n-1,0} & s_{n-1,1} & \cdots & s_{n-1,m-1} \end{array} \right), \end{array} \right. \quad (1) $$

where $s_{i,j} \in \mathbb{F}_2$ for $(i,j) \in [0, n-1] \times [0, m-1]$. We denote by $\mathbf{S}_j$ the matrix obtained after the treatment of the $j$-th column of $\mathbf{S}$ and, by $\mathbf{S}[k]$ the $k$-th column of the matrix $\mathbf{S}$. The recovered mask values from the two inner **for** loops lead to a system of linear equations. This system is obtained from two steps described below.

After the first inner **for** loop in Algorithm 1: we recover the mask values $s_{\text{pivot row},j} \oplus s_{i,j}$. If mask = 0, then the pivot row is unchanged. Otherwise, the $i$-th row is added to the pivot row. Then, the first loop provides the indices of rows XORed to the pivot row. We define

$$ \sigma_j = (\sigma_{0,j}, \sigma_{1,j}, \dots, \sigma_{n-1,j}), \quad \text{where } \sigma_{i,j} = \begin{cases} 0 & \text{if } mask = 0 \\ 1 & \text{if } mask = 1 \end{cases}, $$

the vector containing all mask values recovered after the $j$-th iteration. We also define the matrix

$$ \mathbf{J}_k = \left( \begin{array}{c|c} \begin{array}{cccc} 1 & \cdots & 0 & \cdots & 0 \\ \vdots & \ddots & \vdots & & \vdots \\ \sigma_{0,k} & \cdots & 1 & \cdots & \sigma_{n-1,k} \\ \vdots & & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & \cdots & 1 \end{array} & \leftarrow \text{k-th row,} \\ \uparrow & \\ \text{k-th column} \end{array} \right) $$
10 Side-Channel Attack on ROLLO PQC scheme

involved in the computation of the system of linear equations. For instance, considering the pivot row of index 0. After the first inner **for** loop, the syndrome matrix given in Equation 1 is under the form

$$ \left( \begin{array}{ccc} \sum_{i=0}^{n-1} \sigma_{i,0} s_{i,0} & \sum_{i=0}^{n-1} \sigma_{i,0} s_{i,1} & \cdots \\ s_{1,0} & s_{1,1} & \cdots \\ \vdots & \vdots & \ddots \\ s_{n-1,0} & s_{n-1,1} & \cdots \\ \end{array} \begin{array}{c} \sum_{i=0}^{n-1} \sigma_{i,0} s_{i,m-1} \\ s_{1,m-1} \\ \vdots \\ s_{n-1,m-1} \end{array} \right). $$

In other words, we can compute it as

$$ \mathbf{J}_0 \times \mathbf{S} = \left( \frac{\mathbf{1} \mid \sigma_{1,0} \cdots \sigma_{n-1,0}}{\mathbf{0} \mid \mathbf{I}_{n-1}} \right) \times \mathbf{S}, $$

where $\mathbf{I}_{n-1}$ denotes the identity matrix of size $n-1$ and $\mathbf{0}$ a column of $n-1$ zeros.

We notice in lines 7–8 in Algorithm 1 that only rows with index greater than the pivot row index are added to the pivot row. Thus, after the treatment of the column $j$, we define $\sigma_{i,j} = 0$ for $i \le \text{pivot row}$.

After the second inner **for** loop in Algorithm 1: the recovered mask values correspond to the coefficients $s_{i,j}$ of the matrix obtained after the first inner **for** loop. We denote by $\boldsymbol{\sigma}'_j = (\sigma'_{0,j}, \dots, \sigma'_{j-1,j}, \*, \sigma'_{j+1,j}, \dots, \sigma'_{n-1,j})$ the vector composed of mask values. The item $\*$ represents the pivot that is not processed in the second loop. For the attack, $\*$ is replaced by one.

On one hand, during the treatment of the $j$-th column, $\boldsymbol{\sigma}'_j$ completes the system of linear equations. Assuming we want to recover the column 0, we use a linear solver on the system

$$ \mathbf{J}_0 \times \mathbf{S}[0] = (\boldsymbol{\sigma}'_0)^t. $$

On the other hand, the vector $\boldsymbol{\sigma}'_j$ allows us to recover all the operations performed on rows. These operations are taken into account in solving the system of linear equations of the $(j+1)$-th column. For this, we define the matrix

$$ \mathbf{J}'_k = \left( \begin{array}{c|c} 1 & \cdots \sigma'_{0,k} \cdots 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots 1 & \cdots 0 \\ \vdots & \ddots & \ddots \\ 0 & \cdots \sigma'_{n-1,k} & \cdots 1 \end{array} \right) \leftarrow \begin{array}{l} \text{k-th row.} \\ \text{k-th column} \end{array}. $$
10 Side-Channel Attack on ROLLO PQC scheme

involved in the computation of the system of linear equations. For instance, considering the pivot row of index 0. After the first inner **for** loop, the syndrome matrix given in Equation 1 is under the form

$$ \left( \begin{array}{ccc} \sum_{i=0}^{n-1} \sigma_{i,0} s_{i,0} & \sum_{i=0}^{n-1} \sigma_{i,0} s_{i,1} & \cdots \\ s_{1,0} & s_{1,1} & \cdots \\ \vdots & \vdots & \ddots \\ s_{n-1,0} & s_{n-1,1} & \cdots \\ \end{array} \begin{array}{c} \sum_{i=0}^{n-1} \sigma_{i,0} s_{i,m-1} \\ s_{1,m-1} \\ \vdots \\ s_{n-1,m-1} \end{array} \right). $$

In other words, we can compute it as

$$ \mathbf{J}_0 \times \mathbf{S} = \left( \frac{\mathbf{1} | \sigma_{1,0} \cdots \sigma_{n-1,0} |}{\mathbf{0} | \mathbf{I}_{n-1} |} \right) \times \mathbf{S}, $$

where $\mathbf{I}_{n-1}$ denotes the identity matrix of size $n-1$ and $\mathbf{0}$ a column of size $n-1$ zeros.

We notice in lines 7–8 in Algorithm 1 that only rows with index greater than the pivot row index are added to the pivot row. Thus, after the treatment of the column $j$, we define $\sigma_{i,j} = 0$ for $i \le \text{pivot row}$.

After the second inner **for** loop in Algorithm 1: the recovered mask values correspond to the coefficients $s_{i,j}$ of the matrix obtained after the first inner **for** loop. We denote by $\boldsymbol{\sigma}'_j = (\sigma'_{0,j}, \dots, \sigma'_{j-1,j}, \*, \sigma'_{j+1,j}, \dots, \sigma'_{n-1,j})$ the vector composed of mask values. The item $\*$ represents the pivot that is not processed in the second loop. For the attack, $\*$ is replaced by one.

On one hand, during the treatment of the $j$-th column, $\boldsymbol{\sigma}'_j$ completes the system of linear equations. Assuming we want to recover the column 0, we use a linear solver on the system

$$ \mathbf{J}_0 \times \mathbf{S}[0] = (\boldsymbol{\sigma}'_0)^t. $$

On the other hand, the vector $\boldsymbol{\sigma}'_j$ allows us to recover all the operations performed on rows. These operations are taken into account in solving the system of linear equations of the $(j+1)$-th column. For this, we define the matrix

$$ \mathbf{J}'_k = \left( \begin{array}{c|c} 1 & \cdots \sigma'_{0,k} \cdots 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots 1 & \cdots 0 \\ \vdots & \ddots & \ddots \\ 0 & \cdots \sigma'_{n-1,k} & \cdots 1 \end{array} \right) \leftarrow \begin{array}{l} \text{k-th row.} \\ \text{k-th column} \end{array}. $$
For example, for the treatment of column 1 we consider the matrix

$$ \mathbf{S}_0 = \underbrace{\left( \begin{array}{c} (\boldsymbol{\sigma}'_0)^t \\ \vdots \\ \boldsymbol{I}_{n-1} \end{array} \right)}_{=\mathbf{J}'_0} \times \mathbf{J}_0 \times \mathbf{S}. $$

More generally, during the treatment of the column $j$, for $j \ge 1$, we consider

$$ \mathbf{S}_{j-1} = \left( \prod_{k=j-1, \dots, 0} \mathbf{J}'_k \times \mathbf{J}_k \right) \times \mathbf{S}. $$

In case there is no pivot in a column, all the mask values are equal to zero, thus $\mathbf{J}'_k \times \mathbf{J}_k = \mathbf{I}_n$.

Finally, to recover the column $j$, we solve the system of linear equations

$$ \mathbf{J}_{j-1} \times \left( \prod_{k=j-2, \dots, 0} \mathbf{J}'_k \times \mathbf{J}_k \right) \times \mathbf{S}[j-1] = (\boldsymbol{\sigma}'_{j-1})^t. $$

## 3.2 Information leakage of the GitHub implementation

In this section, we denote by $\mathbf{1} = \underbrace{(11 \dots 11)}_{m}$ and $\mathbf{0} = \underbrace{(00 \dots 00)}_{m}$.

In [2], the authors introduced a row reduction in constant-time given in Algorithm 2, that can be seen as a generalization of the one presented in Algorithm 1.

At the end of Algorithm 2, we obtain a matrix under the row echelon form. In order to ensure this, three masks are first computed according to coefficients and pivot processed. Each mask is equal to $\mathbf{1}$ or $\mathbf{0}$. The three masks influence the operations on rows (lines 19-20 in Algorithm 2) as presented in Figure 2. We notice that two paths (in red bold) lead to bitwise XOR on rows. First, when $mask1 = mask2 = mask3 = \mathbf{1}$, the pivot coefficient is fixed to one. This happens at most once per loop over $j$. Then, when $mask2 = mask3 = \mathbf{1}$ independently of $mask1$, the other ones in the processed column $j$ are removed.
For example, for the treatment of column 1 we consider the matrix

$$ \mathbf{S}_0 = \underbrace{\left( \begin{array}{c} (\boldsymbol{\sigma}'_0)^t \\ \vdots \\ \mathbf{I}_{n-1} \end{array} \right)}_{=\mathbf{J}'_0} \times \mathbf{J}_0 \times \mathbf{S}. $$

More generally, during the treatment of the column $j$, for $j \ge 1$, we consider

$$ \mathbf{S}_{j-1} = \left( \prod_{k=j-1,...,0} \mathbf{J}'_k \times \mathbf{J}_k \right) \times \mathbf{S}. $$

In case there is no pivot in a column, all the mask values are equal to zero, thus $\mathbf{J}'_k \times \mathbf{J}_k = \mathbf{I}_n$.

Finally, to recover the column $j$, we solve the system of linear equations

$$ \mathbf{J}_{j-1} \times \left( \prod_{k=j-2,...,0} \mathbf{J}'_k \times \mathbf{J}_k \right) \times \mathbf{S}[j-1] = (\boldsymbol{\sigma}'_{j-1})^t. $$

## 3.2 Information leakage of the GitHub implementation

In this section, we denote by $\mathbf{1} = \underbrace{(11 \dots 11)}_{m}$ and $\mathbf{0} = \underbrace{(00 \dots 00)}_{m}$.

In [2], the authors introduced a row reduction in constant-time given in Algorithm 2, that can be seen as a generalization of the one presented in Algorithm 1.

At the end of Algorithm 2, we obtain a matrix under the row echelon form. In order to ensure this, three masks are first computed according to coefficients and pivot processed. Each mask is equal to $\mathbf{1}$ or $\mathbf{0}$. The three masks influence the operations on rows (lines 19-20 in Algorithm 2) as presented in Figure 2. We notice that two paths (in red bold) lead to bitwise XOR on rows. First, when $mask1 = mask2 = mask3 = \mathbf{1}$, the pivot coefficient is fixed to one. This happens at most once per loop over $j$. Then, when $mask2 = mask3 = \mathbf{1}$ independently of $mask1$, the other ones in the processed column $j$ are removed.
<caption>**Algorithm 2** Row reduction in constant-time</caption>

**Require:** $S \in \mathcal{M}_{n,m}(\mathbb{F}_2)$
**Ensure:** $S \in \mathcal{M}_{n,m}(\mathbb{F}_2)$ in row echelon form and its rank = pivot_row
1: $pivot_row = 0$
2: for $j = 0, \dots, m-1$ do
3: for $i = 0, \dots, n-1$ do
4: if $s_{pivot_row,j} == 0$ then
5: mask1 = 1
6: else
7: mask1 = 0
8: end if
9: if $s_{i,j} == 1$ then
10: mask2 = 1
11: else
12: mask2 = 0
13: end if
14: if $i \ge \text{pivot_row}$ then
15: mask3 = 1
16: else
17: mask3 = 0
18: end if
19: $s_{pivot_row} \leftarrow s_{pivot_row} \oplus (s_i \land (\text{mask1} \land (\text{mask2} \land \text{mask3})))$
20: $s_i \leftarrow s_i \oplus (s_{pivot_row} \land (\text{mask2} \land \text{mask3}))$
21: end for
22: if $s_{pivot_row,j} = 1$ and $\text{pivot_row} < n$ then
23: $pivot_row = \text{pivot_row} + 1$
24: end if
25: end for

<figure><img src="image_3.png" /><figcaption>**Fig. 2:** Operations on matrix rows according to mask values. In red, paths leading to XOR on rows with $s_p$ the pivot row and $s_i$ the processed row</figcaption></figure>

In Algorithm 2, we observe two sources of leakage. The first one consists of the computation of *mask1*, *mask2* and *mask3*. These masks are set in an equivalent way, algorithmically, to secret-dependent branches. However, they
<caption>**Algorithm 2** Row reduction in constant-time</caption>

**Require:** $S \in \mathcal{M}_{n,m}(\mathbb{F}_2)$
**Ensure:** $S \in \mathcal{M}_{n,m}(\mathbb{F}_2)$ in row echelon form and its $rank = \text{pivot_row}$
1: $\text{pivot_row} = 0$
2: **for** $j = 0, \dots, m-1$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 0, \dots, n-1$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $s_{\text{pivot_row},j} == 0$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`mask1 = 1`
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`mask1 = 0`
8: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
9: &nbsp;&nbsp;&nbsp;&nbsp;**if** $s_{i,j} == 1$ **then**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`mask2 = 1`
11: &nbsp;&nbsp;&nbsp;&nbsp;**else**
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`mask2 = 0`
13: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
14: &nbsp;&nbsp;&nbsp;&nbsp;**if** $i \ge \text{pivot_row}$ **then**
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`mask3 = 1`
16: &nbsp;&nbsp;&nbsp;&nbsp;**else**
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`mask3 = 0`
18: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
19: &nbsp;&nbsp;&nbsp;&nbsp;`s_{\text{pivot_row}} \leftarrow s_{\text{pivot_row}} \oplus (s_i \land (\text{mask1} \land (\text{mask2} \land \text{mask3})))`
20: &nbsp;&nbsp;&nbsp;&nbsp;`s_i \leftarrow s_i \oplus (s_{\text{pivot_row}} \land (\text{mask2} \land \text{mask3}))`
21: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
22: &nbsp;&nbsp;&nbsp;&nbsp;**if** $s_{\text{pivot_row},j} = 1$ and $\text{pivot_row} < n$ **then**
23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`pivot_row = \text{pivot_row} + 1`
24: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
25: &nbsp;&nbsp;&nbsp;&nbsp;**end for**

<figure><img src="image_3.png" /><figcaption>**Fig. 2:** Operations on matrix rows according to mask values. In red, paths leading to XOR on rows with $s_p$ the pivot row and $s_i$ the processed row</figcaption></figure>

In Algorithm 2, we observe two sources of leakage. The first one consists of the computation of `mask1`, `mask2` and `mask3`. These masks are set in an equivalent way, algorithmically, to secret-dependent branches. However, they
are determined before an iterative conditional branching, namely in a weighted sum in the GitHub implementation. We exploit a leakage in the computation of this weighted sum to recover theirs values. Listing 1 details the implementation of mask2 computation in the GitHub version.

<caption>Listing 1: Function to compute mask2 introduced in Algorithm 2 and from GitHub implementation [2]</caption>

1 int bfnetmask(bfCompute_mask(bfElement_t *mask, bfElement_t *a, uint8_t bit_position)
2 {
3 // Determine the processed bit
4 uint8_t pos = bit_position / 64u;
5 // Determine the bit position
6 uint8_t bit = ((uint64_t) (pos * (a->high >> (bit_position - 64u))) ^ (1u-pos)*(a->low >> bit_position)) & 0x1u;
7 mask->low = -(((uint64_t) bit);
8 mask->high = (uint64_t) -(((uint8_t) bit) & ROLLO_I_BF_MASK_HIGH;
9 }

We notice that if the processed coefficient, defined as "bit" in line 6, is equal to one, all bits of mask2 are set to one, otherwise all bits are set to zero (lines 7-8). The same kind of operations are observed for mask1 and mask3. However, the leakage from flipping all the bits to 1 or to 0 differs. We deduce that it is possible to recover the masks values.

The second source of leakage comes from the bitwise AND and XOR applied on the syndrome matrix rows. Indeed, in lines 19-20 in Algorithm 2, the rows are XORed with either zero or non-zero row according to the masks values. The second source of leakage has not been exploited because it is equivalent to what we observe with the masks’ recovery. However, it is always a good point of interest for side-channel attacks.

As in the previous attack, the masks values recovery allows us to obtain a system of linear equations. We define three vectors containing respectively the values of mask1, mask2 and mask2 ∧ mask3 after the iteration j:

$$
\sigma_{\text{mask1},j} = (\sigma_{0,j}, \dots, \sigma_{n-1,j}), \quad \sigma_{\text{mask2},j} = (\sigma'_{0,j}, \dots, \sigma'_{n-1,j}),
$$

$$
\sigma_{\text{mask2}\wedge\text{mask3},j} = (\sigma''_{0,j}, \dots, \sigma''_{n-1,j}),
$$

with $\sigma_{i,j}, \sigma'_{i,j}, \sigma''_{i,j} = 0$ or 1 when mask1, mask2, mask2 $\land$ mask3 = 0 or 1.
As we can see in Figure 2, when mask1 = 1, only one path leads to operations
on rows. Moreover, once we have mask1 = mask2 = mask3 = 1, mask1 = 0
until the end of the column treatment. Then, we have three cases for the pivot:

* If the vector $\sigma_{\text{mask1},j}$ contains only zeros, then the leading coefficient in the pivot row is already one.

* If the vector $\sigma_{\text{mask1},j}$ contains only ones then either the pivot is on the last row, and we need to consider mask2 and mask3 or the column does not contain a pivot.
are determined before an iterative conditional branching, namely in a weighted sum in the *GitHub* implementation. We exploit a leakage in the computation of this weighted sum to recover theirs values. Listing 1 details the implementation of *mask2* computation in the *GitHub* version.

<caption>Listing 1: Function to compute *mask2* introduced in Algorithm 2 and from *GitHub* implementation [2]</caption>

1 int bfnetmask(bfCompute_mask(bfElement_t *mask, bfElement_t *a, uint8_t bit_position)
2 {
3 // Determine the processed bit
4 uint8_t pos = bit_position / 64u;
5 // Determine the bit position
6 uint8_t bit = ((uint64_t) (pos * (a->high >> (bit_position - 64u))) ^ (1u-pos)*(a->low >> bit_position)) & 0x1u;
7 mask->low = -(uint64_t) bit;
8 mask->high = (uint64_t) -(uint8_t) bit & ROLLO_I_BF_MASK_HIGH;
9 }

We notice that if the processed coefficient, defined as "bit" in line 6, is equal to one, all bits of *mask2* are set to one, otherwise all bits are set to zero (lines 7-8). The same kind of operations are observed for *mask1* and *mask3*. However, the leakage from flipping all the bits to 1 or to 0 differs. We deduce that it is possible to recover the masks values.

The second source of leakage comes from the bitwise AND and XOR applied on the syndrome matrix rows. Indeed, in lines 19-20 in Algorithm 2, the rows are XORed with either zero or non-zero row according to the masks values. The second source of leakage has not been exploited because it is equivalent to what we observe with the masks’ recovery. However, it is always a good point of interest for side-channel attacks.

As in the previous attack, the masks values recovery allows us to obtain a system of linear equations. We define three vectors containing respectively the values of *mask1*, *mask2* and *mask2* AND *mask3* after the iteration *j*:

$$ \sigma_{mask1,j} = (\sigma_{0,j}, \dots, \sigma_{n-1,j}), \quad \sigma_{mask2,j} = (\sigma'_{0,j}, \dots, \sigma'_{n-1,j}), $$

$$ \sigma_{mask2 \land mask3,j} = (\sigma''_{0,j}, \dots, \sigma''_{n-1,j}), $$

with $\sigma_{i,j}, \sigma'_{i,j}, \sigma''_{i,j} = 0$ or 1 when *mask1*, *mask2*, *mask2* AND *mask3* = 0 or 1. As we can see in Figure 2, when *mask1* = 1, only one path leads to operations on rows. Moreover, once we have *mask1* = *mask2* = *mask3* = 1, *mask1* = 0 until the end of the column treatment. Then, we have three cases for the pivot:

* If the vector $\sigma_{mask1,j}$ contains only zeros, then the leading coefficient in the pivot row is already one.

* If the vector $\sigma_{mask1,j}$ contains only ones then either the pivot is on the last row, and we need to consider *mask2* and *mask3* or the column does not contain a pivot.
14 Side-Channel Attack on ROLLO PQC scheme

* If the vector $\sigma_{mask1,j}$ contains zeros and ones, the position of the last one is the index of the added row to the pivot row in the column $j$.

We determine the system of linear equations as previously with two matrices depending on respectively of mask1 and mask2 AND mask3:

$$ \mathbf{J}_k = \begin{pmatrix} 1 & \cdots & 0 & 0 & \cdots & 0 & \cdots & 0 \\ \vdots & & \vdots & \vdots & & \vdots & & \vdots \\ 0 & \cdots & 1 & 0 & \cdots & 1 & \cdots & 0 \\ \vdots & & \vdots & \vdots & & \vdots & & \vdots \\ 0 & \cdots & 0 & 0 & \cdots & 0 & \cdots & 1 \\ \uparrow & & \uparrow & & & \uparrow & & \uparrow \end{pmatrix}_{\substack{\text{pivot index} \\ k}} \leftarrow k, \quad \mathbf{J}'_k = \begin{pmatrix} 1 & \cdots & \sigma''_{0,k} & \cdots & 0 \\ \vdots & & \vdots & & \vdots \\ 0 & \cdots & 1 & \cdots & 0 \\ \vdots & & \vdots & & \vdots \\ 0 & \cdots & \sigma''_{n-1,k} & \cdots & 1 \\ \uparrow & & \uparrow & & \uparrow \end{pmatrix}_{\substack{\text{k} \\ k}} \leftarrow k. $$

The vector $\sigma_{mask2,j}$ depends on the coefficients processed in the column $j$. Therefore, $\sigma_{mask2,0}$ gives us the first column as there is no pre-processing on rows. After the first iteration, we have to consider XORs performed on rows of the matrix during the treatment of the column $j-1$.

For example, after the treatment of the column 0, the positions of the executed XORs are given in the resulting matrix $\mathbf{J}'_0 \times \mathbf{J}_0$. Thus, for the column 1, we use a linear solver on the system

$$ \mathbf{J}'_0 \times \mathbf{J}_0 \times \mathbf{S}[0] = (\sigma_{mask2,1})^t. $$

More generally, to recover the column $j \ge 1$, we have to solve the system of linear equations

$$ \left( \prod_{k=j-1, \dots, 0} \mathbf{J}'_k \times \mathbf{J}_k \right) \times \mathbf{S}[j] = (\sigma_{mask2,j})^t. $$

## 3.3 Experimental results of our power consumption analysis

In this section, we demonstrate the practicability of the attack on an ARM SecurCore SC300 32-bit processor (equivalent to CORTEX-M3). We implemented ROLLO-I-128 in C. The first implementation corresponds to the reference one and the second to the GitHub version [2]

ROLLO-I-128 traces are captured with a Lecroy SDA 725Zi-A oscilloscope with a bandwidth of 2.5 GHz. We put a trigger right before the execution of the Gaussian elimination. The measurements for the reference implementation are given in Figure 3. The power trace of the first inner for loop (line 4 - Algorithm 1) is given in Figure 3a and the power trace of the second inner for loop (line 13-Algorithm 1) is given in Figure 3b. We can observe the difference of power consumption when 32-bit words are multiplied either by one or by zero.
14 Side-Channel Attack on ROLLO PQC scheme

* If the vector $\sigma_{mask1,j}$ contains zeros and ones, the position of the last one is the index of the added row to the pivot row in the column $j$.

We determine the system of linear equations as previously with two matrices depending on respectively of mask1 and mask2 AND mask3:

$$ \mathbf{J}_k = \begin{pmatrix} 1 & \cdots & 0 & 0 & \cdots & 0 & \cdots & 0 \\ \vdots & & \vdots & \vdots & & \vdots & & \vdots \\ 0 & \cdots & 1 & 0 & \cdots & 1 & \cdots & 0 \\ \vdots & & \vdots & \vdots & & \vdots & & \vdots \\ 0 & \cdots & 0 & 0 & \cdots & 0 & \cdots & 1 \\ \uparrow & & \uparrow & & & \uparrow & & \uparrow \end{pmatrix}_{\substack{\text{pivot index} \\ k}} \leftarrow k, \quad \mathbf{J}'_k = \begin{pmatrix} 1 & \cdots & \sigma''_{0,k} & \cdots & 0 \\ \vdots & & \vdots & & \vdots \\ 0 & \cdots & 1 & \cdots & 0 \\ \vdots & & \vdots & & \vdots \\ 0 & \cdots & \sigma''_{n-1,k} & \cdots & 1 \\ \uparrow & & \uparrow & & \uparrow \end{pmatrix}_{\substack{\text{pivot index} \\ k}} \leftarrow k. $$

The vector $\sigma_{mask2,j}$ depends on the coefficients processed in the column $j$. Therefore, $\sigma_{mask2,0}$ gives us the first column as there is no pre-processing on rows. After the first iteration, we have to consider XORs performed on rows of the matrix during the treatment of the column $j-1$.

For example, after the treatment of the column 0, the positions of the executed XORs are given in the resulting matrix $\mathbf{J}'_0 \times \mathbf{J}_0$. Thus, for the column 1, we use a linear solver on the system

$$ \mathbf{J}'_0 \times \mathbf{J}_0 \times \mathbf{S}[0] = (\sigma_{mask2,1})^t. $$

More generally, to recover the column $j \ge 1$, we have to solve the system of linear equations

$$ \left( \prod_{k=j-1, \dots, 0} \mathbf{J}'_k \times \mathbf{J}_k \right) \times \mathbf{S}[j] = (\sigma_{mask2,j})^t. $$

## 3.3 Experimental results of our power consumption analysis

In this section, we demonstrate the practicability of the attack on an ARM SecurCore SC300 32-bit processor (equivalent to CORTEX-M3). We implemented ROLLO-I-128 in C. The first implementation corresponds to the reference one and the second to the GitHub version [2].

ROLLO-I-128 traces are captured with a Lecroy SDA 725Zi-A oscilloscope with a bandwidth of 2.5 GHz. We put a trigger right before the execution of the Gaussian elimination. The measurements for the reference implementation are given in Figure 3. The power trace of the first inner for loop (line 4 - Algorithm 1) is given in Figure 3a and the power trace of the second inner for loop (line 13-Algorithm 1) is given in Figure 3b. We can observe the difference of power consumption when 32-bit words are multiplied either by one or by zero.
The difference of pattern leads us to recover the *mask* values of the two inner **for** loops. For example, we observe in Figure 3 the beginning of the treatment of the first column:

$$ \sigma_0 = (0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, \dots), \sigma'_0 = (*, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, \dots). $$

<figure><img src="image_4.png" /><figcaption>(a) Full trace and a zoom of the first inner loop</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(b) Full trace and a zoom of the second inner loop</figcaption></figure>

**Fig. 3:** Measurements for the reference implementation - traces of the two inner loops in Gaussian elimination for the processing of one column in ROLLO-I-128: in green the treatment when the bit is 0 and in red when the bit is 1
The difference of pattern leads us to recover the mask values of the two inner for loops. For example, we observe in Figure 3 the beginning of the treatment of the first column:

$$ \sigma_0 = (0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, \dots), \sigma'_0 = (*, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, \dots). $$

<figure><img src="image_4.png" /><figcaption>(a) Full trace and a zoom of the first inner loop</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(b) Full trace and a zoom of the second inner loop</figcaption></figure>

**Fig. 3:** Measurements for the reference implementation - traces of the two inner loops in Gaussian elimination for the processing of one column in ROLLO-I-128: in green the treatment when the bit is 0 and in red when the bit is 1
16 Side-Channel Attack on ROLLO PQC scheme

The measurement for the *GitHub* implementation is given in Figure 4. We can first observe the difference of patterns for the three masks values at each inner iteration. For a better understanding, we highlight each time the computation of the different masks. Then, we can perform the attack from the recovered masks values:

$$
\left.
\begin{array}{l}
\sigma_{\text{mask1,1}} = (1, 1, 1, 0, 0, 0, \dots), \\
\sigma_{\text{mask2,1}} = (1, 0, 1, 0, 0, 1, 0, \dots) \\
\sigma_{\text{mask3,1}} = (0, 0, 1, 1, 1, 1, 1, \dots)
\end{array}
\right\}
\qquad \sigma_{\text{mask2}\wedge\text{mask3,1}} = (0, 0, 1, 0, 0, 1, 0, \dots).
$$

<figure><img src="image_6.png" /><figcaption>Fig. 4: Measurement for the *GitHub* implementation - trace of the treatment of one column in ROLLO-I-128</figcaption></figure>

3.4 Experiments with a Cortex-M4 and comparison

In this section, we show that the attack is also applicable on an ARM Cortex-
M4. For the experiments we used the ROLLO-I-128 implementation provided
in the *mupq* github on a STM32F4 ChipWhisperer microcontroller available
at https://github.com/mupq/mupq/tree/Round2/crypto_kem.

The traces are captured with a RTO2000 oscilloscope with bandwidth 3GHz.
We put a trigger right before the execution of the Gaussian elimination.

Figure 5 provides measurements obtained with a Cortex-M4. Similarly to
Figure 3 with a Cortex-M3, the traces are annotated with rectangles and colors:
green for a mask at 0 and red for a mask at 1.
16 Side-Channel Attack on ROLLO PQC scheme

The measurement for the *GitHub* implementation is given in Figure 4. We can first observe the difference of patterns for the three masks values at each inner iteration. For a better understanding, we highlight each time the computation of the different masks. Then, we can perform the attack from the recovered masks values:

$$
\left.
\begin{array}{l}
\sigma_{\text{mask1,1}} = (1, 1, 1, 0, 0, 0, \dots), \\
\sigma_{\text{mask2,1}} = (1, 0, 1, 0, 0, 1, 0, \dots) \\
\sigma_{\text{mask3,1}} = (0, 0, 1, 1, 1, 1, 1, \dots)
\end{array}
\right\}
\quad
\sigma_{\text{mask2}\wedge\text{mask3,1}} = (0, 0, 1, 0, 0, 1, 0, \dots).
$$

<figure><img src="image_6.png" /><figcaption>Fig. 4: Measurement for the *GitHub* implementation - trace of the treatment of one column in ROLLO-I-128</figcaption></figure>

3.4 Experiments with a Cortex-M4 and comparison

In this section, we show that the attack is also applicable on an ARM Cortex-
M4. For the experiments we used the ROLLO-I-128 implementation provided
in the *mupq* github on a STM32F4 ChipWhisperer microcontroller available
at https://github.com/mupq/mupq/tree/Round2/crypto_kem.

The traces are captured with a RTO2000 oscilloscope with bandwidth 3GHz.
We put a trigger right before the execution of the Gaussian elimination.

Figure 5 provides measurements obtained with a Cortex-M4. Similarly to
Figure 3 with a Cortex-M3, the traces are annotated with rectangles and colors:
green for a mask at 0 and red for a mask at 1.
<figure><img src="image_7.png" /><figcaption>**Fig. 5:** Measurement for the processing, on the Cortex M4, of one column in the Gaussian elimination from the reference implementation</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>**Fig. 5:** Measurement for the processing, on the Cortex M4, of one column in the Gaussian elimination from the reference implementation</figcaption></figure>
18 Side-Channel Attack on ROLLO PQC scheme

We notice that in Figure 3a the difference between a mask at 0 and a mask at 1 is more pronounced than in Figure 5a. In fact, in the latter, the difference of power consumption between both masks is smaller and requires looking carefully at the end of the pattern to distinguish them. For Figure 3b and Figure 5b, the patterns for a mask at 0 and a mask at 1 are similar. However, we notice that the decreasing power in the pattern of a mask at 0 is more accentuated in Figure 5b.

4 Countermeasures

In this section, we propose two solutions to protect the future implementations against our attack. It is important to emphasize that the implementations with the countermeasures remain in constant-time.

First countermeasure for the reference implementation.

The first countermeasure consists in reducing the differentiation between a multiplication of a word by zero or by one. For this, we mask the coefficients processed. In the first inner **for** loop, we split the pivot row into two parts. Thus, for each iteration, we compute

$$s_{\text{pivot_row}} = s_{\text{pivot_row}} \oplus s_{\text{pivot_row}},$$

with $s_{\text{pivot_row}}, s_{\text{pivot_row}} \in \mathbb{F}_{2^m}$. The variable *tmp* (line 6 - Algorithm 1) is then computed as

$$tmp = (\text{mask}' \land (s_i \oplus s_{\text{pivot_row}})) \lor (\neg \text{mask}' \land s_{\text{pivot_row}}),$$

with $\text{mask}' = \neg(\text{mask} - 1)$. Then, we can update the pivot row by computing

$$s_{\text{pivot_row}} = s_{\text{pivot_row}} \oplus tmp.$$

If $i \le \text{pivot_row}$, we have

$$dummy = s_{\text{pivot_row}} \oplus tmp.$$

The same operations are performed in the second inner **for** loop by replacing the pivot row by the processed row $s_i$. With this countermeasure, whether the mask is zero or one, we always perform the same operations, namely two bitwise ANDs between non-zero and zero words. Thus, we are not able to distinguish different patterns when *mask* equals 0 or 1. We applied the same set up as in Section 3.3 to illustrate this in Figure 6.
18 Side-Channel Attack on ROLLO PQC scheme

We notice that in Figure 3a the difference between a mask at 0 and a mask at 1 is more pronounced than in Figure 5a. In fact, in the latter, the difference of power consumption between both masks is smaller and requires looking carefully at the end of the pattern to distinguish them. For Figure 3b and Figure 5b, the patterns for a mask at 0 and a mask at 1 are similar. However, we notice that the decreasing power in the pattern of a mask at 0 is more accentuated in Figure 5b.

4 Countermeasures

In this section, we propose two solutions to protect the future implementations against our attack. It is important to emphasize that the implementations with the countermeasures remain in constant-time.

First countermeasure for the reference implementation.

The first countermeasure consists in reducing the differentiation between a multiplication of a word by zero or by one. For this, we mask the coefficients processed. In the first inner **for** loop, we split the pivot row into two parts. Thus, for each iteration, we compute

$$s_{\text{pivot_row}} = s_{\text{pivot_row}} \oplus s_{\text{pivot_row}},$$

with $s_{\text{pivot_row}}, s_{\text{pivot_row}} \in \mathbb{F}_{2^m}$. The variable *tmp* (line 6 - Algorithm 1) is then computed as

$$tmp = (\text{mask}' \land (s_i \oplus s_{\text{pivot_row}})) \lor (\neg \text{mask}' \land s_{\text{pivot_row}}),$$

with $\text{mask}' = \neg(\text{mask} - 1)$. Then, we can update the pivot row by computing

$$s_{\text{pivot_row}} = s_{\text{pivot_row}} \oplus tmp.$$

If $i \le \text{pivot_row}$, we have

$$dummy = s_{\text{pivot_row}} \oplus tmp.$$

The same operations are performed in the second inner **for** loop by replacing the pivot row by the processed row $s_i$. With this countermeasure, whether the mask is zero or one, we always perform the same operations, namely two bitwise ANDs between non-zero and zero words. Thus, we are not able to distinguish different patterns when *mask* equals 0 or 1. We applied the same set up as in Section 3.3 to illustrate this in Figure 6.
<figure><img src="image_8.png" /><figcaption>Fig. 6: First **for** loop trace of Gaussian elimination with masking countermeasure</figcaption></figure>

Second countermeasure for both implementations.

The second countermeasure is based on shuffling. The treatment of each column is performed randomly by using an algorithm generating a random permutation of a finite set, such as the Fisher-Yates method (given in Appendix B). The choice is left to the developer under condition of a good implementation.

Given a list of $n$ elements to shuffle, the Fisher-Yates method starts with a random function that generates a random number $j$ such that $1 \le j \le n-k$ where $k$ is the number of elements already processed. Then, the elements are processed in decreasing order. Namely, in the first iteration, the last element of the list is swapped with the $j$-th element and goes on until the first element is reached.

For the reference implementation, a list containing the coefficients indexes is randomized before the two inner **for** loops. Then, at each iteration, the pivot row is chosen randomly and the randomized list gives the proceeding order for the other coefficients in the column. This countermeasure is presented in Appendix A (Algorithm 3). The indexes are shuffled before the two inner **for** loops, then there is no correlation between the masks of the first **for** loop (line 4 - Algorithm 1) and the masks of the second **for** loop (line 13 - Algorithm 1).
<figure><img src="image_8.png" /><figcaption>Fig. 6: First **for** loop trace of Gaussian elimination with masking countermeasure</figcaption></figure>

*Second countermeasure for both implementations.*

The second countermeasure is based on shuffling. The treatment of each column is performed randomly by using an algorithm generating a random permutation of a finite set, such as the Fisher-Yates method (given in Appendix B). The choice is left to the developer under condition of a good implementation.

Given a list of $n$ elements to shuffle, the Fisher-Yates method starts with a random function that generates a random number $j$ such that $1 \le j \le n-k$ where $k$ is the number of elements already processed. Then, the elements are processed in decreasing order. Namely, in the first iteration, the last element of the list is swapped with the $j$-th element and goes on until the first element is reached.

For the reference implementation, a list containing the coefficients indexes is randomized before the two inner **for** loops. Then, at each iteration, the pivot row is chosen randomly and the randomized list gives the proceeding order for the other coefficients in the column. This countermeasure is presented in Appendix A (Algorithm 3). The indexes are shuffled before the two inner **for** loops, then there is no correlation between the masks of the first **for** loop (line 4 - Algorithm 1) and the masks of the second **for** loop (line 13 - Algorithm 1).
For the *GitHub* implementation, a similar countermeasure is performed. presented in Appendix A (Algorithm 4). In this case, for each column (in the main **for** loop) the pivot row is chosen randomly and the indexes are shuffled using Fisher-Yates method.

With the randomization countermeasure, an attacker can distinguish patterns related to the masks values for both implementations, but not determine the order of elements. Moreover, a brute force attack is not achievable. Indeed, an adversary has *n!* possibilities for each column, which implies a total of (*n!*)$^m$ possibilities to recover the whole syndrome matrix. For instance, with ROLLO-I-128 parameters the complexity is approximately $2^{27731}$. Thus, only the number of zeros and ones on the matrix will be known.

We provide in Table 2 the performances' analysis for the SC300 processor of the impact of our countermeasures. This impact depends on the board and the used random number generator. We counted the cycles by using IAR Embedded Workbench IDE for ARM compiler C/C++ with high-speed optimization level. This tool is available at https://www.iar.com/knowledge/learn/debugging/how-to-measure-execution-time-with-cyclecounter/.

<table><caption>**Table 2:** Impact factor of Gaussian elimination with and without countermeasures for ARM securCore SC300 processor</caption><thead><tr><th rowspan="2">implementation</th><th colspan="3">Reference</th><th colspan="2">GitHub</th></tr><tr><th>masking</th><th>randomization</th><th>without</th><th>randomization</th><th>without</th></tr></thead><tbody><tr><td>countermeasure</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td># cycles (×10<sup>6</sup>)</td><td>3,15</td><td>2,5</td><td>1,82</td><td>2,9</td><td>2,22</td></tr></tbody></table>

## 5 Conclusion

We show in this paper that constant-time implementation of Gaussian elimination provided in [1] is sensitive to power consumption attacks. We exploit the weakness introduced by the variable *mask* to avoid previous timing attacks. This information leakage allows us to make the first attack by power consumption on the last implementation version given by the authors of ROLLO. We can also apply our side-channel attack on another implementation of ROLLO-I-128 [2]. These attacks can lead to a full key-recovery using one single trace. To secure the implementations, we propose two different countermeasures. The first one can be applied to [1] by hiding the values of *mask*. The second countermeasure can be applied to both implementations. The idea is to treat each row in a column of the matrix randomly. It adds randomness which makes our attack not exploitable in practice anymore. We base our work on traces got from Cortex-M3 and Cortex-M4 microcontrollers. The constant-time Gaussian elimination function is in the *rbc_library* library. This library is also used in the implementation of the RQC scheme. Even though the Gaussian elimination in constant time is not used in the RQC implementation, the entire library should be analyzed to find possible leakage. In particular, we want to analyze the Karatsuba function used in both ROLLO implementation and the
For the *GitHub* implementation, a similar countermeasure is performed. presented in Appendix A (Algorithm 4). In this case, for each column (in the main **for** loop) the pivot row is chosen randomly and the indexes are shuffled using Fisher-Yates method.

With the randomization countermeasure, an attacker can distinguish patterns related to the masks values for both implementations, but not determine the order of elements. Moreover, a brute force attack is not achievable. Indeed, an adversary has *n!* possibilities for each column, which implies a total of (*n!*)$^m$ possibilities to recover the whole syndrome matrix. For instance, with ROLLO-I-128 parameters the complexity is approximately $2^{27731}$. Thus, only the number of zeros and ones on the matrix will be known.

We provide in Table 2 the performances' analysis for the SC300 processor of the impact of our countermeasures. This impact depends on the board and the used random number generator. We counted the cycles by using IAR Embedded Workbench IDE for ARM compiler C/C++ with high-speed optimization level. This tool is available at https://www.iar.com/knowledge/learn/debugging/how-to-measure-execution-time-with-cyclecounter/.

<table><caption>**Table 2:** Impact factor of Gaussian elimination with and without countermeasures for ARM securCore SC300 processor</caption><thead><tr><th rowspan="2">implementation</th><th colspan="3">Reference</th><th colspan="2">GitHub</th></tr><tr><th>masking</th><th>randomization</th><th>without</th><th>randomization</th><th>without</th></tr></thead><tbody><tr><td>countermeasure</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td># cycles (×10<sup>6</sup>)</td><td>3,15</td><td>2,5</td><td>1,82</td><td>2,9</td><td>2,22</td></tr></tbody></table>

## 5 Conclusion

We show in this paper that constant-time implementation of Gaussian elimination provided in [1] is sensitive to power consumption attacks. We exploit the weakness introduced by the variable *mask* to avoid previous timing attacks. This information leakage allows us to make the first attack by power consumption on the last implementation version given by the authors of ROLLO. We can also apply our side-channel attack on another implementation of ROLLO-I-128 [2]. These attacks can lead to a full key-recovery using one single trace. To secure the implementations, we propose two different countermeasures. The first one can be applied to [1] by hiding the values of *mask*. The second countermeasure can be applied to both implementations. The idea is to treat each row in a column of the matrix randomly. It adds randomness which makes our attack not exploitable in practice anymore. We base our work on traces got from Cortex-M3 and Cortex-M4 microcontrollers. The constant-time Gaussian elimination function is in the *rbc_library* library. This library is also used in the implementation of the RQC scheme. Even though the Gaussian elimination in constant time is not used in the RQC implementation, the entire library should be analyzed to find possible leakage. In particular, we want to analyze the Karatsuba function used in both ROLLO implementation and the
polynomial multiplication for computation over ideal codes in RQC. Another
perspective could be to analyze the various implementations of the Gaussian
elimination in the third round candidates to the NIST PQC standardization
process.

**Acknowledgments.** The authors would like to thank Benoît Gérard for his helpful advice.
polynomial multiplication for computation over ideal codes in RQC. Another
perspective could be to analyze the various implementations of the Gaussian
elimination in the third round candidates to the NIST PQC standardization
process.

**Acknowledgments.** The authors would like to thank Benoît Gérard for his helpful advice.
# Appendix A Algorithms for countermeasures with randomization

**Algorithm 3** Gaussian elimination in constant time with randomization

**Require:** $S \in \mathcal{M}_{n,m}(\mathbb{F}_2)$

**Ensure:** $S \in \mathcal{M}_{n,m}(\mathbb{F}_2)$ in systematic form

1: $\mathit{mask} = \mathit{dimension} = 0$

2: $L \leftarrow \text{array containing indexes } 0, \dots, n-1$

3: **for** $j = 0, \dots, m-1$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp;`pivot_row` = min(`dimension`, $n-1$)

5: &nbsp;&nbsp;&nbsp;&nbsp;`randpivot` = random(`pivot_row` + 1, $n-1$)

6: &nbsp;&nbsp;&nbsp;&nbsp;exchange $s_{\text{pivot_row}}$ and $s_{\text{randpivot}}$

7: &nbsp;&nbsp;&nbsp;&nbsp;$L$ = FisherYatesShuffle($L$)

8: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 0, \dots, n-1$ **do**

9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`randrow` = $L[i]$

10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`mask` = $s_{\text{pivot_row},j} \oplus s_{\text{randrow},j}$

11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`tmp` = `mask` $\otimes$ $s_{\text{randrow}}$

12: &nbsp;&nbsp;&nbsp;&nbsp;**if** `randrow` > `pivot_row` **then**

13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$s_{\text{pivot_row}}$ = $s_{\text{pivot_row}} \oplus \text{tmp}$

14: &nbsp;&nbsp;&nbsp;&nbsp;**else**

15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dummy = $s_{\text{pivot_row}} \oplus \text{tmp}$

16: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

17: &nbsp;&nbsp;&nbsp;&nbsp;**end for**

18: &nbsp;&nbsp;&nbsp;&nbsp;$L$ = FisherYatesShuffle($L$)

19: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 0, \dots, n-1$ **do**

20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`randrow` = $L[i]$

21: &nbsp;&nbsp;&nbsp;&nbsp;**if** `randrow` $\neq$ $j$ **then**

22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`mask` = $s_{\text{randrow},j}$

23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`tmp` = `mask` $\otimes$ $s_{\text{pivot_row}}$

24: &nbsp;&nbsp;&nbsp;&nbsp;**if** `dimension` < $n$ **then**

25: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$s_{\text{randrow}}$ = $s_{\text{randrow}} \oplus \text{tmp}$

26: &nbsp;&nbsp;&nbsp;&nbsp;**else**

27: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dummy = $s_{\text{randrow}} \oplus \text{tmp}$

28: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

29: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

30: &nbsp;&nbsp;&nbsp;&nbsp;**end for**

31: &nbsp;&nbsp;&nbsp;&nbsp;`dimension` = `dimension` + $s_{\text{pivot_row},i}$

32: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
# Appendix A Algorithms for countermeasures with randomization

**Algorithm 3** Gaussian elimination in constant time with randomization

**Require:** $S \in \mathcal{M}_{n,m}(\mathbb{F}_2)$

**Ensure:** $S \in \mathcal{M}_{n,m}(\mathbb{F}_2)$ in systematic form

1: $\mathit{mask} = \mathit{dimension} = 0$

2: $L \leftarrow \text{array containing indexes } 0, \dots, n-1$

3: **for** $j = 0, \dots, m-1$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp;`pivot_row` = `min`(dimension, $n-1$)

5: &nbsp;&nbsp;&nbsp;&nbsp;`randpivot` = `random`(pivot_row + 1, $n-1$)

6: &nbsp;&nbsp;&nbsp;&nbsp;exchange $s_{\text{pivot_row}}$ and $s_{\text{randpivot}}$

7: &nbsp;&nbsp;&nbsp;&nbsp;$L$ = FisherYatesShuffle($L$)

8: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 0, \dots, n-1$ **do**

9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`randrow` = $L[i]$

10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`mask` = $s_{\text{pivot_row},j} \oplus s_{\text{randrow},j}$

11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`tmp` = `mask` $\otimes$ $s_{\text{randrow}}$

12: &nbsp;&nbsp;&nbsp;&nbsp;**if** `randrow` > pivot_row **then**

13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$s_{\text{pivot_row}}$ = $s_{\text{pivot_row}} \oplus \text{tmp}$

14: &nbsp;&nbsp;&nbsp;&nbsp;**else**

15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dummy = $s_{\text{pivot_row}} \oplus \text{tmp}$

16: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

17: &nbsp;&nbsp;&nbsp;&nbsp;**end for**

18: &nbsp;&nbsp;&nbsp;&nbsp;$L$ = FisherYatesShuffle($L$)

19: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 0, \dots, n-1$ **do**

20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`randrow` = $L[i]$

21: &nbsp;&nbsp;&nbsp;&nbsp;**if** `randrow` $\neq$ $j$ **then**

22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`mask` = $s_{\text{randrow},j}$

23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`tmp` = `mask` $\otimes$ $s_{\text{pivot_row}}$

24: &nbsp;&nbsp;&nbsp;&nbsp;**if** dimension < $n$ **then**

25: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$s_{\text{randrow}}$ = $s_{\text{randrow}} \oplus \text{tmp}$

26: &nbsp;&nbsp;&nbsp;&nbsp;**else**

27: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dummy = $s_{\text{randrow}} \oplus \text{tmp}$

28: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

29: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

30: &nbsp;&nbsp;&nbsp;&nbsp;**end for**

31: &nbsp;&nbsp;&nbsp;&nbsp;dimension = dimension + $s_{\text{pivot_row},i}$

32: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
**Algorithm 4** Row echelon form in constant time with randomization

**Require:** $S \in \mathcal{M}_{n,m}(\mathbb{F}_2)$

**Ensure:** $S \in \mathcal{M}_{n,m}(\mathbb{F}_2)$ in row echelon form and its $\text{rank} = \text{pivot_row}$

1: $\text{pivot_row} = 0$

2: $L \leftarrow \text{array containing indexes } 0, \dots, n-1$

3: **for** $j = 0, \dots, m-1$ **do**

4:     $\text{randpivot} = \text{random}(\text{pivot_row} + 1, n-1)$

5:     exchange $s_{\text{pivot_row}}$ and $s_{\text{randpivot}}$

6:     $L = \text{FisherYatesShuffle}(L)$

7:     **for** $i = 0, \dots, n-1$ **do**

8:         $\text{randrow} = L[i]$

9:         **if** $s_{\text{pivot_row},j} == 0$ **then**

10:             $\text{mask1} = 1$

11:             **else**

12:                 $\text{mask1} = 0$

13:             **end if**

14:             **if** $s_{\text{randrow},j} == 1$ **then**

15:                 $\text{mask2} = 1$

16:             **else**

17:                 $\text{mask2} = 0$

18:             **end if**

19:             **if** $\text{randrow} \ge \text{pivot_row}$ **then**

20:                 $\text{mask3} = 1$

21:             **else**

22:                 $\text{mask3} = 0$

23:             **end if**

24:         $s_{\text{pivot_row}} \leftarrow s_{\text{pivot_row}} \oplus s_i \wedge (\text{mask1} \wedge (\text{mask2} \wedge \text{mask3}))$

25:         $s_{\text{randrow}} \leftarrow s_{\text{randrow}} \oplus s_{\text{pivot_row}} \wedge (\text{mask2} \wedge \text{mask3})$

26:     **end for**

27:     **if** $s_{\text{pivot_row},j} = 1$ and $\text{pivot_row} < n$ **then**

28:         $\text{pivot_row} = \text{pivot_row} + 1$

29:     **end if**

30: **end for**
**Algorithm 4** Row echelon form in constant time with randomization

**Require:** $S \in \mathcal{M}_{n,m}(\mathbb{F}_2)$

**Ensure:** $S \in \mathcal{M}_{n,m}(\mathbb{F}_2)$ in row echelon form and its $\text{rank} = \text{pivot_row}$

1: $\text{pivot_row} = 0$

2: $L \leftarrow \text{array containing indexes } 0, \dots, n-1$

3: **for** $j = 0, \dots, m-1$ **do**

4:     $\text{randpivot} = \text{random}(\text{pivot_row} + 1, n-1)$

5:     exchange $s_{\text{pivot_row}}$ and $s_{\text{randpivot}}$

6:     $L = \text{FisherYatesShuffle}(L)$

7:     **for** $i = 0, \dots, n-1$ **do**

8:         $\text{randrow} = L[i]$

9:         **if** $s_{\text{pivot_row},j} == 0$ **then**

10:             $\text{mask1} = 1$

11:             **else**

12:                 $\text{mask1} = 0$

13:             **end if**

14:             **if** $s_{\text{randrow},j} == 1$ **then**

15:                 $\text{mask2} = 1$

16:             **else**

17:                 $\text{mask2} = 0$

18:             **end if**

19:             **if** $\text{randrow} \ge \text{pivot_row}$ **then**

20:                 $\text{mask3} = 1$

21:             **else**

22:                 $\text{mask3} = 0$

23:             **end if**

24:                 $s_{\text{pivot_row}} \leftarrow s_{\text{pivot_row}} \oplus s_i \wedge (\text{mask1} \wedge (\text{mask2} \wedge \text{mask3}))$

25:                 $s_{\text{randrow}} \leftarrow s_{\text{randrow}} \oplus s_{\text{pivot_row}} \wedge (\text{mask2} \wedge \text{mask3})$

26:             **end for**

27:             **if** $s_{\text{pivot_row},j} = 1$ and $\text{pivot_row} < n$ **then**

28:                 $\text{pivot_row} = \text{pivot_row} + 1$

29:             **end if**

30:         **end for**
# Appendix B Fisher-Yates Algorithm

**Algorithm 5 FisherYatesShuffle**

**Require:** L list of n elements

**Ensure:** the list L shuffled

1: **for** i = n − 1 , · · · , 0 **do**

2: $j = \text{random()} \bmod i$

3: exchange $L_i$ and $L_j$

4: end for

# Appendix C Toy example for the attack for the reference implementation

Let us take a small example, with $q = 2$, $m = 5$ and $n = 7$, to illustrate the information leakage that we found.

Assume we want to recover the following matrix

$$
\begin{pmatrix}
1 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 & 0
\end{pmatrix}
$$

The searched matrix is defined as

$$
\mathbf{S} = \begin{pmatrix}
s_{0,0} & s_{0,1} & s_{0,2} & s_{0,3} & s_{0,4} \\
s_{1,0} & s_{1,1} & s_{1,2} & s_{1,3} & s_{1,4} \\
s_{2,0} & s_{2,1} & s_{2,2} & s_{2,3} & s_{2,4} \\
s_{3,0} & s_{3,1} & s_{3,2} & s_{3,3} & s_{3,4} \\
s_{4,0} & s_{4,1} & s_{4,2} & s_{4,3} & s_{4,4} \\
s_{5,0} & s_{5,1} & s_{5,2} & s_{5,3} & s_{5,4} \\
s_{6,0} & s_{6,1} & s_{6,2} & s_{6,3} & s_{6,4}
\end{pmatrix}
$$

corresponding to the syndrome $\mathbf{s} \in \mathbb{F}_{25}^7$.

After the execution of the Gaussian elimination process, we guess from the
power consumption analysis the masks in the first and second loops:

1. masks in the first loop for each column:

$$
\begin{align*}
& (*, 1, 1, 1, 0, 0, 0), (1, *, 1, 0, 1, 1, 0), (1, 0, *, 0, 1, 0, 1), (1, 1, 1, *, 0, 1, 1), \\
& \qquad (1, 1, 1, 0, *, 1, 0)
\end{align*}
$$

2. masks of the second loop for each column:

$$
\begin{align*}
& (*, 0, 0, 0, 1, 1, 1), (1, *, 1, 1, 0, 0, 1), (0, 1, *, 1, 0, 1, 0), (1, 1, 1, *, 0, 1, 0), \\
& \qquad (1, 1, 1, 0, *, 1, 1),
\end{align*}
$$

with * the pivot. As explained in Section 3.1, the * are replaced by one.
## Appendix B Fisher-Yates Algorithm

**Algorithm 5 FisherYatesShuffle**

**Require:** L list of n elements

**Ensure:** the list L shuffled

1: **for** i = n − 1 , · · · , 0 **do**

2: $j = \text{random()} \bmod i$

3: exchange $L_i$ and $L_j$

4: end for

## Appendix C Toy example for the attack for the reference implementation

Let us take a small example, with $q = 2$, $m = 5$ and $n = 7$, to illustrate the information leakage that we found.

Assume we want to recover the following matrix

$$
\begin{pmatrix}
1 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 & 0
\end{pmatrix}
$$

The searched matrix is defined as

$$
\mathbf{S} = \begin{pmatrix}
s_{0,0} & s_{0,1} & s_{0,2} & s_{0,3} & s_{0,4} \\
s_{1,0} & s_{1,1} & s_{1,2} & s_{1,3} & s_{1,4} \\
s_{2,0} & s_{2,1} & s_{2,2} & s_{2,3} & s_{2,4} \\
s_{3,0} & s_{3,1} & s_{3,2} & s_{3,3} & s_{3,4} \\
s_{4,0} & s_{4,1} & s_{4,2} & s_{4,3} & s_{4,4} \\
s_{5,0} & s_{5,1} & s_{5,2} & s_{5,3} & s_{5,4} \\
s_{6,0} & s_{6,1} & s_{6,2} & s_{6,3} & s_{6,4}
\end{pmatrix}
$$

corresponding to the syndrome $\mathbf{s} \in \mathbb{F}_{25}^7$.

After the execution of the Gaussian elimination process, we guess from the power consumption analysis the masks in the first and second loops:

1. masks in the first loop for each column:

$$
\begin{align*}
& (*, 1, 1, 1, 0, 0, 0), (1, *, 1, 0, 1, 1, 0), (1, 0, *, 0, 1, 0, 1), (1, 1, 1, *, 0, 1, 1), \\
& \qquad (1, 1, 1, 0, *, 1, 0)
\end{align*}
$$

2. masks of the second loop for each column:

$$
\begin{align*}
& (*, 0, 0, 0, 1, 1, 1), (1, *, 1, 1, 0, 0, 1), (0, 1, *, 1, 0, 1, 0), (1, 1, 1, *, 0, 1, 0), \\
& \qquad (1, 1, 1, 0, *, 1, 1),
\end{align*}
$$

with * the pivot. As explained in Section 3.1, the * are replaced by one.
Let us focus on recovering the two first columns of the syndrome matrix. The recovered masks vector of the first loop (1, 1, 1, 1, 0, 0, 0) provides the additions on the pivot row 0:

$$J_0 \times \mathbf{S} = \left( \frac{\begin{smallmatrix} 1 & 1 & 1 & 0 & 0 & 0 \end{smallmatrix}}{\mathbf{0}} \right) \times \mathbf{S}[0] = \left( \begin{array}{c} s_{0,0} + s_{1,0} + s_{2,0} + s_{3,0} \\ s_{1,0} \\ s_{2,0} \\ s_{3,0} \\ s_{4,0} \\ s_{5,0} \\ s_{6,0} \end{array} \right).$$

The masks vector of the second loop $\sigma'_0 = (1, 0, 0, 0, 1, 1, 1)$ is the solution vector of the system of linear equations where $s_{i,j}$ are unknowns. Thus, by applying a SageMath linear solver on the system

$$J_0 \times \mathbf{S}[0] = (1 \ 0 \ 0 \ 0 \ 1 \ 1 \ 1)^t,$$

we find the solution $(1, 0, 0, 0, 1, 1, 1)$, which corresponds to the first column of the syndrome matrix. SageMath is available at https://www.sagemath.org/. At the end of the process of the first column, we have the matrix

$$\mathbf{S}_0 = \left( \begin{array}{c|c} (\sigma'_0)^t & \mathbf{0} \\ \hline \mathbf{0} & I_6 \end{array} \right) \times J_0 \times \mathbf{S}.$$

For the second column, the recovered masks vector of the first loop is $(1, 0, 1, 0, 1, 1, 0)$. However, as explained in Section 3.1, only the rows for which the index row is greater than the index pivot row are added to the pivot row. Thus, in the recovered masks vector, we replace one by zero for $i < 1$. This gives us the vector $\sigma_1 = (0, 0, 1, 0, 1, 1, 0)$. In addition, the masks vector of the second loop is $\sigma'_1 = (1, 1, 1, 1, 0, 0, 1)$. We can then apply a SageMath linear solver on the system

$$\underbrace{\left( \begin{array}{c|c} 1 & 0 \ 0 \ 0 \ 0 \ 0 \ 0 \\ \hline 0 & 1 \ 1 \ 0 \ 1 \ 1 \ 0 \\ \hline \mathbf{0} & I_5 \end{array} \right)}_{J_1} \times \mathbf{S}_0[1] = (1 \ 1 \ 1 \ 1 \ 0 \ 0 \ 1)^t,$$

with $\mathbf{S}_0[1]$ the column 1 of the matrix $\mathbf{S}_0$.

The result of this system corresponds to the vector $(1, 0, 1, 1, 1, 1, 0)$.
Let us focus on recovering the two first columns of the syndrome matrix. The recovered masks vector of the first loop (1, 1, 1, 1, 0, 0, 0) provides the additions on the pivot row 0:

$$J_0 \times \mathbf{S} = \left( \frac{\begin{smallmatrix} 1 & 1 & 1 & 0 & 0 & 0 \end{smallmatrix}}{\mathbf{0}} \right) \times \mathbf{S}[0] = \left( \begin{array}{c} s_{0,0} + s_{1,0} + s_{2,0} + s_{3,0} \\ s_{1,0} \\ s_{2,0} \\ s_{3,0} \\ s_{4,0} \\ s_{5,0} \\ s_{6,0} \end{array} \right).$$

The masks vector of the second loop $\sigma'_0 = (1, 0, 0, 0, 1, 1, 1)$ is the solution vector of the system of linear equations where $s_{i,j}$ are unknowns. Thus, by applying a SageMath linear solver on the system

$$J_0 \times \mathbf{S}[0] = (1 \ 0 \ 0 \ 0 \ 1 \ 1 \ 1)^t,$$

we find the solution $(1, 0, 0, 0, 1, 1, 1)$, which corresponds to the first column of the syndrome matrix. SageMath is available at https://www.sagemath.org/. At the end of the process of the first column, we have the matrix

$$\mathbf{S}_0 = \left( \begin{array}{c|c} (\sigma'_0)^t & \mathbf{0} \\ \hline \mathbf{0} & I_6 \end{array} \right) \times J_0 \times \mathbf{S}.$$

For the second column, the recovered masks vector of the first loop is $(1, 0, 1, 0, 1, 1, 0)$. However, as explained in Section 3.1, only the rows for which the index row is greater than the index pivot row are added to the pivot row. Thus, in the recovered masks vector, we replace one by zero for $i < 1$. This gives us the vector $\sigma_1 = (0, 0, 1, 0, 1, 1, 0)$. In addition, the masks vector of the second loop is $\sigma'_1 = (1, 1, 1, 1, 0, 0, 1)$. We can then apply a SageMath linear solver on the system

$$\underbrace{\left( \begin{array}{c|c} 1 & 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \\ \hline 0 & 1 \ 1 \ 0 \ 1 \ 1 \ 0 \ 0 \end{array} \right)}_{J_1} \times \mathbf{S}_0[1] = (1 \ 1 \ 1 \ 1 \ 0 \ 0 \ 1)^t,$$

with $\mathbf{S}_0[1]$ the column 1 of the matrix $\mathbf{S}_0$.

The result of this system corresponds to the vector $(1, 0, 1, 1, 1, 1, 0)$.
At the end, we have the matrix

$$ \mathbf{S}_1 = \left( \begin{array}{c|c} 1 & \mathbf{0} \\ \mathbf{0} & I_5 \end{array} \right)^t \times J_1 \times \mathbf{S}_0. $$

We perform the same for the three remaining columns.

## References

[1] Aguilar-Melchor C, Aragon N, Bardet M, et al (2019) ROLLO-Rank-Ouroboros, LAKE & LOCKER. URL https://pqc-rollo.org/

[2] Aguilar-Melchor C, Aragon N, Bellini E, et al (2020) Constant time algorithms for ROLLO-I-128. https://eprint.iacr.org/2020/1066.pdf, source code available at https://github.com/peacker/constant_time_rollo.git

[3] Aragon N, Bidoux L (2020) rbc_library. https://rbc-lib.org/

[4] Aragon N, Gaborit P (2019) A key recovery attack against LRPC using decryption failures. In: International Workshop on Coding and Cryptography (WCC), Saint-Jacut-de-la-Mer, France

[5] Bardet M, Briaud P, Bros M, et al (2020) An algebraic attack on rank metric code-based cryptosystems. In: Canteaut A, Ishai Y (eds) Advances in Cryptology – EUROCRYPT 2020. Springer International Publishing, Cham, pp 64–93

[6] Bardet M, Bros M, Cabarcas D, et al (2020) Improvements of algebraic attacks for solving the rank decoding and minrank problems. In: Moriai S, Wang H (eds) Advances in Cryptology – ASIACRYPT 2020. Springer International Publishing, Cham, pp 507–536

[7] Bernstein DJ, Chou T, Schwabe P (2013) McBits: Fast constant-time code-based cryptography. In: Bertoni G, Coron JS (eds) Cryptographic Hardware and Embedded Systems (CHES). Springer Berlin Heidelberg, Berlin, Heidelberg, pp 250–272

[8] Cayrel PL, Colombier B, Drăgoi VF, et al (2021) Message-recovery laser fault injection attack on the classic mceliece cryptosystem. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, pp 438–467

[9] Gaborit P, Murat G, Ruatta O, et al (2013) Low Rank Parity Check codes and their application to cryptography. In: Budaghyan L, Helleseth
At the end, we have the matrix

$$ \mathbf{S}_1 = \left( \begin{array}{c|c} 1 & \mathbf{0} \\ \mathbf{0} & I_5 \end{array} \right)^t \times J_1 \times \mathbf{S}_0. $$

We perform the same for the three remaining columns.

## References

[1] Aguilar-Melchor C, Aragon N, Bardet M, et al (2019) ROLLO-Rank-Ouroboros, LAKE & LOCKER. URL https://pqc-rollo.org/

[2] Aguilar-Melchor C, Aragon N, Bellini E, et al (2020) Constant time algorithms for ROLLO-I-128. https://eprint.iacr.org/2020/1066.pdf, source code available at https://github.com/peacker/constant_time_rollo.git

[3] Aragon N, Bidoux L (2020) rbc_library. https://rbc-lib.org/

[4] Aragon N, Gaborit P (2019) A key recovery attack against LRPC using decryption failures. In: International Workshop on Coding and Cryptography (WCC), Saint-Jacut-de-la-Mer, France

[5] Bardet M, Briaud P, Bros M, et al (2020) An algebraic attack on rank metric code-based cryptosystems. In: Canteaut A, Ishai Y (eds) Advances in Cryptology – EUROCRYPT 2020. Springer International Publishing, Cham, pp 64–93

[6] Bardet M, Bros M, Cabarcas D, et al (2020) Improvements of algebraic attacks for solving the rank decoding and minrank problems. In: Moriai S, Wang H (eds) Advances in Cryptology – ASIACRYPT 2020. Springer International Publishing, Cham, pp 507–536

[7] Bernstein DJ, Chou T, Schwabe P (2013) McBits: Fast constant-time code-based cryptography. In: Bertoni G, Coron JS (eds) Cryptographic Hardware and Embedded Systems (CHES). Springer Berlin Heidelberg, Berlin, Heidelberg, pp 250–272

[8] Cayrel PL, Colombier B, Drăgoi VF, et al (2021) Message-recovery laser fault injection attack on the classic mceliece cryptosystem. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, pp 438–467

[9] Gaborit P, Murat G, Ruatta O, et al (2013) Low Rank Parity Check codes and their application to cryptography. In: Budaghyan L, Helleseth
T, Parker MG (eds) International Workshop on Coding and Cryptography (WCC), Bergen, Norway, URL https://hal.archives-ouvertes.fr/ hal-00913719, iISBN 978-82-308-2269-2

[10] Hoffstein J, Pipher J, Silverman JH (1998) NTRU: A ring-based public key cryptosystem. Proceedings of the Third International Symposium on Algorithmic Number Theory pp 267–288

[11] Johnson D, Menezes A, Vanstone S (2001) The Elliptic Curve Digital Signature Algorithm (ECDSA). International Journal of Information Security 1(1):36–63. https://doi.org/10.1007/s102070100002

[12] Kocher PC (1996) Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz N (ed) Advances in Cryptology – CRYPTO. Springer Berlin Heidelberg, Berlin, Heidelberg, pp 104–113

[13] Lahr N, Niederhagen R, Petri R, et al (2020) Side channel information set decoding using iterative chunking. In: Moriai S, Wang H (eds) Advances in Cryptology – ASIACRYPT 2020. Springer International Publishing, Cham, pp 881–910

[14] McEliece RJ (1978) A public-key cryptosystem based on algebraic coding theory. Tech. Rep. 44, California Inst. Technol., Pasadena, CA

[15] Melchor CA, Aragon N, Bettaieb S, et al (2020) Rank Quasi-Cyclic (RQC). https://pqc-rqc.org/

[16] Moody D, Alagic G, Apon DC, et al (2020) Status report on the second round of the NIST post-quantum cryptography standardization process. Tech. rep., https://doi.org/10.6028/nist.ir.8309

[17] Rivest RL, Shamir A, Adleman L (1978) A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21(2):120–126

[18] Samardjiska S, Santini P, Persichetti E, et al (2019) A reaction attack against cryptosystems based on LRPC codes. In: Progress in Cryptology – LATINCRYPT. Springer International Publishing, p 197–216, https://doi.org/10.1007/978-3-030-30530-7_10

[19] Shor PW (1997) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26(5):1484–1509

[20] Strenzke F, Tews E, Molter HG, et al (2008) Side channels in the McEliece PKC. In: International Workshop on Post-Quantum Cryptography, Springer, pp 216–229
T, Parker MG (eds) International Workshop on Coding and Cryptography (WCC), Bergen, Norway, URL https://hal.archives-ouvertes.fr/hal-00913719, iISBN 978-82-308-2269-2

[10] Hoffstein J, Pipher J, Silverman JH (1998) NTRU: A ring-based public key cryptosystem. Proceedings of the Third International Symposium on Algorithmic Number Theory pp 267–288

[11] Johnson D, Menezes A, Vanstone S (2001) The Elliptic Curve Digital Signature Algorithm (ECDSA). International Journal of Information Security 1(1):36–63. https://doi.org/10.1007/s102070100002

[12] Kocher PC (1996) Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz N (ed) Advances in Cryptology – CRYPTO. Springer Berlin Heidelberg, Berlin, Heidelberg, pp 104–113

[13] Lahr N, Niederhagen R, Petri R, et al (2020) Side channel information set decoding using iterative chunking. In: Moriai S, Wang H (eds) Advances in Cryptology – ASIACRYPT 2020. Springer International Publishing, Cham, pp 881–910

[14] McEliece RJ (1978) A public-key cryptosystem based on algebraic coding theory. Tech. Rep. 44, California Inst. Technol., Pasadena, CA

[15] Melchor CA, Aragon N, Bettaieb S, et al (2020) Rank Quasi-Cyclic (RQC). https://pqc-rqc.org/

[16] Moody D, Alagic G, Apon DC, et al (2020) Status report on the second round of the NIST post-quantum cryptography standardization process. Tech. rep., https://doi.org/10.6028/nist.ir.8309

[17] Rivest RL, Shamir A, Adleman L (1978) A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21(2):120–126

[18] Samardjiska S, Santini P, Persichetti E, et al (2019) A reaction attack against cryptosystems based on LRPC codes. In: Progress in Cryptology – LATINCRYPT. Springer International Publishing, p 197–216, https://doi.org/10.1007/978-3-030-30530-7_10

[19] Shor PW (1997) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26(5):1484–1509

[20] Strenzke F, Tews E, Molter HG, et al (2008) Side channels in the McEliece PKC. In: International Workshop on Post-Quantum Cryptography, Springer, pp 216–229