ROLLO

Carlos Aguilar Melchor, Nicolas Aragon, Magali Bardet, Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Adrien Hauteville, Ayoub Otmani, et al.

► To cite this version:

Carlos Aguilar Melchor, Nicolas Aragon, Magali Bardet, Slim Bettaieb, Loïc Bidoux, et al. ROLLO. 2020. hal-04278611

HAL Id: hal-04278611

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

Submitted on 10 Nov 2023

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

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

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

Distributed under a Creative Commons CC0 1.0 - Universal - International License
ROLLO -
Rank-Ouroboros, LAKE
& LOCKER

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

April 21, 2020

ROLLO is a compilation of three candidates to NIST's competition for post-quantum cryptography standardization. They are based on rank metric codes and they share the same decryption algorithm for LRPC codes (see Sec. 1).

Rank-Ouroboros (formerly known as Ouroboros-R) and LAKE are IND-CPA KEM running in the category “post-quantum key exchange”. LOCKER is an IND-CCA2 PKE running in the category “post-quantum public key encryption”. Different sets of parameters for these three cryptosystems are proposed for security strength categories 1, 3, and 5.

For clarification reasons, we have chosen to uniformize the name of our protocols. In the following document,

* LAKE is renamed ROLLO-I,

* LOCKER is renamed ROLLO-II,

* Rank-Ouroboros is renamed ROLLO-III.

*(not considered anymore in April 2020 update)*

**Principal Submitters (by alphabetical order):**

* Carlos AGUILAR MELCHOR

* Nicolas ARAGON

* Magali BARDET

* Slim BETTAIEB

* Loïc BIDOUX

* Olivier BLAZY

* Jean-Christophe DENEUVILLE

* Philippe GABORIT

* Adrien HAUTEVILLE

* Ayoub OTMANI

* Olivier RUATTA

* Jean-Pierre TILLICH

* Gilles ZÉMOR

**Inventors:** Same as submitters

**Developers:** Same as submitters
**Owners:** Same as submitters

The PhD of Nicolas Aragon was partially funded by French DGA.

**Main contact**

Philippe GABORIT

philippe.gaborit@unilim.fr

+33-626-907-245

University of Limoges

123 avenue Albert Thomas
87 060 Limoges Cedex
France

**Backup point of contact**

Adrien HAUTEVILLE

adrien.hauteville@inria.fr

+33-642-709-282

INRIA Saclay

1 rue Honoré d'Estienne d'Orves
Bâtiment Alan Turing
Campus de l'École Polytechnique
91120 Palaiseau
France
# 1 History of updates on ROLLO

## 1.1 Updates for April 22nd, 2020

* For sake of simplicity we now only consider the ROLLO-I and ROLLO-II schemes. These two schemes correspond to two versions of a unique protocol with adapted parameters depending on the expected DFR. ROLLO-I has small public keys when ROLLO-II has larger ones but a smaller DFR.

* New results on algebraic attacks for rank metric [4, 5] now provide a clear and better understanding of algebraic attacks against the rank syndrome decoding problem. As a consequence, we have updated our parameters in order to resist these attacks. The new parameters are presented in section 2.7. Roughly speaking the size of the key has increased by a factor of order 40% and our parameters remain attractive. For instance the size of the public key for ROLLO-I-128 is now 696 Bytes.

* In order to keep small parameters, we modified the decoding algorithm. We now consider in Section 2.4 the original LRPC decoder rather than its optimization. This simpler decoder permits to decode with smaller values of $m$ (the degree of the field extension) than the optimized decoder, and having a smaller $m$ permits to have a better resistance to algebraic attacks of [4, 5].

* We provide an implementation of the decoding algorithm implemented in a constant-time way whenever relevant and which should not leak any sensitive information with respect to timing attacks.

* We provide an optimized implementation leveraging AVX and CLMUL instructions.

* Our implementations no longer rely on third party libraries for finite field arithmetic.

* For 128 bits of security, we obtain the following sizes (in bytes) and performances (in kilocycles) for ROLLO-I:

<table><thead><tr><td>Public Key</td><td>Ciphertext</td><td>KeyGen</td><td>Encaps</td><td>Decaps</td><td>Log<sub>2</sub>(DFR)</td></tr></thead><tbody><tr><td>696</td><td>696</td><td>939</td><td>113</td><td>686</td><td>-28</td></tr></tbody></table>
1.2 Updates between Round 1 and Round 2

* The authors of ROLLO are the authors of LAKE, LOCKER and Ouroboros-R, plus Magali BARDET and Ayoub OTMANI.

* The names of the submissions have changed. LAKE becomes ROLLO-I, LOCKER becomes ROLLO-II and Ouroboros-R becomes ROLLO-III.

* ROLLO-III uses ideal codes instead of quasi-cyclic codes for Ouroboros-R.

* We have updated the parameters of the schemes such that the weight of the error, which is the most important parameter for the security, increases at each level of security. In practice it leads to a small increase of parameters. Concerning ROLLO-II, we have only kept the sets of parameters with a Decryption Failure Rate (DFR) inferior to $2^{-128}$.

* We have reorganized the specifications for clarifications.

* We have added a description of the quantum speed-up in the section Known Attacks.
# Contents

<table><tbody><tr><td>1</td><td>History of updates on ROLLO</td><td>3</td></tr><tr><td>1.1</td><td>Updates for April 22nd, 2020</td><td>3</td></tr><tr><td>1.2</td><td>Updates between Round 1 and Round 2</td><td>4</td></tr><tr><td>2</td><td>Specifications</td><td>7</td></tr><tr><td>2.1</td><td>Presentation of rank metric codes</td><td>9</td></tr><tr><td>2.1.1</td><td>General definitions</td><td>9</td></tr><tr><td>2.1.2</td><td>Ideal codes</td><td>10</td></tr><tr><td>2.2</td><td>Difficult problems in rank metric</td><td>11</td></tr><tr><td>2.3</td><td>The Low Rank Parity Check codes</td><td>13</td></tr><tr><td>2.4</td><td>A support recovery algorithm</td><td>14</td></tr><tr><td>2.4.1</td><td>Algorithm</td><td>15</td></tr><tr><td>2.4.2</td><td>Probability of failure</td><td>15</td></tr><tr><td>2.5</td><td>Presentation of the schemes</td><td>17</td></tr><tr><td>2.5.1</td><td>ROLLO-I as a KEM</td><td>17</td></tr><tr><td>2.5.2</td><td>ROLLO-II as a PKE</td><td>18</td></tr><tr><td>2.6</td><td>Representation of objects</td><td>18</td></tr><tr><td>2.6.1</td><td>Parsing vectors from/to byte strings</td><td>19</td></tr><tr><td>2.7</td><td>Parameters for our schemes</td><td>19</td></tr><tr><td>2.7.1</td><td>General remarks</td><td>19</td></tr><tr><td>2.7.2</td><td>ROLLO-I</td><td>20</td></tr><tr><td>2.7.3</td><td>ROLLO-II</td><td>20</td></tr><tr><td>3</td><td>Performances</td><td>21</td></tr><tr><td>3.1</td><td>ROLLO-I</td><td>22</td></tr><tr><td>3.2</td><td>ROLLO-II</td><td>22</td></tr><tr><td>3.3</td><td>Constant time Implementation</td><td>23</td></tr><tr><td>4</td><td>Known Answer Test Values</td><td>23</td></tr><tr><td>5</td><td>Security</td><td>24</td></tr><tr><td>5.1</td><td>Security Models and Hybrid Argument</td><td>24</td></tr><tr><td>5.2</td><td>IND-CPA security proof of ROLLO-I</td><td>25</td></tr><tr><td>5.3</td><td>IND-CCA2 security proof of ROLLO-II</td><td>25</td></tr><tr><td>5.3.1</td><td>IND-CPA security proof of the ROLLO-II PKE</td><td>25</td></tr><tr><td>5.3.2</td><td>A IND-CCA2 conversion of the ROLLO-II PKE</td><td>26</td></tr><tr><td>6</td><td>Known Attacks</td><td>27</td></tr><tr><td>6.1</td><td>Attack on the IRSD problem</td><td>28</td></tr><tr><td>6.2</td><td>Structural attack on ideal LRPC codes</td><td>28</td></tr><tr><td>6.3</td><td>Algebraic attacks</td><td>29</td></tr></tbody></table>
<table><tr><td>6.4 Quantum speed-up</td><td>30</td></tr><tr><td>7 Advantages and Limitations</td><td>31</td></tr><tr><td>7.1 Strengths</td><td>31</td></tr><tr><td>7.2 Limitations</td><td>31</td></tr><tr><td>References</td><td>31</td></tr></table>
## Prologue

The public key encryption protocol NTRU [14] was introduced in 1998, the main idea behind the protocol is that the secret key consists in the knowledge of a small Euclidean weight vector, which is used to derive a double circulant matrix. This matrix is then seen as a dual matrix of an associated lattice and a specific decoding algorithm based on the knowledge of this small weight dual matrix is used for decryption.

This idea of having as a trapdoor a small weight dual matrix (with a specific associated decoding algorithm) can naturally be generalized to other metrics. It was done in 2013 with MDPC [17] for Hamming metric and also in 2013 for Rank metric with LRPC codes [8]. These three protocols derive from the same basic main idea, adapted for different metrics, which have different properties in terms of efficiency, size of parameters and security reduction.

The previous schemes have many nice features in terms of size of keys, size of exchanged data and efficiency but suffer from the same weakness: their security do not reduce to a well known problem but rather to a specific problem where a special structure is hidden in the public matrix. Indeed the public matrix is generated by small weight vectors. Although this problem is less specific than hidden structure in the McEliece setting, it remains a potential weakness for these schemes (even if practically, one does not really know how to use this type of structure for strongly more efficient attacks in the more general cases).

Recently a new approach called Ouroboros was presented in [1], this approach permits to benefit from the nice features of the previous schemes, but at the same time has a reduction to decoding random quasi-cyclic codes, rather than a more specific code. Of course this comes at a cost: doubling the size of the ciphertext. ROLLO-I follows the idea of [1] for rank metric. The resulting scheme benefits from the nice features of NTRU-like schemes but has also a reduction to a generic problem, at the cost of doubling the size of the ciphertext, also as all associated decoding algorithm for the NTRU-like family of schemes, there is a decryption failure, but in the case of rank metric this decryption failure is low and perfectly estimated.

This proposal is the fusion of three propositions to standardization for the post-quantum cryptography NIST competition: LAKE, LOCKER and Rank Ouroboros (formerly Ouroboros-R). For uniformity reasons, they have been renamed ROLLO-I, ROLLO-II and ROLLO-III respectively.

In the present for sake of simplicity we chose to concentrate on ROLLO-I and ROLLO-II.

## 2 Specifications

In the following document, $q$ denotes a power of a prime $p$. The finite field with $q$ elements is denoted by $\mathbb{F}_q$ and more generally for any positive integer $m$ the finite field with $q^m$ elements is denoted by $\mathbb{F}_{q^m}$. We will frequently view $\mathbb{F}_{q^m}$ as an $m$-dimensional vector space over $\mathbb{F}_q$.
We use bold lowercase (resp. uppercase) letters to denote vectors (resp. matrices).

Let $P \in \mathbb{F}_q[X]$ a polynomial of degree $n$. We can identify the vector space $\mathbb{F}_{q^m}^n$ with the ring $\mathbb{F}_{q^m}[X]/\langle P \rangle$, where $\langle P \rangle$ denotes the ideal of $\mathbb{F}_{q^m}[X]$ generated by $P$.

$$ \Psi: \quad \mathbb{F}_{q^m}^n \quad \approx \mathbb{F}_{q^m}[X]/\langle P \rangle \\ (v_0, \dots, v_{n-1}) \mapsto \sum_{i=0}^{n-1} v_i X^i $$

For $u, v \in \mathbb{F}_{q^m}^n$, we define their product similarly as in $\mathbb{F}_{q^m}[X]/\langle P \rangle$: $w = uv \in \mathbb{F}_{q^m}^n$ is the only vector such that $\Psi(w) = \Psi(u)\Psi(v)$. In order to lighten the formula, we will omit the symbol $\Psi$ in the future.

To a vector $v \in \mathbb{F}_{q^m}^n$ we can associate an $n \times n$ square matrix corresponding to the product by $v$. Indeed,

$$ \begin{aligned} uv &= u(X)v(X) \quad (\text{mod } P) \\ &= \sum_{i=0}^{n-1} u_i X^i v(X) \quad (\text{mod } P) \\ &= \sum_{i=0}^{n-1} u_i (X^i v(X) \quad \text{mod } P) \\ &= (u_0, \dots, u_{n-1}) \begin{pmatrix} v(X) & \text{mod } P \\ Xv(X) & \text{mod } P \\ \vdots & \\ X^{n-1}v(X) & \text{mod } P \end{pmatrix} \end{aligned} $$

Such a matrix is called the ideal matrix generated by $v$ and $P$, or simply by $v$ when there is no ambiguity in the choice of $P$.

**Definition 2.0.1** (Ideal Matrix). Let $P \in \mathbb{F}_q[X]$ a polynomial of degree $n$ and $v \in \mathbb{F}_{q^m}^n$. The ideal matrix generated $v$ is the $n \times n$ square matrix denoted $\mathcal{IM}(v)$ of the form:

$$ \mathcal{IM}(v) = \begin{pmatrix} v \\ Xv \mod P \\ \vdots \\ X^{n-1}v \mod P \end{pmatrix} $$

As a consequence, the product of two elements of $\mathbb{F}_{q^m}[X]/\langle P \rangle$ is equivalent to the usual product vector-matrix:

$$ uv = u\mathcal{IM}(v) = \mathcal{IM}(u)^T v = vu. $$

Let $S$ be a finite set. $x \stackrel{\$}{\leftarrow} S$ means that $x$ is an element of $S$, chosen uniformly at random.
## 2.1 Presentation of rank metric codes

### 2.1.1 General definitions

**Definition 2.1.1 (Rank metric over $\mathbb{F}_{q^m}^n$).** Let $\mathbf{x} = (x_1, \dots, x_n) \in \mathbb{F}_{q^m}^n$ and $(\beta_1, \dots, \beta_m) \in \mathbb{F}_{q^m}^m$ a basis of $\mathbb{F}_{q^m}$ viewed as an $m$-dimensional vector space over $\mathbb{F}_q$. Each coordinate $x_j$ is associated to a vector of $\mathbb{F}_q^m$ in this basis: $x_j = \sum_{i=1}^m x_{ij}\beta_i$. The $m \times n$ matrix associated to $\mathbf{x}$ is given by $\mathbf{M}(\mathbf{x}) = (x_{ij})_{\substack{1 \le i \le m \\ 1 \le j \le n}}$.

The rank weight $\|\mathbf{x}\|$ of $\mathbf{x}$ is defined as

$$ \|\mathbf{x}\| \stackrel{\text{def}}{=} \text{Rank } \mathbf{M}(\mathbf{x}). $$

The associated distance $d(\mathbf{x}, \mathbf{y})$ between elements $\mathbf{x}$ and $\mathbf{y}$ in $\mathbb{F}_{q^m}^n$ is defined by $d(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\|$.

**Definition 2.1.2 (($\mathbb{F}_{q^m}$-linear code).** An $\mathbb{F}_{q^m}$-linear code $C$ of dimension $k$ and length $n$ is a subspace of dimension $k$ of $\mathbb{F}_{q^m}^n$ embedded with the rank metric. It is denoted $[n, k]_{q^m}$.

$C$ can be represented by two equivalent ways:

* by a generator matrix $\mathbf{G} \in \mathbb{F}_{q^m}^{k \times n}$. Each row of $\mathbf{G}$ is an element of a basis of $C$,

$$ C = \{\mathbf{x}\mathbf{G}, \mathbf{x} \in \mathbb{F}_{q^m}^k\} $$

* by a parity-check matrix $\mathbf{H} \in \mathbb{F}_{q^m}^{(n-k) \times n}$. Each row of $\mathbf{H}$ determines a parity-check equation verified by the elements of $C$:

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

$\mathbf{H}\mathbf{v}^T$ is called the syndrome of $\mathbf{v}$ (with respect to $\mathbf{H}$).

We say that $\mathbf{G}$ (respectively $\mathbf{H}$) is under systematic form if and only if it is of the form $(\mathbf{I}_k|\mathbf{A})$ (respectively $(\mathbf{I}_{n-k}|\mathbf{B})$).

**Definition 2.1.3 (Support of a word).** Let $\mathbf{x} = (x_1, \dots, x_n) \in \mathbb{F}_{q^m}^n$. The support $E$ of $\mathbf{x}$, denoted $\text{Supp}(\mathbf{x})$, is the $\mathbb{F}_q$-subspace of $\mathbb{F}_{q^m}$ generated by the coordinates of $\mathbf{x}$:

$$ E = \langle x_1, \dots, x_n \rangle_{\mathbb{F}_q} $$

and we have $\dim E = \|\mathbf{x}\|$.

The number of supports of dimension $w$ of $\mathbb{F}_{q^m}$ is denoted by the Gaussian coefficient

$$ \begin{bmatrix} m \\ w \end{bmatrix}_q = \prod_{i=0}^{w-1} \frac{q^m - q^i}{q^w - q^i}. $$
### 2.1.2 Ideal codes

One of the difficulty with code-based cryptography is the size of the key. Indeed, to represent an $[n, k]_{q^m}$ code with a systematic matrix, we need $k(n-k)$ symbols in $\mathbb{F}_{q^m}$, or $k(n-k) \lfloor \log q \rfloor$ bits. In order to reduce the size of the representation of a code, we introduce the family of ideal codes, which are basically codes with a systematic generator matrix formed with blocks of ideal matrices. More formally,

**Definition 2.1.4 (Ideal codes).** Let $P(X) \in \mathbb{F}_q[X]$ be a polynomial of degree $n$. An $[ns, nt]_{q^m}$ code $C$ is an $(s, t)$-ideal code if its generator matrix under systematic form is of the form

$$ G = \left( \begin{array}{c} \mathcal{IM}(g_{1,1}) \quad \dots \quad \mathcal{IM}(g_{1,s-t}) \\ I_{tn} \\ \vdots \quad \ddots \quad \vdots \\ \mathcal{IM}(g_{t,1}) \quad \dots \quad \mathcal{IM}(g_{t,s-t}) \end{array} \right) $$

where $(g_{i,j})_{i \in [1..s-t], j \in [1..t]}$ are vectors of $\mathbb{F}_{q^m}^n$. In this case, we said that $C$ is generated by the $(g_{i,j})$.

It would be somewhat more natural to choose the generator matrix to be made up of $s \times t$ ideal matrices, rather than to require the code to admit a systematic generator matrix. However, if $m$ and $n$ are two different prime numbers and if $P$ is irreducible, a nonzero ideal matrix is always non-singular. To prove this, we need the following lemma:

**Lemma 1.** Let $m$ and $n$ be two different prime numbers. Let $P \in \mathbb{F}_q[X]$ be an irreducible polynomial of degree $n$ and $U \in \mathbb{F}_{q^m}[X]$ a non zero polynomial of degree at most $n-1$. Then $P$ and $U$ are co-prime in $\mathbb{F}_{q^m}[X]$.

*Proof.* We will show that $P$ and $U$ have no common root. Let $\mathcal{Z}(P)$ (respectively $\mathcal{Z}(U)$) be the set of the roots of $P$ (respectively $U$).

Since $P$ is irreducible of degree $n$, its roots generate $\mathbb{F}_{q^n}$

$$ \implies \mathcal{Z}(P) \subset \mathbb{F}_{q^n} \setminus \mathbb{F}_q $$

Since $U$ is of degree at most $n$, its roots belong to $\mathbb{F}_{q^{m(n-1)!}}$.

But $\text{GCD}(n, m(n-1)!) = 1$ for $m$ and $n$ are two different prime numbers. Thus

$$ \mathbb{F}_{q^{m(n-1)!}} \cap \mathbb{F}_{q^n} = \mathbb{F}_q \implies \mathcal{Z}(P) \cap \mathcal{Z}(U) = \emptyset $$

Hence, $P$ and $U$ are co-prime.

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

Now, let $u \in \mathbb{F}_{q^m}^n$ a non zero vector and $P \in \mathbb{F}_q[X]$ an irreducible polynomial of degree $n$. According to the lemma, there exist a vector $v \in \mathbb{F}_{q^m}^n$ such that

$$ uv = 1 \pmod{P} $$

$$ \iff u \mathcal{IM}(v) = (1, 0, \dots, 0) $$

$$ \iff \mathcal{IM}(u)\mathcal{IM}(v) = I_n $$
This demonstrates that every block of ideal matrix of $G$ is non-singular, hence $C$ can be represented under systematic form. $\square$

All the parameters we propose in Section 2.7 verify these conditions.

**Remark 2.1.** With this definition, the ideal codes can be seen as a generalization of Quasi-Cyclic codes. Indeed, the generator matrix under systematic form of a Quasi-Cyclic code [6] is of the same form, except that the ideal matrices are replaced by circulant matrices. Yet, an $n \times n$ circulant matrix can be seen as an element of $\mathbb{F}_{q^m}[X]/\langle X^n - 1 \rangle$. Thus ideal codes only differ from Quasi-Cyclic codes by the choice of the polynomial $P$.

In our scheme, we only use $[ns, n]_{q^m}$ ideal codes. In order to shorten the notation, we denote these codes an $s$-ideal code. If $C$ is an $[sn, n]$ ideal code generated by $(g_1, \dots, g_{s-1})$, we have $C = \{(u, ug_1, \dots, ug_{s-1}), u \in \mathbb{F}_{q^m}^n\}$.

We need to be careful when we use these notations in the case of parity-check matrix. Indeed, the parity-check matrix under systematic form of $C$ is of the form:

$$ H = \left( \begin{array}{c} \mathcal{IM}(h_1)^T \\ \mathbf{I}_{n(s-1)} \\ \vdots \\ \mathcal{IM}(h_{s-1})^T \end{array} \right). \qquad (1) $$

Thus, if $\boldsymbol{\sigma} = (\boldsymbol{\sigma}_1 \dots \boldsymbol{\sigma}_{s-1}) \in \mathbb{F}_{q^m}^{s(n-1)}$ is the syndrome of an error $\boldsymbol{e} = (e_1 \dots e_{s-1}) \in \mathbb{F}_{q^m}^{ns}$, the parity-check equations

$$ He^T = \boldsymbol{\sigma}^T $$

are equivalent to $e_i + h_i e_{s-1} = \boldsymbol{\sigma}_i$ for $1 \le i \le s-1$.

## 2.2 Difficult problems in rank metric

In this section, we describe difficult problems which can be used for cryptography and discuss their hardness. All problems are variants of the decoding problem, which consists of looking for the closest codeword to a given vector: when dealing with linear codes, it is readily seen that the decoding problem stays the same when one is given the syndrome of the received vector rather than the received vector. We therefore speak of (rank) Syndrome Decoding (RSD).

**Definition 2.2.1 (RSD Distribution).** For positive integers, $n, k$, and $w$, the RSD($n, k, w$) Distribution chooses $\mathbf{H} \stackrel{\$}{\leftarrow} \mathbb{F}_{q^m}^{(n-k) \times n}$ and $\mathbf{x} \stackrel{\$}{\leftarrow} \mathbb{F}_{q^m}^n$ such that $\|\mathbf{x}\| = w$, and outputs $(\mathbf{H}, \sigma(\mathbf{x}) = \mathbf{Hx}^\top)$.

**Definition 2.2.2 (Computational RSD Problem).** On input $(\mathbf{H}, \mathbf{y}^\top) \in \mathbb{F}_{q^m}^{(n-k) \times n} \times \mathbb{F}_{q^m}^{(n-k)}$ from the RSD distribution, the Computational Rank Syndrome Decoding Problem RSD($n, k, w$) asks to compute $\mathbf{x} \in \mathbb{F}_{q^m}^n$ such that $\mathbf{Hx}^\top = \mathbf{y}^\top$ and $\|\mathbf{x}\| = w$.
The RSD problem has recently been proven difficult with a probabilistic reduction to the Hamming setting in [11]. For cryptography we also need a decision version of the problem, which is given in the following definition.

**Definition 2.2.3 (Decision RSD Problem).** On input $(\mathbf{H}, \mathbf{y}^\top) \in \mathbb{F}_{q^m}^{(n-k)\times n} \times \mathbb{F}_{q^m}^{(n-k)}$, the Decision RSD Problem DRSD$(n, k, w)$ asks to decide with non-negligible advantage whether $(\mathbf{H}, \mathbf{y}^\top)$ came from the RSD$(n, k, w)$ distribution or the uniform distribution over $\mathbb{F}_{q^m}^{(n-k)\times n} \times \mathbb{F}_{q^m}^{(n-k)}$.

As our cryptosystem uses ideal codes, we explicitly define the problem on this setting. The following definitions describe the DRSD problem in the ideal configuration, and are just a combination of Definition 2.1.4 and 2.2.3. Ideal codes are very useful in cryptography since their compact description allows to decrease considerably the size of the keys.

**Definition 2.2.4 (s-IRSD Distribution).** Let $P \in \mathbb{F}_q[X]$ an irreducible polynomial of degree $n$. For positive integers $n, w$ and $s$, let $S(n, s)$ be the set of the parity-check matrices $\mathbf{H}$ under systematic form of s-ideal codes of type $[sn, n]$ (see Equation 1). The s-IRSD$(n, w)$ Distribution chooses uniformly at random a matrix $\mathbf{H} \stackrel{\$}{\leftarrow} S(n, s)$ together with a vector $\mathbf{x} = (\mathbf{x}_1, \dots, \mathbf{x}_s) \stackrel{\$}{\leftarrow} \mathbb{F}_{q^m}^{sn}$ such that $\|\mathbf{x}\| = w$ and outputs $(\mathbf{H}, \mathbf{H}\mathbf{x}^\top)$.

**Definition 2.2.5 (Computational s-IRSD Problem).** Let $P \in \mathbb{F}_q[X]$ an irreducible polynomial of degree $n$. For positive integers $n, w, s$, a random parity check matrix $\mathbf{H}$ under systematic form of an s-ideal code $C$ and $\mathbf{y} \stackrel{\$}{\leftarrow} \mathbb{F}_{q^m}^{sn-n}$, the Computational s-ideal RSD Problem s-IRSD$(n, w)$ asks to compute $\mathbf{x} = (\mathbf{x}_1, \dots, \mathbf{x}_s) \in \mathbb{F}_{q^m}^{sn}$ such that $\|\mathbf{x}\| = w$ and $\mathbf{y} = \mathbf{x}\mathbf{H}^\top$.

The problem has a decisional form:

**Definition 2.2.6 (Decision s-IRSD Problem).** Let $P \in \mathbb{F}_q[X]$ an irreducible polynomial of degree $n$. For positive integers $n, w$ and $s$, let $S(n, s)$ be the set of the parity-check matrices $\mathbf{H}$ under systematic form of s-ideal codes of type $[sn, n]$ (see Equation 1). The Decision s-Ideal RSD Problem s-IRSD$(n, w)$ asks to decide with non-negligible advantage whether $(\mathbf{H}, \mathbf{y}^\top)$ came from the s-IRSD$(n, w)$ distribution or the uniform distribution over $S(n, s) \times \mathbb{F}_{q^m}^{(sn-n)}$.

As for the ring-LPN problem, there is no known reduction from the search version of s-IRSD problem to its decision version. The proof of [2] cannot be directly adapted in the ideal case, however the best known attacks on the decision version of the problem s-IRSD remain the direct attacks on the search version of the problem s-IRSD.

Finally we need to introduce a last problem which is useful for the security proof of our schemes. (see Sections 5).

**Problem 2.2 (s-Ideal Rank Support Recovery).** Given a vector $\mathbf{h}_1, \dots, \mathbf{h}_{s-1} \in \mathbb{F}_{q^m}^n$, a polynomial $P \in \mathbb{F}_q[X]$ of degree $n$ and a syndrome $\boldsymbol{\sigma}$ and a weight $w$, it is hard to recover a support $E$ of dimension lower than $w$ such that $\mathbf{e}_0 + \mathbf{e}_1\mathbf{h}_1 + \dots \mathbf{e}_{s-1}\mathbf{h}_{s-1} = \boldsymbol{\sigma} \pmod{P}$ where the vectors $\mathbf{e}_i$ are of support $E$.
**Hardness of the problem:** We show that the s-IRSR problem and the s-IRSD problem are equivalent.

The s-IRSR problem is trivially reduced to the s-IRSD problem. Indeed to recover the support $E$ of an instance of the s-IRSR problem from a solution $\boldsymbol{x}$ of the s-IRSD problem, we just have to compute the support of $\boldsymbol{x}$.

Reciprocally, the s-IRSD problem can also be reduced to the s-IRSR problem. We prove this property for $s = 2$, the generalization is straightforward. Let us suppose we know the support $E$ of a solution of the 2-IRSR problem for a weight $w$. We want to find $\boldsymbol{x} = (\boldsymbol{x}_0, \boldsymbol{x}_1)$ of weight lower than $w$ such that $\boldsymbol{x}_0 + \boldsymbol{x}_1\boldsymbol{h} = \boldsymbol{\sigma}$ (mod $P$).

This equation is equivalent to

$$ \left( \mathbf{I}_n \quad \mathcal{IM}(\boldsymbol{h})^T \right) (x_{0,0} \dots x_{0,n-1}, x_{1,0} \dots x_{1,n-1})^T = \boldsymbol{\sigma}^T \quad (2) $$

where $\boldsymbol{x}_0 = (x_{1,0} \dots x_{0,n-1})$ and $\boldsymbol{x}_1 = (x_{1,0} \dots x_{1,n-1})$.

Let $(E_1, \dots, E_w)$ be a basis of $E$. We can express the coordinates of $\boldsymbol{x}_0$ and $\boldsymbol{x}_1$ in this basis:

$$ \forall i \in \{0, 1\}, 0 \le j \le n-1, x_{ij} = \sum_{k=1}^{w} \lambda_{ijk} E_k, \text{ with } \lambda_{ijk} \in \mathbb{F}_q $$

Then we rewrite the equations of (2) in the new unknowns $\lambda_{ijk}$. We obtain a system of $2nw$ unknowns over $\mathbb{F}_q$ and $n$ equations over $\mathbb{F}_{q^m}$, so $nm$ equations over $\mathbb{F}_q$.

Since $E$ is solution to the 2-IRSR problem, the system has at least one solution and by construction all the solutions have their support included in $E$ of dimension $w$, so we can find a solution to the 2-IRSD problem by solving this system.

The complexity of known attacks against these problems are described in Section 6.

## 2.3 The Low Rank Parity Check codes

The LRPC codes have been introduced in [8]. They are good candidates for the cryptosystem of McEliece because they have a weak algebraic structure.

**Definition 2.3.1 (LRPC codes).** Let $\mathbf{H} = (h_{ij})_{\substack{1 \le i \le n-k \\ 1 \le j \le n}} \in \mathbb{F}_{q^m}^{(n-k) \times n}$ a full-rank matrix such that its coefficients generate an $\mathbb{F}_q$-subspace $F$ of small dimension $d$:

$$ F = \langle h_{ij} \rangle_{\mathbb{F}_q} $$

Let $C$ be the code with parity-check matrix $\mathbf{H}$. By definition, $C$ is an $[n, k]_{q^m}$ LRPC code. Such a matrix $\mathbf{H}$ is called homogeneous matrix of weight $d$ and support $F$.

We can now define the ideal LRPC codes. As we will only use (2, 1)-ideal LRPC codes in our cryptosystems, we restraint the following definition to this type of codes, but the generalization is straightforward, such as we have done for ideal code.
**Definition 2.3.2 (Ideal LRPC codes).** Let $F$ be a $\mathbb{F}_q$-subspace of dimension $d$ of $\mathbb{F}_{q^m}$, $(\mathbf{h}_1, \mathbf{h}_2)$ two vectors of $\mathbb{F}_{q^m}$ of support $F$ and $P \in \mathbb{F}_q[X]$ a polynomial of degree $n$. Let

$$ \mathbf{H} = \left( \mathcal{IM}(\mathbf{h}_1)^T \quad \mathcal{IM}(\mathbf{h}_2)^T \right) $$

By definition, the code $\mathcal{C}$ with parity check matrix $\mathbf{H}$ is an ideal LRPC code of type $[2n, n]_{q^m}$.

As we can see, since $P \in \mathbb{F}_q[X]$, the support of $X^i\mathbf{h}_1$ is still $F$ for all $1 \le i \le n-1$ hence the necessity to choose $P$ with coefficients in the base field $\mathbb{F}_q$ to keep the LRPC structure of the ideal code.

To hide the structure of an ideal LRPC, we only reveal its systematic parity-check matrix.

**Problem 2.3 (Ideal LRPC codes indistinguishability).** Given a polynomial $P \in \mathbb{F}_q[X]$ of degree $n$ and a vector $\mathbf{h} \in \mathbb{F}_{q^m}$, it is hard to distinguish whether the ideal code $\mathcal{C}$ with the parity-check matrix generated by $\mathbf{h}$ and $P$ is a random ideal code or if it is an ideal LRPC code of weight $d$.

In other words, it is hard to distinguish if $\mathbf{h}$ was sampled uniformly at random or as $\mathbf{x}^{-1}\mathbf{y}$ mod $P$ where the vectors $\mathbf{x}$ and $\mathbf{y}$ have the same support of small dimension $d$.

The ideal LRPC codes are particularly interesting if we choose an irreducible polynomial for $P$. In this case we counter a structural attack against double circulant LRPC which can be found in [12].

## 2.4 A support recovery algorithm

**Notation 2.4.** Let $E$ be an $\mathbb{F}_q$-subspace of $\mathbb{F}_{q^m}$ of dimension $r$ and $F$ an $\mathbb{F}_q$-subspace of dimension $d$. We denote by $EF$ the subspace generated by the product of the elements of $E$ and $F$:

$$ EF = \langle \{ef, e \in E, f \in F\} \rangle $$

Let $(e_1, \dots, e_r)$ be basis of $E$ and $(f_1, \dots, f_d)$ a basis of $F$. It is clear that $(e_i f_j)_{\substack{1 \le i \le r \\ 1 \le j \le d}}$ is a generator family of $EF$. In the typical case $\dim EF = rd$ (see [8], Section 3 for more details on the probability). For the considered parameters, it can happen that $\dim EF < rd$, but this case is also covered by the decoding algorithm without any modification.

Let $\mathbf{H} \in \mathbb{F}_{q^m}^{2n \times n}$ be an homogeneous matrix of support $F$ and $\mathbf{e} \in \mathbb{F}_{q^m}^{2n}$ an error of support $E$. Let $\mathcal{C}$ be the LRPC code with parity-check matrix $\mathbf{H}$ and $\mathbf{s}$ be the syndrome of $\mathbf{e}$: $\mathbf{H}\mathbf{e}^T = \mathbf{s}^T$. In the following section $S$ denotes the support of $\mathbf{s}$, it is a subspace of $EF$ so its dimension is at most $rd$.

$S_i$ is defined by $S_i := f_i^{-1}S$.
### 2.4.1 Algorithm

The decoding algorithm of LRPC codes first recovers the support of the error vector then solves a linear system in order to recover the error coordinates. For these proposals, we only need to recover the support of the error. The algorithm we present here uses the general decoding algorithm of the LRPC codes described in [8] without the coordinates recovery part.

**Algorithm 1:** Rank Support Recover (RSR) algorithm

**Data:** $F = \langle f_1, ..., f_d \rangle$ an $\mathbb{F}_q$-subspace of $\mathbb{F}_{q^m}$, $\mathbf{s} = (s_1, ..., s_n) \in \mathbb{F}_{q^m}^n$ a syndrome of an error $\mathbf{e}$ of weight $r$ and of support $E$

**Result:** A candidate for the vector space $E$

//Part 1 : Compute the vector space $EF$

1. Compute $S = \langle s_1, ..., s_n \rangle$

//Part 2 : Recover the vector space $E$

2. $E \leftarrow \bigcap_{i=1}^{d} f_i^{-1} S$

3. Pre-compute every $S_i$ for $i = 1$ to $d$

4. return $E$

### 2.4.2 Probability of failure

First we remark that the previous decoding algorithm works even if the dimension of $EF$ is not maximal, this case happens scarcely and even in this case the intersection of the $S_i$ is still $E$.

In fact there are only two cases that can make the algorithm fail:

* $\dim S < \dim EF$

* $\dim \bigcap_{i=1}^{d} f_i^{-1} S > r$

We consider in the following the probability of these events.

**Proposition 2.4.1.** *The probability that $\dim S < \dim EF$ is:*

$$q^{-(n-rd+1)}$$

*Proof.* As in [8] we use the fact that since the error is chosen randomly, every $s_i$ can be seen as a random element of $EF$, hence the probability that a set of $n$ elements does not generate the whole vector space of dimension $rd$ (with $n > rd$) is given by the probability that a random $rd \times n$ matrix over $\mathbb{F}_q$ is not invertible, i.e $q^{n-rd+1}$. $\square$

For the second event $\dim \bigcap_{i=1}^{d} f_i^{-1} S > r$, we first prove the following result:
<table><caption>Table 1: Simulation results for proposition 2.4.2</caption><thead><tr><th>r</th><th>r</th><th>m</th><th>log<sub>2</sub>(failure) from 2.4.2</th><th>log<sub>2</sub>(failure) from simulations</th></tr></thead><tbody><tr><td>7</td><td>8</td><td>63</td><td>0</td><td>-0.50</td></tr><tr><td>7</td><td>8</td><td>64</td><td>-7</td><td>-7.01</td></tr><tr><td>7</td><td>8</td><td>65</td><td>-14</td><td>-14.07</td></tr><tr><td>7</td><td>8</td><td>66</td><td>-21</td><td>-20.91</td></tr><tr><td>7</td><td>8</td><td>67</td><td>-28</td><td>-28.19</td></tr></tbody></table>

**Proposition 2.4.2.** Let $V$ be the space $\mathbb{F}_{q^m}$ and let $r$ and $d$ be two integers. Let $E$ be a fixed subspace of dimension $r$ and let $R_i$, $1 \le i \le d$, be $d$ independently chosen random subspaces of dimension $rd$ containing the subspace $E$. The probability that $\dim \bigcap_{i=1}^d R_i > r$ is bounded from above by:

$$q^{rd-r} \left( \frac{q^{rd} - q^r}{q^m} \right)^{d-1} \approx q^{-(d-1)(m-rd-r)}.$$

*Proof.* It suffices to prove the proposition for $r=0$, since the general result will follow from the case $r=0$ by applying it to the quotient space $V/E$. Fix the first subspace $R_1$ and let $y \in R_1$, $y \ne 0$. The probability that $y \in R_i$ equals $(q^{rd} - 1)/q^m$, and by independence the probability that this occurs for all $i=2 \dots d$ is

$$\left( \frac{q^{rd} - q^r}{q^m} \right)^{d-1} . \qquad (3)$$

The expected number of non-zero vectors $y$ in the intersection of all the spaces $R_i$ is therefore $q^{rd} - 1$ times the quantity (3), hence the result, since the probability that such a vector $y$ exists is bounded from above by their expected number. $\square$

In practice, in our case the $R_i$ correspond to the $S_i$ and they are not random, but since $S_i = f_i^{-1}S$, we consider the effect of the multiplication by a $f_i^{-1}$ and we do the simplifying assumption that the $S_i$ behave as random spaces in term of intersection. This assumption is remarkably accurate when confronted with simulations as it is shown in Table 1. From here on we consider that the probability that $\dim \bigcap_{i=1}^d S_i > r$ can be approximated by $q^{-(d-1)(m-rd-r)}$ which fits very well all the simulations we have made.

From these two propositions we deduce the Decryption Failure Rate of the RSR algorithm:

**Proposition 2.4.3.** Under the assumption (validated by simulations) that for intersections the $S_i$ behave as random subspaces containing $E$, the Decryption Failure Rate of the RSR algorithm 1 can be approximated by:

$$q^{-(d-1)(m-rd-r)} + q^{-(n-rd+1)}$$
## 2.5 Presentation of the schemes

In this subsection, $S_w^n(\mathbb{F}_{q^m})$ stands for the set of vectors of length $n$ and rank weight $w$ over $\mathbb{F}_{q^m}$:

$$S_w^n(\mathbb{F}_{q^m}) = \{\boldsymbol{x} \in \mathbb{F}_{q^m}^n : \dim \mathrm{Supp}(\boldsymbol{x}) = w\}$$

### 2.5.1 ROLLO-I as a KEM

A Key-Encapsulation scheme KEM = (KeyGen, Encap, Decap) is a triple of probabilistic algorithms together with a key space $\mathcal{K}$. The key generation algorithm KeyGen generates a pair of public and secret key (pk, sk). The encapsulation algorithm Encap uses the public key pk to produce an encapsulation c, and a key $K \in \mathcal{K}$. Finally Decap using the secret key sk and an encapsulation c, recovers the key $K \in \mathcal{K}$ or fails and return $\perp$.

ROLLO-I is depicted in fig. 1, then formally described in fig. 2. The RSR algorithm was presented in previous section. P is a irreducible polynomial of $\mathbb{F}_q[X]$ of degree $n$ and constitutes a parameter of the cryptosystem.

<figure><img src="image_4.png" /><figcaption>Figure 1: Informal description of ROLLO-I. $h$ constitutes the public key.</figcaption></figure>

**Correctness:** Alice recovers $s = xc = xe_1 + xe_2h = xe_1 + ye_2 \mod P$, since $E = \mathrm{Supp}(e_1, e_2)$, $F = \mathrm{Supp}(x, y)$ and $P \in \mathbb{F}_q[X]$, the coordinates of $s$ generate a subspace of $EF$ on which Bob can apply the RSR algorithm to recover $E$.

<figure><img src="image_5.png" /><figcaption>Figure 2: Formal description of ROLLO-I.</figcaption></figure>

**Computational costs.** The costs are expressed in operations in the base field $\mathbb{F}_q$. The KeyGen cost corresponds to a polynomial modular inversion in $\mathbb{F}_{q^m}[X]/\langle P \rangle$, the Encap and
Decap costs correspond to a polynomial modular addition and a polynomial modular multiplication in $\mathbb{F}_{q^m}[X]/\langle P\rangle$, plus the decoding cost of the RSR algorithm for the decapsulation.

### 2.5.2 ROLLO-II as a PKE

A Public Key Encryption (PKE) scheme is defined by three algorithms: the key generation algorithm KeyGen which takes on input the security parameter $\lambda$ and outputs a pair of public and private keys ($pk, sk$); the encryption algorithm Encrypt($pk, M$) which outputs the ciphertext $C$ corresponding to the message $M$ and the decryption algorithm Decrypt($sk, C$) which outputs the plaintext $M$.

Since ROLLO-II is almost identical to ROLLO-I, we only give its formal description in fig. 3, the correctness and the computational costs are the same. $P$ is an irreducible polynomial of $\mathbb{F}_q[X]$ of degree $n$ and constitutes a parameter of the cryptosystem. The symbol $\oplus$ denotes here the bitwise XOR.

* KeyGen($1^{\lambda}$): Picks $(\mathbf{x}, \mathbf{y}) \stackrel{\$}{\leftarrow} S_d^{2n}(\mathbb{F}_{q^m})$. Sets $\mathbf{h} = \mathbf{x}^{-1}\mathbf{y}$ mod $P$ and return $pk = \mathbf{h}, sk = (\mathbf{x}, \mathbf{y})$.

* Encrypt($M, pk$): Picks $(e_1, e_2) \stackrel{\$}{\leftarrow} S_r^{2n}(\mathbb{F}_{q^m})$, sets $E = \text{Supp}(e_1, e_2)$, $c = e_1 + e_2\mathbf{h}$ mod $P$. Computes $\text{cipher} = M \oplus \text{Hash}(E)$ and returns the ciphertext $C = (c, \text{cipher})$.

* Decrypt($C, sk$): Sets $\mathbf{s} = \mathbf{x}\mathbf{c}$ mod $P$, $F = \text{Supp}(\mathbf{x}, \mathbf{y})$ and $E \leftarrow \text{RSR}(F, \mathbf{s}, r)$. Return $M = \text{cipher} \oplus \text{Hash}(E)$.

<caption>Figure 3: Formal description of ROLLO-II.</caption>

## 2.6 Representation of objects

**Field elements.** Elements of $\mathbb{F}_{q^m}$ are represented as vectors of size $m$ over $\mathbb{F}_q$. For ROLLO, $q$ is always chosen equal to 2 (see section 2.7) thus $e \in \mathbb{F}_{q^m}$ is represented as $(e_0, \dots, e_{m-1}) \in \mathbb{F}_2^m$. In the reference implementation, elements are stored using $8 \times [m/64]$ bytes in which the unused $64 \times [m/64] - m$ bits are zero-padded. In the optimized implementation, elements are stored using $16 \times [m/128]$ bytes in which the unused $128 \times [m/128] - m$ are zero-padded. The first bit $e_0$ corresponds to the constant coefficient of the polynomial $e$.

The polynomials used to construct $\mathbb{F}_{2^m}$ as an extension of $\mathbb{F}_2$ are given table 2.

<table><caption>Table 2: Polynomials used to construct $\mathbb{F}_{2^m}$.</caption><thead><tr><th>m</th><th>P<sub>m</sub></th></tr></thead><tbody><tr><td>67</td><td>X<sup>67</sup> + X<sup>5</sup> + X<sup>2</sup> + X + 1</td></tr><tr><td>79</td><td>X<sup>79</sup> + X<sup>9</sup> + 1</td></tr><tr><td>83</td><td>X<sup>83</sup> + X<sup>7</sup> + X<sup>4</sup> + X<sup>2</sup> + 1</td></tr><tr><td>97</td><td>X<sup>97</sup> + X<sup>6</sup> + 1</td></tr></tbody></table>
**Vectors.** Elements of $\mathbb{F}_{q^m}^n$ are represented as $n$-dimensional arrays of $\mathbb{F}_{q^m}$ elements.

**Vector spaces.** Let $E$ be an $\mathbb{F}_q$-subspace of $\mathbb{F}_{q^m}$ and $(e_1, \dots, e_r) \in \mathbb{F}_{q^m}^r$ a basis of $E$. We suppose that Alice and Bob have agreed on a basis $(\beta_1, \dots, \beta_m)$ of $\mathbb{F}_{q^m}$ over $\mathbb{F}_q$. There exists a matrix $M \in \mathbb{F}_q^{r \times m}$ such that $(e_1, \dots, e_r)^T = M(\beta_1, \dots, \beta_m)^T$. In order to have a unique representation, the natural way is to choose the row echelon form of $M$ to represent $E$ (this is equivalent to choose a basis of $E$). This representation only depends on $E$. $M$ is then converted into a byte string before being hashed.

**Seeds.** The considered seed-expander has been provided by the NIST. It is initialized with a byte string of length 40 of which 32 are used as the **seed** and 8 are used as the **diversifier**. In addition, it is initialized with $\max\_length$ equal to $2^{32} - 1$.

### 2.6.1 Parsing vectors from/to byte strings

Vectors of $\mathbb{F}_{q^m}^n$ are converted to byte strings using a compact representation, in which the unused bits of each element are removed thus leading to a $\lceil \frac{nm}{8} \rceil$ long byte string.

## 2.7 Parameters for our schemes

### 2.7.1 General remarks

In this Section, we propose several sets of parameters for ROLLO-I and ROLLO-II, achieving 128, 192, or 256 bits of security and corresponding therefore to NIST's security strength categories 1, 3, and 5 respectively.

All of our submissions use ideal codes over $\mathbb{F}_{2^m}$ in order to reduce the size of the key and to allow to compute the syndrome of an error as sums and products of polynomials in $\mathbb{F}_{2^m}[X]/\langle P \rangle$, with $P \in \mathbb{F}_2[X]$ of degree $n$. In order to avoid folding attacks (see [13]), $P$ is chosen irreducible. Moreover, to decrease the computational costs, we want $P$ to be sparse. We have obtained these polynomials with the Magma software. More details are available at http://magma.maths.usyd.edu.au/magma/handbook/text/193#1685.

The best known attacks against our cryptosystems consist in solving an instance of the IRSD problem. The most important parameter for the complexity of algorithms which solve this problem is the weight of the error. That is why we want this parameter to increase at each level of security. Moreover, in order to get homogeneous parameters, we choose the same value for the weight of the error in all sets of parameters, 5 for 128 bits of security, 6 for 192 bits of security and 7 for 256 bits of security.

All the parameters have been chosen so that the best known attack requires at least $2^{\lambda}$ elementary operations for $\lambda$ bits of security. We refer the reader to Section 6 for more details on best known attacks.
## 2.7.2 ROLLO-I

**Choice of parameters.** In section 5.2, the security of the protocol is reduced to the ILRPC problem 2.3 and the IRSR problem 2.2. Our parameters are chosen in function of the best known attacks on these problems described in Section 6. Because of the recent results of [4] and [5] the best attacks for our type of parameters (except for 128 security bits) are now based on algebraic attacks and our parameters are chosen accordingly.

Notice that for 128 security bits parameters, the practical security is rather higher than 128 at about 170 bits. It was possible to have a smaller security parameter closer to 128 by considering smaller $r$ and $d$, but since there was almost no advantage on the size of the key, we chose to keep the security higher than 128.

The probability of decryption failure (DFR) comes from the probability that the RSR algorithm 1 fails (see Proposition 2.4.3).

**Size of parameters.** One may use seeds to represent the random data in order to decrease the keysize. We use the NIST seed expander initialized with 40 bytes long seeds.

The public key $pk$ is composed of a vector $h \in \mathbb{F}_{2^m}^n$, so its size is $\lceil \frac{nm}{8} \rceil$ bytes.

The secret key $sk$ is composed of two random vectors of $S_d^n(\mathbb{F}_{2^m})$, so its size is 40 bytes.

The ciphertext $ct$ is composed of a vector of $\mathbb{F}_{2^m}^n$, so its size is $\lceil \frac{nm}{8} \rceil$ bytes.

The shared secret $ss$ is composed of $K = \text{Hash}(E)$, so its size is 64 bytes (SHA512 output size).

<table><caption>Table 3: Parameters for ROLLO-I.</caption><thead><tr><th>Instance</th><th>q</th><th>n</th><th>m</th><th>r</th><th>d</th><th>P</th><th>security</th><th>DFR</th></tr></thead><tbody><tr><td>ROLLO-I-128</td><td>2</td><td>83</td><td>67</td><td>7</td><td>8</td><td>X<sup>83</sup> + X<sup>7</sup> + X<sup>4</sup> + X<sup>2</sup> + 1</td><td>128</td><td>2<sup>-28</sup></td></tr><tr><td>ROLLO-I-192</td><td>2</td><td>97</td><td>79</td><td>8</td><td>8</td><td>X<sup>97</sup> + X<sup>6</sup> + 1</td><td>192</td><td>2<sup>-34</sup></td></tr><tr><td>ROLLO-I-256</td><td>2</td><td>113</td><td>97</td><td>9</td><td>9</td><td>X<sup>113</sup> + X<sup>9</sup> + 1</td><td>256</td><td>2<sup>-33</sup></td></tr></tbody></table>

<table><caption>Table 4: Resulting sizes in bytes for ROLLO-I using NIST seed expander initialized with 40 bytes long seeds. The security is expressed in bits.</caption><thead><tr><th>Instance</th><th>pk size</th><th>sk size</th><th>ct size</th><th>ss size</th><th>Security</th></tr></thead><tbody><tr><td>ROLLO-I-128</td><td>696</td><td>40</td><td>696</td><td>64</td><td>128</td></tr><tr><td>ROLLO-I-192</td><td>958</td><td>40</td><td>958</td><td>64</td><td>192</td></tr><tr><td>ROLLO-I-256</td><td>1371</td><td>40</td><td>1371</td><td>64</td><td>256</td></tr></tbody></table>

## 2.7.3 ROLLO-II

**Choice of parameters.** In section 5.3, the security of the protocol is reduced to the ILRPC problem 2.3 and the IRSR problem 2.2. As for ROLLO-I our parameters are chosen in
function of the best known attacks on these problems described in Section 6, also algebraic attacks for this type of parameters.

The probability of decryption failure (DFR) comes from the probability that the RSR algorithm 1 fails (see Proposition 2.4.3).

**Size of parameters.** One may use seeds to represent the random data in order to decrease the keysize. We use the NIST seed expander initialized with 40 bytes long seeds.

The public key pk is composed of a vector $h \in \mathbb{F}_{2^m}^n$, so its size is $\lceil \frac{nm}{8} \rceil$ bytes.

The secret key sk is composed of two random vectors of $S_d^n(\mathbb{F}_{2^m})$, so its size is 40 bytes.

The ciphertext ct is composed of a vector of $\mathbb{F}_{2^m}^n$ and a message of 64 bytes masked by random value obtained via a hash. To obtain the IND-CCA2 security, we need to add another hash to the ciphertext (see Section 5.3.2 for more details) so the ciphertext size is $\lceil \frac{nm}{8} \rceil + 2 * 64$ bytes (two hashes).

<table><caption>Table 5: Parameters for ROLLO-II.</caption><thead><tr><th>Instance</th><th>q</th><th>n</th><th>m</th><th>r</th><th>d</th><th>P</th><th>security</th><th>DFR</th></tr></thead><tbody><tr><td>ROLLO-II-128</td><td>2</td><td>189</td><td>83</td><td>7</td><td>8</td><td>X<sup>189</sup> + X<sup>6</sup> + X<sup>5</sup> + X<sup>2</sup> + 1</td><td>128</td><td>2<sup>-134</sup></td></tr><tr><td>ROLLO-II-192</td><td>2</td><td>193</td><td>97</td><td>8</td><td>8</td><td>X<sup>193</sup> + X<sup>15</sup> + 1</td><td>192</td><td>2<sup>-130</sup></td></tr><tr><td>ROLLO-II-256</td><td>2</td><td>211</td><td>97</td><td>8</td><td>9</td><td>X<sup>211</sup> + X<sup>11</sup> + X<sup>10</sup> + X<sup>8</sup> + 1</td><td>256</td><td>2<sup>-136</sup></td></tr></tbody></table>

<table><caption>Table 6: Resulting sizes in bytes for ROLLO-II using NIST seed expander initialized with 40 bytes long seeds. The security is expressed in bits.</caption><thead><tr><th>Instance</th><th>pk size</th><th>sk size</th><th>ct size</th><th>Security</th></tr></thead><tbody><tr><td>ROLLO-II-128</td><td>1941</td><td>40</td><td>2089</td><td>128</td></tr><tr><td>ROLLO-II-192</td><td>2341</td><td>40</td><td>2469</td><td>192</td></tr><tr><td>ROLLO-II-256</td><td>2559</td><td>40</td><td>2687</td><td>256</td></tr></tbody></table>

# 3 Performances

This section provides performance measures of our implementations.

**Benchmark platform.** The benchmarks have been performed on a machine that has 16GB of memory and an Intel® Core™ i7-7820X CPU @ 3.6GHz for which the Hyper-Threading, Turbo Boost and SpeedStep features were disabled. The scheme have been compiled with gcc (version 9.2.0) and use the openssl (version 1.1.1d) library as a provider for SHA2. For each parameter set, the results have been obtained by computing the mean from 1000 random instances. In order to minimize biases from background tasks running on the benchmark platform, each instances have been repeated 100 times and averaged.
## 3.1 ROLLO-I

### Reference Implementation

The performance of our reference implementation on the aforementioned benchmark platform are described in Tab. 7 (thousands of CPU cycles). The following compilation flags have been used: `-O3 -flto`.

<table><caption>Table 7: Performances of ROLLO-I reference implementation in thousands of CPU cycles.</caption><thead><tr><td>Instance</td><td>KeyGen</td><td>Encap</td><td>Decrypt</td></tr></thead><tbody><tr><td>ROLLO-I-128</td><td>3530</td><td>392</td><td>1062</td></tr><tr><td>ROLLO-I-192</td><td>4669</td><td>458</td><td>1284</td></tr><tr><td>ROLLO-I-256</td><td>6962</td><td>591</td><td>1992</td></tr></tbody></table>

### Optimized Implementation

An optimized implementation using AVX2 instructions have been provided. Its performances on the aforementioned benchmark platform are described in Tab. 8 (millions of CPU cycles). The following compilation flags have been used: `-O3 -flto -mavx2 -mpclmul -msse4.2 -maes`.

<table><caption>Table 8: Performances of ROLLO-I optimized implementation in thousands of CPU cycles.</caption><thead><tr><td>Instance</td><td>KeyGen</td><td>Encrypt</td><td>Decap</td></tr></thead><tbody><tr><td>ROLLO-I-128</td><td>939</td><td>113</td><td>686</td></tr><tr><td>ROLLO-I-192</td><td>1142</td><td>127</td><td>803</td></tr><tr><td>ROLLO-I-256</td><td>1582</td><td>151</td><td>1347</td></tr></tbody></table>

## 3.2 ROLLO-II

### Reference Implementation

The performance of our reference implementation on the aforementioned benchmark platform are described in Tab. 9 (thousands of CPU cycles). The following compilation flags have been used: `-O3 -flto`.

### Optimized Implementation

An optimized implementation using AVX2 instructions have been provided. Its performances on the aforementioned benchmark platform are described in Tab. 10 (thousands of CPU cycles). The following compilation flags have been used: `-O3 -flto -mavx2 -mpclmul -msse4.2 -maes`.
<table><caption>Table 9: Performances of ROLLO-II reference implementation in thousands of CPU cycles.</caption><thead><tr><td>Instance</td><td>KeyGen</td><td>Encrypt</td><td>Decap</td></tr></thead><tbody><tr><td>ROLLO-II-128</td><td>16987</td><td>1309</td><td>3218</td></tr><tr><td>ROLLO-II-192</td><td>19153</td><td>1441</td><td>3684</td></tr><tr><td>ROLLO-II-256</td><td>22694</td><td>1643</td><td>4260</td></tr></tbody></table>

<table><caption>Table 10: Performances of ROLLO-II optimized implementation in thousands of CPU cycles.</caption><thead><tr><td>Instance</td><td>KeyGen</td><td>Encrypt</td><td>Decap</td></tr></thead><tbody><tr><td>ROLLO-II-128</td><td>3690</td><td>331</td><td>1195</td></tr><tr><td>ROLLO-II-192</td><td>3689</td><td>334</td><td>1258</td></tr><tr><td>ROLLO-II-256</td><td>4296</td><td>361</td><td>1604</td></tr></tbody></table>

## 3.3 Constant time Implementation

We provided a constant time version of the RSR algorithm 1 in the Additional_Implementations/ folder. This implementation provides the following:

* Constant-time implementation of the Gaussian reduction and of the intersection of vector spaces

* Manipulation of vector spaces of fixed dimension, regardless of the actual dimension of the vector space S

The performances of the reference constant-time version are presented figure 11 for ROLLO-I and 12 for ROLLO-II.

<table><caption>Table 11: Performances of ROLLO-I constant time implementation in thousands of CPU cycles.</caption><thead><tr><td>Instance</td><td>KeyGen</td><td>Encrypt</td><td>Decap</td></tr></thead><tbody><tr><td>ROLLO-I-128</td><td>3537</td><td>395</td><td>1754</td></tr><tr><td>ROLLO-I-192</td><td>4662</td><td>455</td><td>2286</td></tr><tr><td>ROLLO-I-256</td><td>6959</td><td>590</td><td>3594</td></tr></tbody></table>

## 4 Known Answer Test Values

Known Answer Test (KAT) values have been generated using the script provided by the NIST. They are available in the KAT/Reference_Implementation/ and KAT/Optimized_Implementation/ folders.
<table><caption>Table 12: Performances of ROLLO-II constant time implementation in thousands of CPU cycles.</caption><thead><tr><th>Instance</th><th>KeyGen</th><th>Encrypt</th><th>Decap</th></tr></thead><tbody><tr><td>ROLLO-II-128</td><td>16986</td><td>1307</td><td>4484</td></tr><tr><td>ROLLO-II-192</td><td>19702</td><td>1438</td><td>5200</td></tr><tr><td>ROLLO-II-256</td><td>23364</td><td>1618</td><td>6241</td></tr></tbody></table>

Notice that one can generate the aforementioned test files using the kat mode of our implementation. The procedure to follow in order to do so is detailed in the technical documentation.

# 5 Security

## 5.1 Security Models and Hybrid Argument

**IND-CPA.** IND-CPA is generally proved through the following game: the adversary $\mathcal{A}$ chooses two plaintexts $\mu_0$ and $\mu_1$ and sends them to the challenger who flips a coin $b \in \{0, 1\}$, encrypts $\mu_b$ into ciphertext $c$ and returns $c$ to $\mathcal{A}$. The encryption scheme is said to be IND-CPA secure if $\mathcal{A}$ has a negligible advantage in deciding which plaintext $c$ encrypts. This game is formally described hereunder on Fig. 4.

$\mathbf{Exp}_{\mathcal{E}, \mathcal{A}}^{\text{ind}-b}(\lambda)$

1. $\mathbf{param} \leftarrow \text{Setup}(1^{\lambda})$

2. $(pk, sk) \leftarrow \text{KeyGen}(\mathbf{param})$

3. $(\mu_0, \mu_1) \leftarrow \mathcal{A}(\text{FIND} : pk)$

4. $\mathbf{c}^* \leftarrow \text{Encrypt}(pk, \mu_b, \theta)$

5. $b' \leftarrow \mathcal{A}(\text{GUESS} : \mathbf{c}^*)$

6. $\text{RETURN } b'$

<caption>Figure 4: Experiment against the indistinguishability under chosen plaintext attacks</caption>

The global advantage for polynomial time adversaries (running in time less than $t$) is:

$$ \mathbf{Adv}_{\mathcal{E}}^{\text{ind}}(\lambda, t) = \max_{\mathcal{A} \le t} \mathbf{Adv}_{\mathcal{E}, \mathcal{A}}^{\text{ind}}(\lambda), \qquad (4) $$

where $\mathbf{Adv}_{\mathcal{E}, \mathcal{A}}^{\text{ind}}(\lambda)$ is the advantage the adversary $\mathcal{A}$ has in winning game $\mathbf{Exp}_{\mathcal{E}, \mathcal{A}}^{\text{ind}-b}(\lambda)$:

$$ \mathbf{Adv}_{\mathcal{E}, \mathcal{A}}^{\text{ind}}(\lambda) = \left| \Pr[\mathbf{Exp}_{\mathcal{E}, \mathcal{A}}^{\text{ind}-1}(\lambda) = 1] - \Pr[\mathbf{Exp}_{\mathcal{E}, \mathcal{A}}^{\text{ind}-0}(\lambda) = 1] \right|. \qquad (5) $$

**Hybrid argument.** Alternatively (and equivalently by the hybrid argument), it is possible to construct a sequence of games from a valid encryption of a first message $\mu_0$ to a
valid encryption of another message $\mu_1$ and show that these games are two-by-two indistinguishable. We follow this latter approach and prove the security of our KEM similarly to [1].

## 5.2 IND-CPA security proof of ROLLO-I

**Theorem 5.1.** Under the Ideal LRPC indistinguishability 2.3 and the Ideal-Rank Support Recovery 2.2 Problems, the KEM presented earlier in section 2.5.1 is indistinguishable against Chosen Plaintext Attack in the Random Oracle Model.

*Proof.* We are going to proceed in a sequence of games. The simulator first starts from the real scheme. First we replace the public key matrix by a random element, and then we use the ROM to solve the Ideal-Rank Support Recovery.

We start from the normal game $G_0$: We generate the public key $\mathbf{h}$ honestly, and $E, \mathbf{c}$ also

* In game $G_1$, we now replace $\mathbf{h}$ by a random vector, the rest is identical to the previous game. From an adversary point of view, the only difference is the distribution on $\mathbf{h}$, which is either generated at random, or as a product of low weight vectors. This is exactly the *Ideal LRPC indistinguishability* problem, hence

$$ \mathrm{Adv}_{\mathcal{A}}^{G_0} \le \mathrm{Adv}_{\mathcal{A}}^{G_1} + \mathrm{Adv}_{\mathcal{A}}^{\mathrm{ILRPC}} $$

* In game $G_2$, we now proceed as earlier except we receive $\mathbf{h}, \mathbf{c}$ from a Support Recovery challenger. After sending $\mathbf{c}$ to the adversary, we monitor the adversary queries to the Random Oracle, and pick a random one that we forward as our simulator answer to the Ideal-Rank Support Recovery problem. Either the adversary was able to predict the random oracle output, or with probably $1/q_G$, we picked the query associated with the support $E$ (by $q_G$ we denote the number of queries to the random oracle $G$), hence

$$ \mathrm{Adv}_{\mathcal{A}}^{G_1} \le 2^{-\lambda} + 1/q_G \cdot \mathrm{Adv}_{\mathcal{A}}^{\mathrm{RSR}} $$

which leads to the conclusion.

□

## 5.3 IND-CCA2 security proof of ROLLO-II

### 5.3.1 IND-CPA security proof of the ROLLO-II PKE

**Theorem 5.2.** Under the Ideal LRPC indistinguishability 2.3 and the Ideal-Rank Support Recovery 2.2 Problems, the encryption scheme presented earlier in section 2.5.2 in indistinguishable against Chosen Plaintext Attack in the Random Oracle Model.
*Proof.* We are going to proceed in a sequence of games. The simulator first starts from the real scheme. First we replace the public key matrix by a random element, and then we use the ROM to solve the QC-Rank Support Recovery.

We start from the normal game $G_0$: We generate the public key $h$ honestly, and $E, c$ also

* In game $G_1$, we now replace $h$ by a random vector, the rest is identical to the previous game. From an adversary point of view, the only difference is the distribution on $h$, which is either generated at random, or as a product of low weight vectors. This is exactly the *Ideal LRPC indistinguishability* problem, hence

$$ \mathrm{Adv}_{\mathcal{A}}^{G_0} \le \mathrm{Adv}_{\mathcal{A}}^{G_1} + \mathrm{Adv}_{\mathcal{A}}^{\mathrm{ILRPC}} $$

* In game $G_2$, we now proceed as earlier except we replace $G(E)$ by random. It can be shown, that by monitoring the call to the ROM, the difference between this game and the previous one can be reduced to the QC-Rank Support Recovery problem, so that:

$$ \mathrm{Adv}_{\mathcal{A}}^{G_1} \le 2^{-\lambda} + q_G \cdot \mathrm{Adv}_{\mathcal{A}}^{\mathrm{IRSR}}. $$

* In a final game $G_3$ we replace $d = M \oplus \mathrm{Rand}$ by just $d = \mathrm{Rand}$, which leads to the conclusion.

□

### 5.3.2 A IND-CCA2 conversion of the ROLLO-II PKE

Let $\mathcal{E}$ be an instance of the ROLLO-II cryptosystem as described above. Let $\mathcal{G}, \mathcal{H}$, and $\mathcal{K}$. The KEM-DEM version of the ROLLO-II cryptosystem is defined as follows (following [15]):

When applying the HHK [15] framework for the Fujisaki-Okamoto transformation, one can show that the final transformation is CCA-2 secure such that:

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{CCA}-2} \le q_G \cdot \delta + q_V \cdot 2^{-\gamma} + \frac{2q_G + 1}{|\mathcal{M}|} + 3\mathrm{Adv}_{\mathcal{A}}^{\mathrm{CPA}} $$

As our scheme is CPA secure, the last term is negligible, we can handle exponentially large message space for a polynomial number of query, so the previous is too.

As shown before, our scheme is gamma-spread so again for a polynomial number of verification query, the term in $q_V$ is negligible.

The tricky term remaining is $q_G \cdot \delta$, this is the product of the number of queries to the random oracle, by the probability of generating an decipherable ciphertext in an honest execution. For real application, we want schemes to be correct enough so that the probability of such occurrence is very small. This often leads, in application in running with a probability of a magnitude of $2^{-64}$. This may seem not low enough for pure cryptographic security, however it should be noted this number, corresponds to the number of request,
* Setup(1^λ): as before, except that k will be the length of the symmetric key being exchanged, typically k = 256.

* KeyGen (param): exactly as before.

* Encap (pk): generate $\mathbf{m} \leftarrow \mathbb{F}^k$ (this will serve as a seed to derive the shared key). Derive the randomness $\theta \leftarrow \mathcal{G}(\mathbf{m})$. Generate the ciphertext $c \leftarrow (\mathbf{u}, \mathbf{v}) = \mathcal{E}.Encrypt(pk, \mathbf{m}, \theta)$, and derive the symmetric key $K \leftarrow \mathcal{K}(\mathbf{m}, \mathbf{c})$. Let $\mathbf{d} \leftarrow \mathcal{H}(\mathbf{m})$, and send $(\mathbf{c}, \mathbf{d})$.

* Decap (sk, c, d): Decrypt $\mathbf{m}' \leftarrow \mathcal{E}.Decrypt(sk, c)$, compute $\theta' \leftarrow \mathcal{G}(\mathbf{m}')$, and (re-)encrypt $\mathbf{m}'$ to get $\mathbf{c}' \leftarrow \mathcal{E}.Encrypt(pk, \mathbf{m}', \theta')$. If $\mathbf{c} \neq \mathbf{c}'$ or $\mathbf{d} \neq \mathcal{H}(\mathbf{m}')$ then abort. Otherwise, derive the shared key $K \leftarrow \mathcal{K}(\mathbf{m}, \mathbf{c})$.

<caption>Figure 5: Description of our proposal ROLLO-II.KEM.</caption>

adversarially generated where the simulator gives an honest answer to a decryption query, which would mean that a single user would be able to do as many queries as expected by the whole targeted users in a live application, so a little trade-off at this level seems more than fair.

**Security concerns and implementation details.** Notice that while NIST only recommends SHA512 as a hash function, the transformation of [15] would be dangerous – at least in our setting – if one sets $\mathcal{G} = \mathcal{H}$. Indeed, publishing the randomness $\theta = \mathcal{G}(\mathbf{m}) = \mathcal{H}(\mathbf{m}) = \mathbf{d}$ used to generate $\mathbf{e}_1$ and $\mathbf{e}_2$, would allow one to retrieve the secret $E$. We therefore suggest to use SHA3-512 for $\mathcal{G}$ and SHA512 for $\mathcal{H}$.

# 6 Known Attacks

In this section, we present the best known attacks against the **IRSR 2.2**, **ILRPC 2.3** and **DIRSD 2.2.6** problems on which our schemes are based.

Both the **ILRPC** and **DIRSD** problems are decision problems. However, at the current state-of-the-art, the best attacks consist in solving a search problem: finding a codeword of a small weight in an ideal **LRPC** code for the **ILRPC** and solving an instance of the **IRSD** problem for the **DIRSD** problem.

There exist two types of attacks on these problems:

* the combinatorial attacks where the goal is to find the support of the error or of the codeword.

* the algebraic attacks where the opponent tries to solve an algebraic system by Gröbner basis.

First, we deal with the combinatorial attacks for the **IRSD** and the **ILRPC** problems and in a third subsection we discuss about the algebraic attacks.
## 6.1 Attack on the IRSD problem

For an $[sn, n]$ ideal code over $\mathbb{F}_{q^m}$ the best combinatorial attack to solve the IRSD problem 2.2.6 with an error of weight $r$ is in:

$$ \mathcal{O}((s-1)nm)^{\omega}q^{r\left\lfloor \frac{m(n+1)}{sn}\right\rfloor-m} $$

operations in $\mathbb{F}_q$. $\omega$ is the exponent of the complexity of the solution of a linear system.

This attack is an improvement of a previous attack described in [9], a detailed description of the attack can be found in [3]. The general idea of the attack is to adapt the Information Set Decoding attack for the Hamming distance. For the rank metric, the attacker tries and guesses a subspace which contains the support of the error and then solves a linear system obtained from the parity-check equations to check if the choice was correct.

The complexity of the best attack against IRSR problem is the same since there is no known way to compute the support of an error without first computing this error.

This attack is a generic attack against the RSD problem, there is no known improvement which exploit the ideal structure of the code.

**Remark 6.1.** Since the linear system is not random, it is reasonable to take $\omega = 2$ for the choice of the parameters of ROLLO-I and ROLLO-II, even if the attack described in [3] takes $\omega = 3$.

Let us remark that the choice of our parameter is flexible. We could take $\omega = 0$ and increase the parameters, which corresponds to only keeping the exponential complexity of the attack, for instance by slightly increasing $m$.

## 6.2 Structural attack on ideal LRPC codes

Let $C$ be an $[2n, n]_{q^m}$ ideal LRPC code generated by the two polynomials $(\mathbf{x}, \mathbf{y})$ of support $F$ of dimension $d$. Let $\mathbf{h} = \mathbf{x}^{-1}\mathbf{y}$ which generates the systematic parity-check matrix of $C$. The problem is to recover the structure of $C$, given only access to $\mathbf{h}$.

The most efficient known attack is to find a codeword of weight $d$ in an $[2n - \lfloor \frac{n}{d} \rfloor, n - \lfloor \frac{n}{d} \rfloor]_{q^m}$ subcode $C'$ of the dual code $C^{\perp}$ generated by $\mathbf{h}$, as described in [10]. The best algorithm is the same decoding algorithm used in the previous subsection [3]. Its complexity is in:

$$ \mathcal{O}\left((nm)^{\omega}q^{d\left\lfloor \frac{n-\lfloor \frac{n}{d} \rfloor}{2n-\lfloor \frac{n}{d} \rfloor} \right\rfloor-m}\right) $$

However, the dual of an ideal LRPC code contains much more codeword of weight $d$ than a random code with the same parameters. Indeed, let $\mathbf{H}$ be the matrix of size $n \times 2n$ generated by $(\mathbf{x}, \mathbf{y})$. By definition, $\mathbf{H}$ is a generator matrix of $C^{\perp}$. Let $(\mathbf{h}_i)_{1 \le i \le n}$ be the rows of $\mathbf{H}$. For all $1 \le i \le n$, $\text{Supp}(\mathbf{h}_i) = F \implies C^{\perp}$ contains $q^n$ codewords of the same support. Thus, we have considered an attack in

$$ \mathcal{O}\left((nm)^{\omega}q^{d\left\lfloor \frac{m}{2} \right\rfloor-m-n}\right) $$
for the choice of the parameters of ROLLO-I and ROLLO-II.

There exists a specific attack on the ideal LRPC codes which can be found in [13]. In this article, the authors present an attack against double circulant LRPC codes but it can be adapted straightforwardly in the case of ideal LRPC codes. However, the crucial point of this attack is that the polynomial $X^n - 1$ has always $X - 1$ as divisor and may have many more factors depending on $n$ and $q$. In the case of ideal LRPC codes, we can choose an irreducible polynomial $P$ of degree $n$ of $\mathbb{F}_q[X]$ to generate the quotient-ring $\mathbb{F}_q[X]/\langle P\rangle$, which completely negates this specific attack.

## 6.3 Algebraic attacks

For a long time algebraic attacks against the RSD problem were thought to be harmless, two recent papers [4] and [5] have permitted to have a clear and better view of the situation of algebraic attacks for rank metric. These results show that for our cryptographic when $r = O(\sqrt{n})$ they are in fact the best attacks. We sum up in the following these results.

The purpose of algebraic attacks is to consider an RSD instance and to write it as a system of equations, called a modeling, then if one solves this system, that is to say finds one solution, it is a solution to the RSD instance.

Ourivski and Johansson pioneered the algebraic attack against RSD by giving a modeling in [18], then Levy and Perret first proposed to solve it using Gröbner basis computations in [16]. In [4], a new modeling was proposed, it is based on maximal minors taken from a slightly different version of Ourivksi and Johansson's modeling.

From now on, in this section, we deal with RSD instances based on $[n, k]$-code over $\mathbb{F}_{2^m}$ with target rank weight $r$.

The modeling uses the fact that the vector $e$ of small weight $r$ can be written as a product $SC$ where $S$ is a matrix containing a basis of the support of $e$ and $C$ is a matrix containing the coordinates of each component of $e$ in this basis. Those matrices are called the *support* and the *coordinate* matrices.

Roughly, the system will consist in $m \binom{n-k-1}{r}$ equations in $\binom{n}{r}$ variables which are maximal determinants, in [4], this system was then solved by computing its Gröbner basis; in [5], a different modeling enables one to solve it directly by linearization. More precisely, the condition

$$m \binom{n-k-1}{r} \geq \binom{n}{r} \qquad (6)$$

is inherent to this system; when it is fulfilled, it corresponds to the *overdetermined case*, if it is not, it corresponds to the *underdetermined case*.

**Overdetermined case.** If the condition (6) is fulfilled, solving the RSD problem is equivalent to solving a linear system with $m \binom{n-k-1}{r}$ equations in $\binom{n}{r}$ variables, which can be done with a cost in

$$O\left(m \binom{n-k-1}{r} \binom{n}{r}^{\omega-1}\right). \qquad (7)$$
On the one hand, if the condition (6) is widely fulfilled, there is an optimization in [5] to reduce the complexity of (7) using a punctured version of the code. On the other hand, if (6) is not fulfilled, one can reduce to it by guessing few variables at an exponential cost, it is an hybrid attack, also in [5].

**Underdetermined case.** For cryptographic purpose, the parameters are chosen so that they belong to an area where the condition (6) is obviously not fulfilled and where the exponential cost of the hybrid attack would make it impractical, this particular area is called the *underdetermined case*. The best known complexity in this case is also described in [5]: it uses a variation of the aforementioned system together with a new setting coming from the reduction between RSD and the MinRank problem. This new system, despite being bigger, is sometimes sparser, so its resolution could take advantage of Wiedemann algorithm to solve sparse linear systems.

More precisely, the complexity in the underdetermined case is

$$ \mathcal{O}((B_b + C_b)A_b^{\omega-1}) \qquad (8) $$

where

$$ \begin{aligned} A_b &:= \sum_{j=1}^{b} \binom{n}{r} \binom{mk+1}{j} \\ B_b &:= \sum_{j=1}^{b} \binom{m}{r} \binom{mk+1}{j} \\ C_b &:= \sum_{j=1}^{b} \sum_{i=1}^{j} \binom{(-1)^{i+1}}{r+i} \binom{n}{i} \binom{m+i-1}{j-i} \binom{mk+1}{j-i} \end{aligned} $$

and where $b$ is the smallest positive integer so that the condition $A_b - 1 \le B_c + C_b$ is fulfilled. When $b \ge 2$, one uses Wiedemann algorithm, resulting in a new complexity of

$$ \mathcal{O} \left( \frac{B_b \binom{k+r+1}{r} + C_b(mk+1)(r+1)}{B_b + C_b} \left( \sum_{j=1}^{b} \binom{n}{r} \binom{mk+1}{j} \right)^2 \right). \qquad (9) $$

## 6.4 Quantum speed-up

For computational attacks, the quantum speed-up is easy to analyze. According to [7], a slight generalization of Grover's quantum search algorithm allows to divide by a factor 2 the exponential complexity of the attacks. Thus the complexity of the quantum computational attack is

* $\mathcal{O}((s-1)nm)^{\omega q^{\frac{1}{2}(r\lceil \frac{m(n+1)}{sn} \rceil - m)}}$ for the attack on the $s$-IRSD problem.

* $\mathcal{O}((nm)^{\omega q^{\frac{1}{2}(d\lceil \frac{m}{2} \rceil - m - n)}})$ for the attack on ideal LRPC codes.
* at the best of our knowledge for algebraic attacks there is not any real quantum speed up

# 7 Advantages and Limitations

## 7.1 Strengths

The proposed schemes are very efficient, both in terms of size of keys and computational complexity. They also benefit from a constant time decoding algorithm and its failure probability is very well studied and estimated and can easily be chosen to meet security standards. Moreover, the choice of parameters is very versatile. For ROLLO-I and ROLLO-II, there is a reduction to a well understood generic problem IRSD, which is a natural generalization of Quasi-Cyclic RSD problem. This type of problems has been used for many years for Hamming and Euclidean distances.

## 7.2 Limitations

Rank metric has very nice features, but the use of rank metric for cryptographic purposes is not very old (1991). It may seem as a limitation, but still in recent years there have been a lot of activities on understanding the inherent computational difficulty of the related problems. The combinatorial attacks are very well understood, and the recent results of [4, 5] permit to have a clear view on the complexity of algebraic attacks.

Like for cryptosystems à la McEliece, ROLLO-I and ROLLO-II security proofs rely on the hardness of retrieving the structure of a structured code, in our case the ideal LRPC codes. However, this problem has been also studied for Hamming and euclidean metrics and is considered hard by the community (for instance, MDPC and NTRU-like cryptosystems are based on it).

# References

[1] Carlos Aguilar Melchor, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, and Gilles Zémor. Efficient encryption from random quasi-cyclic codes. CoRR, abs/1612.05572, 2016.

[2] Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography with constant input locality. pages 92–110.

[3] Nicolas Aragon, Philippe Gaborit, Adrien Hauteville, and Jean-Pierre Tillich. A new algorithm for solving the rank syndrome decoding problem. In Proc. IEEE Int. Symposium Inf. Theory - ISIT, Vail, USA, 2018. IEEE.
[4] Magali Bardet, Pierre Briaud, Maxime Bros, Philippe Gaborit, Vincent Neiger, Olivier Ruatta, and Jean-Pierre Tillich. An algebraic attack on rank metric code-based cryptosystems. In *Advances in Cryptology - EUROCRYPT 2020 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020. Proceedings*, 2020. To appear, preprint available on https://arxiv.org/pdf/1910.00810.pdf.

[5] Magali Bardet, Maxime Bros, Daniel Cabarcas, Philippe Gaborit, Ray Perlner, Daniel Smith-Tone, Jean-Pierre Tillich, and Javier Verbel. Algebraic attacks for solving the rank decoding and minrank problems without Gröbner basis, 2020. Preprint available on https://arxiv.org/pdf/2002.08322.pdf.

[6] Philippe Gaborit. Shorter keys for code based cryptography. In *Proceedings of the 2005 International Workshop on Coding and Cryptography (WCC 2005)*, pages 81–91, Bergen, Norway, March 2005.

[7] Philippe Gaborit, Adrien Hauteville, and Jean-Pierre Tillich. Ranksynd a PRNG based on rank metric. In *Post-Quantum Cryptography 2016*, pages 18–28, Fukuoka, Japan, February 2016.

[8] Philippe Gaborit, Gaétan Murat, Olivier Ruatta, and Gilles Zémor. Low rank parity check codes and their application to cryptography. In *Proceedings of the Workshop on Coding and Cryptography WCC'2013*, Bergen, Norway, 2013. Available on www.selmer.uib.no/WCC2013/pdfs/Gaborit.pdf.

[9] Philippe Gaborit, Olivier Ruatta, and Julien Schrek. On the complexity of the rank syndrome decoding problem. *IEEE Trans. Information Theory*, 62(2):1006–1019, 2016.

[10] Philippe Gaborit, Olivier Ruatta, Julien Schrek, and Gilles Zémor. New results for rank-based cryptography. In *Progress in Cryptology - AFRICACRYPT 2014*, volume 8469 of LNCS, pages 1–12, 2014.

[11] Philippe Gaborit and Gilles Zémor. On the hardness of the decoding and the minimum distance problems for rank codes. *IEEE Trans. Inform. Theory*, 62(12):7245–7252, 2016. https://arxiv.org/pdf/1404.3482.pdf.

[12] Adrien Hauteville and Jean-Pierre Tillich. New algorithms for decoding in the rank metric and an attack on the lrpc cryptosystem. In *2015 IEEE International Symposium on Information Theory (ISIT)*, pages 2747–2751. IEEE, 2015.

[13] Adrien Hauteville and Jean-Pierre Tillich. New algorithms for decoding in the rank metric and an attack on the LRPC cryptosystem. In *Proc. IEEE Int. Symposium Inf. Theory - ISIT 2015*, pages 2747–2751, Hong Kong, China, June 2015.
[14] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A ring-based public key cryptosystem. In Joe Buhler, editor, *Algorithmic Number Theory, Third International Symposium, ANTS-III, Portland, Oregon, USA, June 21-25, 1998, Proceedings*, volume 1423 of LNCS, pages 267–288. Springer, 1998.

[15] Dennis Hofheinz, Kathrin Hövelmanns, and Eike Kiltz. A modular analysis of the Fujisaki-Okamoto transformation. In *Theory of Cryptography Conference*, pages 341–371. Springer, 2017.

[16] Françoise Lévy-dit Vehel and Ludovic Perret. Algebraic decoding of codes in rank metric. In *proceedings of YACC06*, Porquerolles, France, June 2006. available on http://grim.univ-tln.fr/YACC06/abstracts-yacc06.pdf.

[17] Rafael Misoczki, Jean-Pierre Tillich, Nicolas Sendrier, and Paulo S. L. M. Barreto. MDPC-McEliece: New McEliece variants from moderate density parity-check codes. In *Proc. IEEE Int. Symposium Inf. Theory - ISIT*, pages 2069–2073, 2013.

[18] Alexei V. Ourivski and Thomas Johansson. New technique for decoding codes in the rank metric and its cryptography applications. *Problems of Information Transmission*, 38(3):237–246, 2002.