# RYDE specifications

Nicolas Aragon, Magali Bardet, Loïc Bidoux, Jesús-Javier Chi-Domínguez, Victor Dyseryn, Thibauld Feneuil, Philippe Gaborit, Antoine Joux, Matthieu Rivain, Jean-Pierre Tillich, et al.

## ► To cite this version:

Nicolas Aragon, Magali Bardet, Loïc Bidoux, Jesús-Javier Chi-Domínguez, Victor Dyseryn, et al.  
RYDE specifications. 2023. hal-04315895

HAL Id: hal-04315895

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

Submitted on 30 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>
RYDE specifications

Nicolas Aragon<fnref n="1" />, Magali Bardet<fnref n="2" />,<fnref n="3" />, Loïc Bidoux<fnref n="4" />, Jesús-Javier Chi-Domínguez<fnref n="4" />, Victor Dyseryn<fnref n="5" />, Thibauld Feneuil<fnref n="6" />,<fnref n="7" />, Philippe Gaborit<fnref n="5" />, Antoine Joux<fnref n="8" />, Matthieu Rivain<fnref n="7" />, Jean-Pierre Tillich<fnref n="3" />, and Adrien Vinçotte<fnref n="5" />

<footnote n="1">¹ Naquidis Center, Talence, France</footnote>

<footnote n="2">² LITIS, University of Rouen Normandie, France</footnote>

<footnote n="3">³ INRIA, Paris, France</footnote>

<footnote n="4">⁴ Technology Innovation Institute, UAE</footnote>

<footnote n="5">⁵ University of Limoges, France</footnote>

<footnote n="6">⁶ Sorbonne Université, CNRS, INRIA, Institut de Mathématiques de Jussieu-Paris Rive Gauche, Ouragan, Paris, France</footnote>

<footnote n="7">⁷ Cryptoexperts, Paris, France</footnote>

<footnote n="8">⁸ CISPA, Helmholtz Center for Information Security, Saarbrücken</footnote>
Table of Contents

<table><tr><td>1</td><td>Introduction</td><td>3</td></tr><tr><td>2</td><td>Background and notations</td><td>3</td></tr><tr><td>3</td><td>High level description of the signature scheme</td><td>5</td></tr><tr><td>3.1</td><td>MPC protocol</td><td>5</td></tr><tr><td>3.2</td><td>Application of the MPCitH paradigm</td><td>6</td></tr><tr><td>4</td><td>Detailed algorithmic description</td><td>7</td></tr><tr><td>4.1</td><td>Algorithmic notation</td><td>7</td></tr><tr><td>4.2</td><td>Operations on finite field elements</td><td>9</td></tr><tr><td>4.3</td><td>Randomness generators and hash functions</td><td>10</td></tr><tr><td>4.4</td><td>Sampling routines</td><td>11</td></tr><tr><td>4.5</td><td>MPC routines</td><td>13</td></tr><tr><td>4.6</td><td>Hypercube routines</td><td>14</td></tr><tr><td>4.7</td><td>Key parsing routines</td><td>15</td></tr><tr><td>4.8</td><td>PRG tree routines</td><td>15</td></tr><tr><td>4.9</td><td>Protocol specification</td><td>16</td></tr><tr><td>5</td><td>Parameter Sets</td><td>19</td></tr><tr><td>5.1</td><td>Additive-sharing scheme</td><td>19</td></tr><tr><td>5.2</td><td>Threshold-sharing scheme</td><td>20</td></tr><tr><td>6</td><td>Performance Analysis</td><td>20</td></tr><tr><td></td><td>Benchmark platform</td><td>20</td></tr><tr><td></td><td>Constant time</td><td>21</td></tr><tr><td>6.1</td><td>Reference Implementation</td><td>21</td></tr><tr><td>6.2</td><td>Optimized Implementation</td><td>21</td></tr><tr><td>7</td><td>Known Answer Test Values</td><td>22</td></tr><tr><td>8</td><td>Expected security strength</td><td>22</td></tr><tr><td>8.1</td><td>Resistance to quantum attacks</td><td>23</td></tr><tr><td>9</td><td>Analysis of known attacks</td><td>23</td></tr><tr><td>9.1</td><td>Kales and Zaverucha's attack against Fiat-Shamir Signatures</td><td>23</td></tr><tr><td>9.2</td><td>Combinatorial attacks against Rank-SD problem</td><td>24</td></tr><tr><td>9.2.1</td><td>Enumeration of basis</td><td>24</td></tr><tr><td>9.2.2</td><td>GRS Algorithm</td><td>25</td></tr><tr><td>9.2.3</td><td>An improvement of GRS Algorithm</td><td>25</td></tr><tr><td>9.3</td><td>Algebraic attacks against Rank-SD problem</td><td>25</td></tr><tr><td></td><td>Hybrid methods</td><td>25</td></tr><tr><td></td><td>MaxMinors Modeling</td><td>26</td></tr><tr><td></td><td>The Support Minors modeling</td><td>27</td></tr><tr><td>10</td><td>Advantages and limitations</td><td>29</td></tr><tr><td>10.1</td><td>Advantages</td><td>29</td></tr><tr><td>10.2</td><td>Limitations</td><td>30</td></tr></table>
# 1 Introduction

This document specifies the RYDE digital signature scheme. It is a quantum-resistant sig- nature, based on zero-knowledge proofs, and symmetric functions, such as hash functions. We present a high-level description of the scheme and the MPC-in-the-Head paradigm (it allows to transform MPC protocols in proofs of knowledge) on which the signatures are based. The security of the signature relies on the Rank Syndrome Decoding problem: thanks to the previous process we can transform a proof of knowledge of a witness to a Rank-SD instance [Fen22] to obtain a signature scheme. We apply then the Fiat-Shamir transform to obtain signature schemes.

We present a signature scheme, of which we have designed two variants, both based on the transformation of an additive MPC protocol optimized with the hypercube tech- nique [AMGH+22]. The difference of these variants is the number of parties we use in the underlying MPC protocol: taking less parties increases the size of the signature, but induces a faster one. We refer to the design document [BCDF+23] for the proofs of the security statements.

# 2 Background and notations

To understand the mathematical background to the problem, we begin by recalling a few fundamental definitions and fixing some notations.

Let $\mathbb{F}_{q^m}$ be the finite field of size $q^m$. We fix a $\mathbb{F}_q$-basis $\mathcal{B} = (b_1, ..., b_m)$ of $\mathbb{F}_{q^m}$.

Let us consider a vector $\mathbf{x} = (x_1, ..., x_n) \in \mathbb{F}_{q^m}^n$. Each coordinate $x_i$ can be associated with a vector $(x_{i,1}, ..., x_{i,m}) \in \mathbb{F}_q^m$ such that

$$x_i = \sum_{j=1}^{m} x_{i,j}b_j.$$

The matrix $\mathbf{M}(\mathbf{x}) = (x_{i,j})_{(i,j)\in[1,n]\times[1,m]}$ is called matrix associated to the vector $\mathbf{x}$.

We then define the following notations:

- the rank weight $W_R(\mathbf{x})$ of a vector $\mathbf{x}$ is defined as the rank of the associated matrix: $W_R(\mathbf{x}) := \mathrm{Rank}(\mathbf{M}(\mathbf{x}))$.

- the distance between two vectors $\mathbf{x}$ and $\mathbf{y}$ is then given by $d(\mathbf{x}, \mathbf{y}) := W_R(\mathbf{x} - \mathbf{y})$.

- the support of a vector $\mathbf{x}$ is the linear subspace of $\mathbb{F}_{q^m}$ generated by its coordinates:

$$\mathrm{Supp}(\mathbf{x}) = \langle x_1, ..., x_n \rangle.$$

Now that we have defined the mathematical background, we can define the Rank Syndrome Decoding problem, on which the security of the signature RYDE is based:

**Rank Syndrome Decoding problem:**

Let $(n, k, r)$ positive integers such that $k \le n$. The Rank Syndrome Decoding (Rank-SD) problem with parameters $(q, m, n, k, r)$ is the following one:
Let $\mathbf{H}$, $\mathbf{x}$ and $\mathbf{y}$ such that:

* $\mathbf{H}'$ is uniformly sampled from $\mathbb{F}_{q^m}^{(n-k)\times k}$, and $\mathbf{H} = (I | \mathbf{H}') \in \mathbb{F}_{q^m}^{(n-k)\times n}$

* $\mathbf{x}$ is uniformly sampled from $\{\mathbf{x} \in \mathbb{F}_{q^m}^n, W_R(\mathbf{x}) \le r\}$

* $\mathbf{y} = \mathbf{H}\mathbf{x}$

From the public data $(\mathbf{H}, \mathbf{y})$, find $\mathbf{x}$.

In the RYDE signature scheme, the public key is an instance $(\mathbf{H}, \mathbf{y})$ of the Rank-SD problem, and the secret key is the corresponding solution $\mathbf{x}$. The principle of the signature is based on a transformation of a proof of knowledge into a non-interactive protocol thanks to the Fiat-Shamir transform [FS86]. Iterating this process multiple times gives the verifier high assurance that the prover knows $\mathbf{x}$.

The interactive proof relies on a prover which simulates a multiparty computation (MPC) protocol, where each party has a share of the secret witness $\mathbf{x}$. One details here the formalism proposed by [FR22]. The sharing of a secret value $s$ into $N$ parties is denoted $(s[1], ..., s[N])$, where $s[i]$ is the share of index $i$ for $i \in [1, N]$, and $s[J] = (s[i])_{i \in J}$ is the subset of shares for $J \subset [1, N]$.

Let $\mathbb{F}$ a finite field and an integer $\ell \in [1, N]$. A $(\ell, N)$-threshold Linear Secret Sharing Scheme is a method to share a secret $s \in \mathbb{F}$ into $N$ shares $s[1, N] = (s[1], ..., s[N]) \in \mathbb{F}^N$ such that the secret can be rebuilt from any subset of $\ell + 1$ shares, while the knowledge of any subset of $\ell$ shares (or less) gives no information on $s$.

Formally, a $(\ell + 1, N)$-threshold LSSS is a pair of algorithms:

$$ \begin{cases} \text{Share} : \mathbb{F} \times \mathbb{R} \to \mathbb{F}^N \\ \text{Reconstruct}_J : \mathbb{F}^\ell \to \mathbb{F} \end{cases} $$

where $R$ denotes some randomness space, and $\text{Reconstruct}_J$ is indexed by a subset $J \subset [1, N]$ of $\ell + 1$ elements. These algorithms must verify the following properties:

- **Correctness**: $\text{Reconstruct}$ allows to retrieve $s$ if it has any subset of $\ell + 1$ shares as input;

- **Perfect $\ell$-privacy**: The distribution of the outputs of Share on two different secrets are perfectly indistinguishable;

- **Linearity**: for every $v, v' \in \mathbb{F}^\ell$, $\alpha \in \mathbb{F}$ and subset $J \subset [1, N]$ of $\ell + 1$ elements:

$$ \text{Reconstruct}_J(\alpha v + v') = \alpha \text{Reconstruct}_J(v) + \text{Reconstruct}_J(v') $$

We present below the additive secret sharing, that we use in the signature scheme:

### Additive secret sharing

An additive secret sharing over a finite field $\mathbb{F}$ is an $(N, N)$-threshold LSSS where $R =$
$\mathbb{F}^{N-1}$. The Share algorithm is defined as:

$$ \text{Share} : (s, (r_1, \dots, r_{N-1})) \rightarrow s[1, N] = \left( r_1, \dots, r_{N-1}, s - \sum_{i=1}^{N-1} r_i \right) $$

The Reconstruct$_{[1,N]}$ outputs the sum of all the shares.

## 3 High level description of the signature scheme

As mentioned below, the security of the signature scheme relies on the hardness to solve the Rank-SD problem. The instance $(\mathbf{H}, \mathbf{y})$ is the public key of the signature, and the associated witness $\mathbf{x}$ is the secret key. In order to sign a message, we must:

- Build an interactive zero-knowledge proof of the knowledge of $\mathbf{x}$;

- Use the Fiat-Shamir transform to obtain a non-interactive proof

The proof relies on an MPC protocol, and we use the MPC-in-the-Head paradigm to transform it in a zero-knowledge proof.

### 3.1 MPC protocol

A multi-party computation protocol is an interactive protocol involving several parties whose objective is to jointly compute a function $f$ on the shares $x[\cdot]$ they received at the begin of the protocol, so that they obtained the shares $f(x)[\cdot]$ at the end of the protocol. At each step, the parties can perform one of the following actions:

- Receiving elements: it can be randomness sent by a random oracle, or the share of a hint which depends on the witness $\omega$ and the previous elements sent;

- Computing: since the sharing is linear, the parties can perform linear transformations on their shares;

- Broadcasting: it is sometimes necessary to open some shared values (which give no information about the witness $\omega$) to execute the protocol.

Due to application to zero-knowledge proofs that we will do below, we suppose here that all parties are honest: they compute and share only correct values.

The interactive proof relies on the application of the MPC-in-the-Head (MPCitH) paradigm [IKOS07]: the prover simulates a MPC protocol, where each party has a share of the secret witness $\mathbf{x}$. Informally, an MPC protocol takes place as follows:

- each party takes a share of the witness;

- they jointly compute (some operations are locally calculated, others are performed together) a Boolean value indicating whether $\mathbf{x}$ is right the witness associated to $(\mathbf{H}, \mathbf{y})$ (in other words, the MPC protocol compute the function $f$ which verifies that $\mathbf{x}$ is the correct solution of the instance $(\mathbf{H}, \mathbf{y})$);
- In the case of the additive sharing, the view of all parties except one gives no information about $\boldsymbol{x}$.

We formally describe the MPC protocol [Fen22] used for the RYDE scheme in Figure 1. Compared to its original version, the protocol of Figure 1 integrates an optimization: it relies on the fact that $L(1) = 0$ to save one field element in the communication cost. We refer to [BCDF$^{+}$23] for the proof of correctness and the false positive rate.

**Public values.** An instance of a Rank-SD problem: $\mathbf{H} = (I \ \mathbf{H}') \in \mathbb{F}_{q^m}^{(n-k) \times n}$ and $\mathbf{y} \in \mathbb{F}_{q^m}^{n-k}$.

**Inputs.** Each party takes a share of $\boldsymbol{x}_B[\cdot]$ where $\boldsymbol{x} \in \mathbb{F}_{q^m}^n$. Let $U$ a $\mathbb{F}_q$-linear subspace of $\mathbb{F}_{q^m}$ of dimension $r$ which contains $x_1, \dots, x_n$ and has for annihilator polynomial $L = \prod_{u \in U} (X - u)$. Each party takes a share of the following sharing as inputs : $L[\cdot] = \sum_{i=1}^{r-1} \beta_i[\cdot](X^{q^i} - X) + (X^r - X)$, $\boldsymbol{a}[\cdot]$ where $\boldsymbol{a}$ is uniformly sampled from $\mathbb{F}_{q^m \cdot \eta}^r$ and $c[\cdot]$ such that $c = -\langle \boldsymbol{\beta}, \boldsymbol{a} \rangle$.

**MPC Protocol:**

1. The parties sample uniformly random: $(\gamma_1, \dots, \gamma_n, \varepsilon) \stackrel{\$}{\leftarrow} \mathbb{F}_{q^m \cdot \eta}^{n+1}$.

2. The parties locally compute $\boldsymbol{x}_A[\cdot] = \mathbf{y} - \mathbf{H}'\boldsymbol{x}_B[\cdot]$ and $\boldsymbol{x}[\cdot] = (\boldsymbol{x}_A[\cdot] || \boldsymbol{x}_B[\cdot])$.

3. The parties locally compute $z[\cdot] = -\sum_{j=1}^n \gamma_j (x_j[\cdot]q^j - x_j[\cdot])$.

4. The parties locally compute for all $k$ from $1$ to $r-1$: $\omega_k[\cdot] = \sum_{j=1}^n \gamma_j (x_j[\cdot]q^k - x_j[\cdot])$.

5. The parties locally compute $\boldsymbol{\alpha}[\cdot] = \varepsilon \cdot \boldsymbol{\omega}[\cdot] + \boldsymbol{a}[\cdot]$.

6. The parties open $\boldsymbol{\alpha}$.

7. The parties locally compute $v[\cdot] = \varepsilon \cdot z[\cdot] - \langle \boldsymbol{\alpha}, \boldsymbol{\beta}[\cdot] \rangle - c[\cdot]$.

8. The parties open $v$.

9. The parties output ACCEPT if $v = 0$, and reject otherwise.

<caption>Fig. 1: Protocol $\Pi^n$: a protocol that checks that the given input is a solution of the considered instance of Rank-SD problem</caption>

## 3.2 Application of the MPCitH paradigm

The MPC-in-the-Head paradigm, introduced by [IKOS07], is a framework enabling to convert an MPC protocol into a zero-knowledge proof. The RYDE signature scheme has two trade-offs, induced by the same proof of knowledge. Both use an additive MPC protocol turned into zero-knowledge proof thanks to the MPC-in-the-Head paradigm, but with different numbers of parties.

We start by presenting the main idea of the hypercube optimization [AMGH$^{+}$22]: splitting a secret in $N = 2^D$ additive shares, and arranging them in a geometrical structure. Let us consider an hypercube of dimension $D$, each dimension having 2 slots. These $2^D$ shares are called “leafs”. Since we use an additive secret sharing, one can intertwine several executions where each party (what we will call a “main party”) can be the sum of a subset of leafs, such that these subsets form a partition of the leafs. The main parties’ shares of a secret $s$ are denoted $\hat{s}$. We build here $D$ intertwined protocols, and each of them has 2 main parties (an interested reader can find more details in [BCDF$^{+}$23]).
The proof of knowledge in the additive case works as follows:

- the prover builds the inputs of the MPC protocol, i.e, he generates the states of $N$ parties;

- he then commits the states of the parties, and receives a first challenge corresponding to some random values. This challenge consists in the random values $(\gamma_1, ..., \gamma_n, \varepsilon)$ to be used in the MPC protocol;

- the prover runs one MPC protocol per dimension of hypercube. For each of the $D$ dimensions, he builds two main parties, each of them being the sum of the leafs whose has the same coordinate for this dimension. The prover hashes the shares of $\alpha$ and $v$;

- thanks to this challenge, he simulates the MPC protocol on the main parties, and hashes the results of the computations;

- he receives a second challenge, which is a subset of $N-1$ parties, and reveals their views. (In practice, he receives only a subset of 1 party, and reveals the views of every party except this one). He also reveals one specific share of data for the party whose views are not revealed;

- the verifier can verify that the computation of the MPC protocol was done honestly.

From the interactive proof of knowledge, we can easily build a non-interactive proof/signature, using the Fiat-Shamir transform [FS86].

# 4 Detailed algorithmic description

This section is dedicated to a low-level algorithmic description of the three algorithms of our scheme: `RYDE_Keygen`, `RYDE_Sign` and `RYDE_Verify`. Before that, we introduce low-level notation in Section 4.1, and detail subroutines of our main algorithm in Sections 4.2-4.8.

The MPC protocol from Figure 1 is characterized by a degree $\eta$ of extension of $\mathbb{F}_{q^m}$ in which the computations are done. The signature size is minimized for $\eta = 1$, as presented in Section 5. The rest of this section assumes $\eta = 1$ for simplification purposes.

## 4.1 Algorithmic notation

For an integer $x \in [0, 2^D - 1]$ and $\delta \in [D]$, we denote $\text{bit}(x, \delta)$ the $\delta$-th least significant bit of the binary representation of $x$. For example, let $x = 35 = 100011_2$, then $\text{bit}(x, 2) = 1$ and $\text{bit}(x, 3) = 0$.
<table><thead><tr><th colspan="3">Indexes:</th></tr></thead><tbody><tr><td><i>i</i></td><td>[1, N]</td><td>Index of a leaf party.</td></tr><tr><td><i>δ</i></td><td>[1, D]</td><td>Index of a main party.</td></tr><tr><td><i>e</i></td><td>[1, τ]</td><td>Index of an iteration.</td></tr><tr><td colspan="3"><strong>Seeds:</strong></td></tr><tr><td><i>seed_pk</i></td><td>{0, 1}<sup>λ</sup></td><td>Seed for generation of the public matrix <i>H</i>.</td></tr><tr><td><i>seed_sk</i></td><td>{0, 1}<sup>λ</sup></td><td>Seed for generation of the secret vector <i>x</i> and secret annihilator polynomial <i>β</i>.</td></tr><tr><td><i>mseed</i></td><td>{0, 1}<sup>λ</sup></td><td>Master seed for generation of the seeds <i>seed</i><sup>(e)</sup></td></tr><tr><td><i>seed</i><sup>(e)</sup></td><td>{0, 1}<sup>λ</sup></td><td>Root seed of the PRG tree.</td></tr><tr><td><i>seed</i><sub><i>i</i></sub><sup>(e)</sup></td><td>{0, 1}<sup>λ</sup></td><td>Leaf seed of the PRG tree.</td></tr><tr><td><i>ptree</i><sup>(e)</sup></td><td>{0, 1}<sup>λD</sup></td><td>Partial seeds of the PRG tree masking an index <i>i</i><sup>*</sup><sub>(e)</sub>.</td></tr><tr><td colspan="3"><strong>Constants:</strong></td></tr><tr><td><i>DS_M</i></td><td>{0, 1}<sup>λ</sup></td><td>Domain separator for the message.</td></tr><tr><td><i>DS_T</i></td><td>{0, 1}<sup>λ</sup></td><td>Domain separator for the PRG tree.</td></tr><tr><td><i>DS_C</i></td><td>{0, 1}<sup>λ</sup></td><td>Domain separator for the PRG commitments.</td></tr><tr><td><i>DS_1</i></td><td>{0, 1}<sup>λ</sup></td><td>Domain separator for the first response.</td></tr><tr><td><i>DS_2</i></td><td>{0, 1}<sup>λ</sup></td><td>Domain separator for the second response.</td></tr><tr><td colspan="3"><strong>Bytestring variables:</strong></td></tr><tr><td><i>cmt</i><sub><i>i</i></sub><sup>(e)</sup></td><td>{0, 1}<sup>2λ</sup></td><td>Leaf commitments.</td></tr><tr><td><i>h</i><sub>1</sub></td><td>{0, 1}<sup>2λ</sup></td><td>First commitment.</td></tr><tr><td><i>h</i><sub>2</sub></td><td>{0, 1}<sup>2λ</sup></td><td>Second commitment.</td></tr><tr><td colspan="3"><strong>Field elements, vectors and matrices:</strong></td></tr><tr><td><b><i>H</i></b></td><td>F<sub><i>q</i><sup><i>n</i>−<i>k</i></sub></sub><sup><i>n</i>−<i>k</i></sup>×<i>n</i></td><td>Public matrix.</td></tr><tr><td><b><i>x</i></b></td><td>F<sub><i>q</i><sup><i>n</i></sub></sub><sup><i>n</i></sup></td><td>Secret vector of small rank weight.</td></tr><tr><td><b><i>β</i></b></td><td>F<sub><i>q</i><sup><i>r</i>−<i>1</i></sub></sub><sup><i>r</i></sup></td><td>Annulator polynomial of the support of <i>x</i>.</td></tr><tr><td><b><i>y</i></b></td><td>F<sub><i>q</i><sup><i>n</i>−<i>k</i></sub></sub><sup><i>k</i></sup></td><td>Public syndrome.</td></tr><tr><td><b><i>a</i></b></td><td>F<sub><i>q</i><sup><i>r</i>−<i>1</i></sub></sub><sup><i>r</i></sup></td><td>Vector used in the MPC rank checking protocol.</td></tr><tr><td><b><i>w</i></b></td><td>F<sub><i>q</i><sup><i>r</i>−<i>1</i></sub></sub><sup><i>r</i></sup></td><td>Vector used in the MPC rank checking protocol.</td></tr><tr><td><b><i>γ</i></b></td><td>F<sub><i>q</i><sup><i>n</i></sub></sub><sup><i>n</i></sup></td><td>Vector from the first challenge.</td></tr><tr><td><i>c</i></td><td>F<sub><i>q</i><sup><i>m</i></sub></sub></td><td>Element used in the MPC rank checking protocol.</td></tr><tr><td><i>z</i></td><td>F<sub><i>q</i><sup><i>m</i></sub></sub></td><td>Element used in the MPC rank checking protocol.</td></tr><tr><td><i>ε</i></td><td>F<sub><i>q</i><sup><i>m</i></sub></sub></td><td>Element from the first challenge.</td></tr></tbody></table>

The leaf shares of the above vectors and elements are noted with an array index *i* (for example $\mathbf{a}[i]$).

The main shares of the above vectors and elements are noted with an hat and an array index *δ* (for example $\hat{\mathbf{a}}[\delta]$).

<caption>Table 1: Description of low level notation used in our scheme</caption>
## 4.2 Operations on finite field elements

### Representation of finite field elements

In this document we always have $\mathbb{F}_{q^m} = \mathbb{F}_{2^m}$. We define $\mathbb{F}_{q^m}$ as $\mathbb{F}_2[X]/\langle P \rangle$ where $P$ is a sparse irreducible polynomial of degree $m$. Table 2 describes the chosen polynomials.

<table><caption>Table 2: Polynomials used to define the field $\mathbb{F}_{q^m}$.</caption><thead><tr><th>m</th><th>P</th></tr></thead><tbody><tr><td>31</td><td>X<sup>31</sup> + X<sup>3</sup> + 1</td></tr><tr><td>37</td><td>X<sup>37</sup> + X<sup>6</sup> + X<sup>4</sup> + X + 1</td></tr><tr><td>43</td><td>X<sup>43</sup> + X<sup>6</sup> + X<sup>4</sup> + X<sup>3</sup> + 1</td></tr></tbody></table>

Elements of $\mathbb{F}_{q^m}$ are represented in the polynomial basis. An array of $l = \lfloor \frac{m}{8} \rfloor$ bytes $[b_1, \dots, b_l]$ is used to store an element $u$ of $\mathbb{F}_{q^m}$. Each byte $b_i$ can be converted into a bitstring $\beta_1, \dots, \beta_8$ where $\beta_j = (b_i \gg j) \& 0x1$.

Let $\beta_1, \dots, \beta_{8l}$ be the bitstring stored in the byte array $[b_1, \dots, b_l]$, then:

$$u = \sum_{i=1}^{m} \beta_i X^{i-1}$$

### Converting a byte stream into an element of $\mathbb{F}_{q^m}$

When sampling randomness, we want to convert a byte stream into elements of $\mathbb{F}_{q^m}$. Sampling an element $u$ is done as the following way:

- Obtain $l = \lfloor \frac{m}{8} \rfloor$ bytes from the stream. Let $\beta_1, \dots, \beta_{8l}$ be the obtained bitstring.

- Set $u = \sum_{i=1}^{m} \beta_i X^{i-1}$.

To sample an array of $\mathbb{F}_{q^m}$ elements of length $n$ we simply repeat this process $n$ times, requiring $n \times \lfloor \frac{m}{8} \rfloor$ bytes $b$ of randomness. We refer to this process as $\text{FqmArrayFromBytes}(b)$.

To convert an array $\mathbf{y}$ of $n$ elements in $\mathbb{F}_{q^m}$ into a byte array, we simply revert this process, writing the values of the bits $\beta_1, \dots, \beta_{8l}$ for each element of $\mathbb{F}_{q^m}$ and repeating the process $n$ times. We refer to this process as $\text{FqmArrayToBytes}(\mathbf{y})$.

### Compacting arrays of $\mathbb{F}_{q^m}$ elements

In order to obtain a more compact representation (for values that will be sent over the network for example), we want to use a more compact representation for arrays of $\mathbb{F}_{q^m}$ elements.

Let $\mathbf{y}$ be an array of $n \mathbb{F}_{q^m}$ elements. Instead of representing each $\mathbb{F}_{q^m}$ element in a fixed number of bytes, we concatenate the $n$ bitstring obtained from the $y_i$ into a bitstring of
length $nm$. This process thus requires ⌈ $\frac{nm}{8}$ ⌉ bytes instead of $n \times \lfloor \frac{m}{8} \rfloor$ for representing the whole array.

We refer to these subroutines as FqmArrayToString(y) and FqmArrayFromString(str) respectively.

### Computing the weight of an array of $\mathbb{F}_{q^m}$ elements

The following algorithm computes the rank weight of an $\mathbb{F}_{q^m}$-vector.

**Algorithm 1 GetRankWeight**

**Input:** A vector $\boldsymbol{x} \in \mathbb{F}_{q^m}^n$ of length $n$

**Output:** Its rank weight $r \in \mathbb{N}$

1. Initialize a new zero matrix $M \in \mathbb{F}_q^{m \times n}$.

2. **for** $j \in [n]$ **do**

3. Fill the $j$-th column of $M$ with the coefficients of $\boldsymbol{x}[j]$ seen as a polynomial.

$$ \boldsymbol{x}[j] = \sum_{i=1}^{m} M[i][j] X^{i-1} $$

4. **return** Rank($M$)

### Computing an annihilator polynomial

We use the procedure from [Loi07, Ch. 3, Sec. 2.4] to compute the coefficients of a linearized polynomial given its roots.

**Algorithm 2 ComputeAnnihilatorPolynomial**

**Input:** Support $\mathbf{supp} \in \mathbb{F}_{q^m}^r$ of rank $r$

**Output:** Annihilator polynomial $P \in \mathbb{F}_{q^m}^r[X]$ such that for all $u \in \langle \mathbf{supp} \rangle$, $P(u) = 0$

$$ P_1 = X^q - \mathbf{supp}[0]^{q-1} $$

**for** $i$ from 1 to $r$ **do**

$$ T = P_i^q $$

$$ \mathit{eval} = P_i(\mathbf{supp}[i]) $$

$$ P_{i+1} = \mathit{eval}^{q-1} P_i + T $$

**return** $P_{r+1}$

### 4.3 Randomness generators and hash functions

- $\text{RandomBytes}(\ell)$ is instanciated using the NIST provided `randombytes` function, it returns $\ell$ bytes from system entropy;

- PRG is a psuedorandom generator instanciated using `SHAKE-128` for security category 1 and `SHAKE-256` otherwise. It offers two invocable functions:

- PRG.Init(seed) initializes the internal state of the generator with a seed,
* `PRGwert(ℓ)` outputs `ℓ` bytes from the generator and updates its internal state.

- Hash functions are instantiated using `SHA3-256`, `SHA3-384` or `SHA3-512` for security categories 1, 3 and 5 respectively.

## 4.4 Sampling routines

The routines presented in this subsection sample from a seed some set of elements needed in the scheme.

**Algorithm 3 SampleFqmVector**

**Input:** Length $n$, a seed `seed`

**Output:** $x \in \mathbb{F}_{q^m}^n$

PRG.Init(seed)

xbytes = PRGwert(n \times ⌊m/8⌋)

x = FqmArrayFromBytes(xbytes)

return x

**Algorithm 4 SampleFqmMatrix**

**Input:** Dimensions $k \times n$, a seed `seed`

**Output:** $A \in \mathbb{F}_{q^m}^{k \times n}$

PRG.Init(seed)

for $i \in [k]$ do

xbytes = PRGwert(n \times ⌊m/8⌋)

Ai,* = FqmArrayFromBytes(xbytes)

return A

The following algorithm samples a support of rank weight $r$, represented by a basis $supp \in \mathbb{F}_{q^m}^r$. The support always contain the element $1 \in \mathbb{F}_{q^m}$, as explained in Section 3. The algorithm further samples a vector $x$ of support $supp$.
Algorithm 5 SampleFqmVectorAndSupport

Input: Length $n$, rank weight $r$, a seed `seed`

Output: $x \in \mathbb{F}_{q^m}^n$ of rank weight $r$ and its support $supp \in \mathbb{F}_{q^m}^r$

1: PRG.Init(seed)

2: r_bytes = r ⌊m/8⌋

3: repeat

4: supp[1] = 1

5: supp[2, r] = FqmArrayFromBytes(PRG.GetBytes(r_bytes))

6: until GetRankWeight(supp) = r

7: x = (0, ..., 0)

8: repeat

9: rand =PRG.GetBytes( ⌊nr/8⌋ )

10: Convert `rand` into a bitstring `randbits` of length $8^{\lceil nr/8 \rceil}$

11: for $i \in [n]$ do

12: for $j \in [r]$ do

13: $x_i = x_i + \text{randbits}[ir + j] \cdot \text{supp}[j]$

14: until GetRankWeight($x$) = $r$

15: return $x$, `supp`

▷ The support always contains one

▷ Sampling the rest of the support

▷ Initialize $x$ with zeros

Algorithm 6 SampleSeeds

Input: Length $\ell$, Number of seeds $\tau$, a seed `seed`

Output: $(seed^{(e)})_{e \in [\tau]} \in (\{0, 1\}^{\ell})^{\tau}$

PRG.Init(seed)

for $i \in [\tau]$ do

$seed^{(e)} = \text{PRG. GetBytes}(\ell)$

return $(seed^{(e)})_{e \in [\tau]}$

Algorithm 7 SampleShares

Input: A seed `seed`

Output: A set of shares $(x_B, \beta, a, c) \in \mathbb{F}_{q^m}^k \times \mathbb{F}_{q^m}^{r-1} \times \mathbb{F}_{q^m}^{r-1} \times \mathbb{F}_{q^m}$

PRG.Init(seed)

xbytes = PRG. GetBytes($k \times \lceil m/8 \rceil$)

$x_B = \text{FqmArrayFromBytes}(xbytes)$

bbytes = PRG. GetBytes((r - 1) × ⌊m/8⌋)

$\beta = \text{FqmArrayFromBytes}(bbytes)$

abytes = PRG. GetBytes((r - 1) × ⌊m/8⌋)

$a = \text{FqmArrayFromBytes}(abytes)$

cbytes = PRG. GetBytes(1 × ⌊m/8⌋)

$c = \text{FqmArrayFromBytes}(cbytes)$ [0]

return $x$
**Algorithm 8 SampleFirstChallenge**

**Input:** A seed *seed*

**Output:** A set of first challenges $(\gamma^{(e)}, \epsilon^{(e)})_{e \in [\tau]} \in (\mathbb{F}_{q^m}^n \times \mathbb{F}_{q^m})^\tau$

PRG.Init(seed)

for $e \in [\tau]$ do

xbytes = PRG.GetBytes((n + 1) × ⌊$\frac{m}{8}$⌋)

$\gamma^{(e)} = \text{FqmArrayFromBytes}(\text{xbytes}[..n])$

$\epsilon^{(e)} = \text{FqmArrayFromBytes}(\text{xbytes}[n+1])[0]$

return $(\gamma^{(e)}, \epsilon^{(e)})_{e \in [\tau]}$

**Algorithm 9 SampleSecondChallenge**

**Input:** A seed *seed*

**Output:** A set of second challenges $(i^{*(e)})_{e \in [\tau]} \in [N]^\tau$

PRG.Init(seed)

for $e \in [\tau]$ do

$i^{*(e)} = \text{PRG.GetBytes}(1) \mod N$

return $(i^{*(e)})_{e \in [\tau]}$

## 4.5 MPC routines

**Algorithm 10 MPC-RSD ComputeAlpha**

**Input:**

- A set of shares $(\mathbf{x}, \mathbf{a})$

- A protocol challenge $((\gamma_j)_{j \in [1,n]}, \epsilon)$

**Output:** $\alpha$

1: **for** $s \in [1, r-1]$ **do**

2: &nbsp;&nbsp;&nbsp;&nbsp; $w_k = \sum_{j=1}^{n} \gamma_j (\mathbf{x}_j^{q^k} - \mathbf{x}_j)$

3: &nbsp;&nbsp;&nbsp;&nbsp; $\alpha = \epsilon \cdot \mathbf{w} + \mathbf{a}$

4: **return** $\alpha$
**Algorithm 11 MPC-RSD Exec**

**Input:**

- A set of main shares $(\hat{x}_B[\delta], \hat{\beta}[\delta], \hat{a}[\delta], \hat{c}[\delta])_{\delta \in [D]}$

- A protocol challenge $((\gamma_j)_{j \in [1,n]}, \epsilon)$

- A full value $\alpha$

- The public matrix $H$ and the public syndrome $y$

**Output:** $(\hat{\alpha}[\delta], \hat{v}[\delta])_{\delta \in [D]}$

1: **for** $\delta \in [D]$ **do**

2: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{x}_A[\delta] = y - H\hat{x}_B[\delta]$

3: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{x}[\delta] = (\hat{x}_A[\delta] || \hat{x}_B[\delta])$

4: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{\alpha}[\delta] = \text{MPC-RSD}\_\text{ComputeAlpha}(\hat{x}[\delta], \hat{a}[\delta], (\gamma_j)_{j \in [1,n]}, \epsilon)$

5: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{z}[\delta] = - \sum_{j=1}^n \gamma_j (\hat{x}_j[\delta]^{q_r} - \hat{x}_j[\delta])$

6: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{v}[\delta] = \epsilon \cdot \hat{z}[\delta] - \langle \alpha, \hat{\beta}[\delta] \rangle - \hat{c}[\delta]$

7: **return** $(\hat{\alpha}[\delta], \hat{v}[\delta])_{\delta \in [D]}$

## 4.6 Hypercube routines

The $N = 2^D$ leaf shares are arranged on a $D$-dimensional hypercube of side length 2. An index $i \in [N]$ is positioned according to the binary representation of $i - 1 \in [0, 2^D - 1]$. The $\delta$-th coordinate of $i$ in the hypercube is the $\delta$-th least significant bit of the binary representation of $i - 1$, i.e. $\text{bit}(i - 1, \delta)$.

A main share of index $\delta$ is the sum of all leaf shares in the hyperface of the hypercube comprising all vertices whose $\delta$-th coordinate is zero.

**Algorithm 12 Hypercube MainShares-Compute**

**Input:** A set of leaf shares $(\boldsymbol{x}_B[i], \boldsymbol{\beta}[i], \boldsymbol{a}[i], c[i])_{i \in [N]}$ where $N = 2^D$

**Output:** A set of main shares $(\hat{\boldsymbol{x}}_B[\delta], \hat{\boldsymbol{\beta}}[\delta], \hat{\boldsymbol{a}}[\delta], \hat{c}[\delta])_{\delta \in [D]}$

1: **for** $\delta \in [D]$ **do**

2: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{x}_B[\delta] = \sum_{\text{bit}(i-1,\delta)=0}^{i \in [N]} \boldsymbol{x}_B[i]$

3: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{\beta}[\delta] = \sum_{\text{bit}(i-1,\delta)=0}^{i \in [N]} \boldsymbol{\beta}[i]$

4: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{a}[\delta] = \sum_{\text{bit}(i-1,\delta)=0}^{i \in [N]} \boldsymbol{a}[i]$

5: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{c}[\delta] = \sum_{\text{bit}(i-1,\delta)=0}^{i \in [N]} c[i]$
**Algorithm 13 Hypercube.**MainAlphaAndV-Compute

**Input:** A set of leaf shares $(\alpha[i], v[i])_{i \in [N]}$ where $N = 2^D$

**Output:** A set of main shares $(\hat{\alpha}[\delta], \hat{v}[\delta])_{\delta \in [D]}$

1: for $\delta \in [D]$ do

2: $\hat{\alpha}[\delta] = \sum_{i \in [N]} \alpha[i]$

3: $\hat{v}[\delta] = \sum_{\text{bit}(i-1, \delta)=0}^{\text{bit}(i-1, \delta)=0} v[i]$

## 4.7 Key parsing routines

**Algorithm 14 ParseSecretKey**

**Input:** Secret key sk

**Output:** $H, x, y$ and the annihilator polynomial $\beta$

1: $(sk\_seed, pk\_seed) = sk$

2: $(x, supp) = \text{SampleFqmVectorAndSupport}(n, r, sk\_seed)$

3: $H = \text{SampleFqmMatrix}(n - k, k, pk\_seed)$

4: $y = (I|H)x$

5: $\beta = \text{ComputeAnnihilatorPolynomial}(supp)$

6: return $(H, x, y, \beta)$

**Algorithm 15 ParsePublicKey**

**Input:** Public key pk

**Output:** $H, y$

1: $(pk\_seed, y\_string) = pk$

2: $H = \text{SampleFqmMatrix}(n - k, k, pk\_seed)$

3: $y = \text{FqmArrayFromString}(y\_string)$

4: return $(H, y)$

## 4.8 PRG tree routines

**Algorithm 16 PRGTreeExpand**

**Input:** A root seed $seed$, a number of parties $N = 2^D$, a salt and an iteration index $e$

**Output:** A family of seeds $(seed_i)_{i \in [N]}$

1: if $D = 0$ then

2: return seed

3: else

4: $(seed\_left, seed\_right) = \text{Hash}(DS\_T, salt, e, seed)$

5: $(seed_i)_{i \in [1, N/2]} = \text{PRGTreeExpand}(seed\_left, N/2, salt, e)$

6: $(seed_i)_{i \in [N/2+1, N]} = \text{PRGTreeExpand}(seed\_right, N/2, salt, e)$

7: return $(seed_i)_{i \in [N]}$
Algorithm 17 PRGPartialTreeReveal

Input: A root seed seed, a number of parties $N = 2^D$, a salt and an iteration index $e$, a hidden index $i^*$

Output: A partial tree, i.e. a family of seeds $(seed_i)_{i \in [D]}$

1: $(seed\_left, seed\_right) = \text{Hash}(\text{DS\_T}, \text{salt}, e, seed)$
2: if $D = 1$ then
3:     if $i^* = 1$ then
4:         return $seed\_right$
5:     else
6:         return $seed\_left$
7: else
8:     if $i^* \le N/2$ then
9:         $(seed_i)_{i \in [1, D-1]} = \text{PRGPartialTreeReveal}(seed\_left, N/2, \text{salt}, e, i^*)$
10:    seed$_D = seed\_right$
11: else
12:    seed$_1 = seed\_left$
13:    $(seed_i)_{i \in [2, D]} = \text{PRGPartialTreeReveal}(seed\_right, N/2, \text{salt}, e, i^* - N/2)$
14:    return $(seed_i)_{i \in [D]}$

Algorithm 18 PRGPartialTreeExpand

Input: A partial tree, i.e. a family of seeds $(seed_i)_{i \in [D]}$, a salt and an iteration index $e$, a hidden index $i^*$

Output: All seeds but one $(seed_i)_{i \in [N], i \neq i^*}$

1: Let $N = 2^D$
2: if $i^* \le N/2$ then
3:     $(seed_i)_{i \in [N/2], i \neq i^*} = \text{PRGPartialTreeExpand}((seed_i)_{i \in [D-1]})$
4:     $(seed_i)_{i \in [N/2+1, N]} = \text{PRGTreeExpand}(seed_D, N/2, \text{salt}, e)$
5: else
6:     $(seed_i)_{i \in [N/2]} = \text{PRGTreeExpand}(seed_1, N/2, \text{salt}, e)$
7:     $(seed_i)_{i \in [N/2+1, N], i \neq i^*} = \text{PRGPartialTreeExpand}((seed_i)_{i \in [2, D]})$
8: return $(seed_i)_{i \in [N], i \neq i^*}$

4.9 Protocol specification

Algorithm 19 RYDE_Keygen

Input: Security level $\lambda$

Output: Secret key sk, public key pk

1: sk\_seed = RandomBytes($\lambda$)
2: pk\_seed = RandomBytes($\lambda$)
3: ($x, \_\_$) = SampleFqmVectorAndSupport($n, r, sk\_seed$)
4: $H = \text{SampleFqmMatrix}(n - k, k, pk\_seed)$
5: $y = (I|H)x$
6: pk = pk\_seed || FqmArrayToString($y$)
7: sk = sk\_seed || pk\_seed
8: return sk, pk
Algorithm 20 RYDE_Sign

Input: Secret key sk, public key pk, message $m \in \{0, 1\}^*$

Output: Signature $\sigma \in \{0, 1\}^*$

▷ Step 0: Parse keys

1: $(H, x, y, \beta) = \text{ParseSecretKey}(sk)$

2: Define $x_B$ as the last $k$ coordinates of $x$.

▷ Step 1: Commitment

3: $\text{salt} = \text{RandomBytes}(2\lambda)$

4: $\text{mseed} = \text{RandomBytes}(\lambda)$

5: $\text{md} = \text{Hash}(\text{DS\_M}, m)$

6: $(\text{seed}^{(e)})_{e \in [\tau]} = \text{SampleSeeds}(\lambda, \tau, \text{mseed})$

7: for $e \in [\tau]$ do

8:   $(\text{seed}_i^{(e)})_{i \in [N]} = \text{PRGTreeExpand}(\text{seed}^{(e)}, N, \text{salt}, e)$

9:   for $i \in [N-1]$ do

10:   $(x_B^{(e)}[i], \beta^{(e)}[i], \mathbf{a}^{(e)}[i], c^{(e)}[i]) = \text{SampleShares}(\text{seed}_i^{(e)})$

11:   $\text{cmt}_i^{(e)} = \text{Hash}(\text{DS\_C}, \text{salt}, e, i, \text{seed}_i^{(e)})$

12:   $\mathbf{a}^{(e)}[N] = \text{SampleFqmVector}(\text{seed}_N^{(e)}, r-1)$

13:   $\mathbf{a}^{(e)} = \sum_{i \in [N]} \mathbf{a}^{(e)}[i]$

14:   $x_B^{(e)}[N] = x_B - \sum_{i=1}^{N-1} x_B^{(e)}[i]$

15:   $\beta^{(e)}[N] = \beta - \sum_{i=1}^{N-1} \beta^{(e)}[i]$

16:   $c^{(e)}[N] = -\langle \mathbf{a}^{(e)}, \beta \rangle - \sum_{i=1}^{N-1} c^{(e)}[i]$

17:   $\text{cmt}_N^{(e)} = \text{Hash}(\text{DS\_C}, \text{salt}, e, N, \text{seed}_i^{(e)}, x_B^{(e)}[N], \beta^{(e)}[N], c^{(e)}[N])$

18:   $(\hat{x}_B^{(e)}[\delta], \hat{\beta}^{(e)}[\delta], \hat{\mathbf{a}}^{(e)}[\delta], \hat{c}^{(e)}[\delta])_{\delta \in [D]} = \text{Hypercube}\_\text{MainShares-Compute}((x_B^{(e)}[i], \beta^{(e)}[i], \mathbf{a}^{(e)}[i], c^{(e)}[i])_{i \in [N]}$

19:   $h_1 = \text{Hash}(\text{md}, \text{pk}, \text{salt}, \text{DS\_1}, \text{cmt}_1^{(1)}, \dots, \text{cmt}_N^{(1)}, \text{cmt}_1^{(2)}, \dots, \text{cmt}_N^{(\tau)}, \dots, \text{cmt}_N^{(\tau)}) \quad \triangleright \text{Commit hypercube}$

▷ Step 2: First challenge

20: $(\gamma^{(e)}, \epsilon^{(e)})_{e \in [\tau]} = \text{SampleFirstChallenge}(h_1)$

▷ Step 3: First response

21: for $e \in [\tau]$ do

22:   $\mathbf{a}^{(e)} = \text{MPC-RSD}\_\text{ComputeAlpha}(\mathbf{x}, \mathbf{a}^{(e)}, \gamma^{(e)}, \epsilon^{(e)})$

23:   $(\hat{\mathbf{a}}^{(e)}[\delta], \hat{v}^{(e)}[\delta])_{\delta \in [D]} = \text{MPC-RSD}\_\text{Exec}[(\hat{x}_B^{(e)}[\delta], \hat{\beta}^{(e)}[\delta], \hat{\mathbf{a}}^{(e)}[\delta], \hat{c}^{(e)}[\delta])_{\delta \in [D]}, \gamma^{(e)}, \epsilon^{(e)}, \mathbf{a}^{(e)}, H, y]$

24:   $h_2 = \text{Hash}(\text{md}, \text{pk}, \text{salt}, h_1, \text{DS\_2}, (\mathbf{a}^{(e)}, (\hat{\mathbf{a}}^{(e)}[\delta], \hat{v}^{(e)}[\delta])_{\delta \in [D]})_{e \in [\tau]}$

▷ Step 4: Second challenge

25: $(i^{*(e)})_{e \in [\tau]} = \text{SampleSecondChallenge}(h_2)$

▷ Step 5: Second response

26: for $e \in [\tau]$ do

27: $\text{ptree}^{(e)} = \text{PRGPartialTreeReveal}(\text{seed}^{(e)}, i^{*(e)})$

28:   $x_A^{(e)}[i^{*(e)}] = \begin{cases} y - Hx_B^{(e)}[i^{*(e)}] & \text{if } i^{*(e)} = 1 \\ -Hx_B^{(e)}[i^{*(e)}] & \text{otherwise} \end{cases}$

29:   $x_A^{(e)}[i^{*(e)}] = (x_A^{(e)}[i^{*(e)}] || x_B^{(e)}[i^{*(e)}])$

30:   MPC-RSD\_ComputeAlpha($x_A^{(e)}[i^{*(e)}]$, $\mathbf{a}^{(e)}[i^{*(e)}]$, $\gamma^{(e)}$, $\epsilon^{(e)}$)

31:   if $i^{*(e)} = N$ then

32:   $\text{rsp}^{(e)} = (\text{ptree}^{(e)}, \text{cmt}_{i^{*(e)}}^{(e)}, \mathbf{a}^{(e)}[i^{*(e)}], \mathbf{0}, \mathbf{0}, \mathbf{0})$

33:   else

34:   $\text{rsp}^{(e)} = (\text{ptree}^{(e)}, \text{cmt}_{i^{*(e)}}^{(e)}, \mathbf{a}^{(e)}[i^{*(e)}], x_B^{(e)}[N], \beta^{(e)}[N], c^{(e)}[N])$

▷ Step 6: Signature

35: return $\sigma = (\text{salt}, h_1, h_2, (\text{rsp}^{(e)})_{e \in [\tau]})$

▷ Compute leaf shares

▷ Compute final leaf shares
Algorithm 21 RYDE_Verify

Input: Public key pk, message $m \in \{0, 1\}^*$, signature $\sigma \in \{0, 1\}^*$

Output: ACCEPT or REJECT

▷ Step 0: Parse keys

1: $(\mathbf{H}, \mathbf{y}) = \text{ParsePublicKey}(\text{pk})$

▷ Step 1: Parse challenges

2: $(\gamma^{(e)}, \epsilon^{(e)})_{e \in [\tau]} = \text{SampleFirstChallenge}(h_1)$

3: $(i^{*(e)})_{e \in [\tau]} = \text{SampleSecondChallenge}(h_2)$

4: for $e \in [\tau]$ do

5: if $i^{*(e)} = N$ then

6: Check that $(\mathbf{x}_B^{(e)}[N], \beta^{(e)}[N], c^{(e)}[N]) = (0, 0, 0)$. If not, return REJECT.

▷ Step 2: Recompute $h_1$

7: $\text{md} = \text{Hash}(\text{DS\_M}, m)$

8: for $e \in [\tau]$ do

9: $(\text{seed}_i^{(e)})_{i \in [N], i \neq i^{*(e)}} = \text{PRGPartialTreeExpand}(\text{ptree}^{(e)}, N, \text{salt}, e)$

10: for $i \in [N], i \neq i^{*(e)}$ do

11: if $i \neq N$ then

12: $(\mathbf{x}_B^{(e)}[i], \beta^{(e)}[i], \mathbf{a}^{(e)}[i], c^{(e)}[i]) = \text{SampleShares}(\text{seed}_i^{(e)})$

13: $\text{cmt}_i^{(e)} = \text{Hash}(\text{DS\_C}, \text{salt}, e, i, \text{seed}_i^{(e)})$

14: else

15: $\mathbf{a}^{(e)}[N] = \text{SampleFqmVector}(\text{seed}_N^{(e)}, r-1)$

16: $\text{cmt}_N^{(e)} = \text{Hash}(\text{DS\_C}, \text{salt}, e, N, \text{seed}_i^{(e)}, \mathbf{x}_B^{(e)}[N], \beta^{(e)}[N], c^{(e)}[N])$

17: $\bar{h}_1 = \text{Hash}(\text{DS\_1}, \text{md}, \text{pk}, \text{salt}, \text{cmt}_1^{(1)}, \dots, \text{cmt}_N^{(1)}, \text{cmt}_1^{(2)}, \dots, \text{cmt}_N^{(\tau)}, \dots, \text{cmt}_N^{(\tau)})$

▷ Step 3: Recompute $h_2$

18: for $e \in [\tau]$ do

19: for $i \in [N], i \neq i^{*(e)}$ do

20: $\mathbf{x}_A^{(e)}[i] = \begin{cases} \mathbf{y} - H\mathbf{x}_B^{(e)}[i] & \text{if } i=1 \\ -H\mathbf{x}_B^{(e)}[i] & \text{otherwise} \end{cases}$

21: $\mathbf{x}_A^{(e)}[i] = (\mathbf{x}_A^{(e)}[i] || \mathbf{x}_B^{(e)}[i])$

22: $z^{(e)}[i] = - \sum_{j=1}^{n} \gamma_j^{(e)} (\mathbf{x}_j^{(e)}[i]^{q_r} - \mathbf{x}_j^{(e)}[i])$

23: $\alpha^{(e)}[i] = \text{MPC-RSD}\_\text{ComputeAlpha}(\mathbf{x}^{(e)}[i], \mathbf{a}^{(e)}[i], \gamma^{(e)}, \epsilon^{(e)})$

24: $\alpha^{(e)} = \sum_i \alpha^{(e)}[i]$

25: for $i \in [N], i \neq i^{*(e)}$ do

26: $v^{(e)}[i] = \epsilon^{(e)} \cdot z^{(e)}[i] - \langle \alpha^{(e)}, \beta^{(e)}[i] \rangle - c^{(e)}[i]$

27: $v^{(e)}[i^{*(e)}] = - \sum_{i \neq i^{*(e)}} v^{(e)}[i]$

28: $(\hat{\alpha}^{(e)}[\delta], \hat{v}^{(e)}[\delta])_{\delta \in [D]} = \text{Hypercube}\_\text{MainAlphaAndV}\_\text{Compute}((\alpha^{(e)}[i], v^{(e)}[i])_{i \in [N]})$

29: $\bar{h}_2 = \text{Hash}(\text{DS\_2}, \text{md}, \text{pk}, \text{salt}, h_1, (\alpha^{(e)}, (\hat{\alpha}^{(e)}[\delta], \hat{v}^{(e)}[\delta]))_{\delta \in [D]})_{e \in [\tau]}$

▷ Step 4: Verify commitments

30: return $\bar{h}_1 \stackrel{?}{=} h_1 \land \bar{h}_2 \stackrel{?}{=} h_2$
# 5 Parameter Sets

The Rank Syndrome Decoding problem has the following parameters:

- $q \in \mathbb{N}$ - the order of the base field;

- $m \in \mathbb{N}$ - the extension degree of the extension field $\mathbb{F}_{q^m}$;

- $n \in \mathbb{N}$ - the length of the code $\mathcal{C}$;

- $k \in \mathbb{N}$ - the dimension of the code;

- $r \in \mathbb{N}$ - the rank of the vector $\mathbf{x}$.

The other parameters of RYDE include:

- $N \in \mathbb{N}$ - the number of parties of the MPC protocol;

- $\tau \in \mathbb{N}$ - the number of parallel repetitions;

- $\eta \in \mathbb{N}$ - the extension degree for the MPC protocol (checking relations on $\mathbb{F}_{q^{m\cdot\eta}}$).

In order to choose the parameters, we need to consider:

- the security of the Rank-SD instance, i.e, the complexity of the attacks on the chosen parameters;

- the security of the signature scheme, i.e, the cost of a forgery;

- the size of the signature.

## 5.1 Additive-sharing scheme

The choice of the number $N \in \mathbb{N}$ of shares in the MPC protocol is a parameter which impacts performances: the bigger $N$, the slower the signing and verification, but the shorter the signature. We propose here two versions of the signature scheme with different values for $N$: we set $N = 256$ for a short version of the signature, and $N = 32$ for a fast version. There is also the number $\tau$ of repetitions required to reach the desired level of security, which increases the size and the signing time.

With additive sharing, we take $q = 2$ since it is the most efficient (and it does not impose a constraint on the number of parties unlike with threshold sharing). The choice of $(q, m, n, k, r)$ was then made in order to have the necessary security in regards to the considered attacks. As for the choice of $\tau$, we need to choose it such that our signature scheme resists to the forgery attack described in [KZ20].

We add a parameter $\eta$ in the signature: the degree of the extension field on which the relations are checked in the MPC protocol. While it increases the quantity of information to transmit per round, it also increases the soundness of the zero-knowledge proof thus reducing the number of necessary repetitions $\tau$. We choose for each set of parameters the optimal value of $\eta$ with respect to the signature size.
Parameters are chosen based on the effectiveness of existing attacks on the Rank-SD problem (see section 9.2). We remind that the security levels of the signature 1, 3 and 5 correspond respectively to the security of AES-128, AES-192 and AES-256. The following table presents our different sets of secured parameters in the case of additive shares:

<table><caption>Table 3: Parameters for RYDE with additive sharing, fast and short signatures</caption><thead><tr><th>Instance</th><th>NIST Security Level</th><th>q</th><th>m</th><th>n</th><th>k</th><th>r</th><th>N</th><th>η</th><th>τ</th><th>sk</th><th>pk</th><th>σ</th></tr></thead><tbody><tr><td>RYDE-128F</td><td>1</td><td>2</td><td>31</td><td>33</td><td>15</td><td>10</td><td>32</td><td>1</td><td>30</td><td>32 B</td><td>86 B</td><td>7.446 kB</td></tr><tr><td>RYDE-128S</td><td>1</td><td>2</td><td>31</td><td>33</td><td>15</td><td>10</td><td>256</td><td>1</td><td>20</td><td>32 B</td><td>86 B</td><td>5.956 kB</td></tr><tr><td>RYDE-192F</td><td>3</td><td>2</td><td>37</td><td>41</td><td>18</td><td>13</td><td>32</td><td>1</td><td>44</td><td>48 B</td><td>131 B</td><td>16.380 kB</td></tr><tr><td>RYDE-192S</td><td>3</td><td>2</td><td>37</td><td>41</td><td>18</td><td>13</td><td>256</td><td>1</td><td>29</td><td>48 B</td><td>131 B</td><td>12.933 kB</td></tr><tr><td>RYDE-256F</td><td>5</td><td>2</td><td>43</td><td>47</td><td>18</td><td>17</td><td>32</td><td>1</td><td>58</td><td>64 B</td><td>188 B</td><td>29.134 kB</td></tr><tr><td>RYDE-256S</td><td>5</td><td>2</td><td>43</td><td>47</td><td>18</td><td>17</td><td>256</td><td>1</td><td>38</td><td>64 B</td><td>188 B</td><td>22.802 kB</td></tr></tbody></table>

We refer to the design document for the computation of the theoretical sizes [BCDF$^{+23}$].

The main difference from the theoretical sizes relies on the packing of the vector: RYDE implementation individually packs each vector in the signature instead of a single vector containing all the vector coefficients.

## 5.2 Threshold-sharing scheme

In [BCDF$^{+23}$], two different variants of RYDE are described, using either an additive sharing scheme, or a threshold sharing scheme. The present specification contains only the additive sharing scheme, since, so far, “threshold MPCitH” does not bring a significant advantage compared to “hypercube MPCitH” for the considered protocol for the Rank-SD problem (we obtain roughly the same signature sizes while not being particularly faster with threshold techniques). This might however change in the future, in the case where threshold techniques were to improve.

# 6 Performance Analysis

This section provides performance measures of our implementations of RYDE.

*Benchmark platform.* The benchmarks have been performed on a machine running Ubuntu Server 22.04.2 LTS equipped with an Intel 13th Gen Intel (R) Core(TM) i9-13900K CPU running at 3000MHz and 64GB of RAM. All the experiments were performed with Hyper-Threading, Turbo Boost, and SpeedStep features disabled. The scheme has been compiled with GCC compiler (version 11.3.0) and uses the XKCP and OpenSSL (version 3.0.2) libraries.
For each parameter set, the results have been obtained by computing the mean from 25 random instances. To minimize biases from background tasks running on the benchmark platform, each instance has been repeated 25 times and averaged.

*Constant time.* The provided implementations have been implemented in a constant time way whenever relevant, and as such, the running time should not leak any information concerning sensitive data. For instance, all If branches depend on public data. Additionally, Valgrind (version 3.18.1) and LibVEX were used to check that there were no memory leaks on the implementation.

## 6.1 Reference Implementation

The performance concerning the reference implementation on the aforementioned benchmark platform are described in Table 4. The following optimization flags have been used during compilation:

- Concerning the C code: `-O3 -flto`.

- Concerning the ASM code (required in the XKCP library): `-x assembler-with-cpp -Wa,-defsym,old_gas_syntax=1 -Wa,-defsym,no_plt=1`.

<table><caption>Table 4: Thousand (K) and Million (M) of CPU cycles of RYDE reference implementation.</caption><thead><tr><th>Instance</th><th>Key Generation</th><th>Sign</th><th>Verify</th></tr></thead><tbody><tr><td>RYDE-128F</td><td>86.0 K</td><td>88.9 M</td><td>82.8 M</td></tr><tr><td>RYDE-128S</td><td>85.9 K</td><td>340.4 M</td><td>331.3 M</td></tr><tr><td>RYDE-192F</td><td>141.1 K</td><td>221.1 M</td><td>204.0 M</td></tr><tr><td>RYDE-192S</td><td>143.9 K</td><td>876.5 M</td><td>826.7 M</td></tr><tr><td>RYDE-256F</td><td>186.8 K</td><td>415.4 M</td><td>385.7 M</td></tr><tr><td>RYDE-256S</td><td>186.5 K</td><td>1500.3 M</td><td>1444.9 M</td></tr></tbody></table>

## 6.2 Optimized Implementation

The performance concerning the optimized implementation on the aforementioned benchmark platform are described in Table 5. The following optimization flags have been used during compilation:

- Concerning the C code: `-O3 -flto -mavx2 -mpclmul -msse4.2 -maes`.

- Concerning the ASM code (required in the XKCP library): `-x assembler-with-cpp -Wa,-defsym,old_gas_syntax=1 -Wa,-defsym,no_plt=1`.
<table><caption>Table 5: Thousand (K) and Million (M) of CPU cycles of RYDE optimized implementation.</caption><thead><tr><th>Instance</th><th>Key Generation</th><th>Sign</th><th>Verify</th></tr></thead><tbody><tr><td>RYDE-128F</td><td>33.2 K</td><td>5.4 M</td><td>4.4 M</td></tr><tr><td>RYDE-128S</td><td>33.1 K</td><td>23.4 M</td><td>20.1 M</td></tr><tr><td>RYDE-192F</td><td>48.4 K</td><td>12.2 M</td><td>10.7 M</td></tr><tr><td>RYDE-129S</td><td>48.5 K</td><td>49.6 M</td><td>44.8 M</td></tr><tr><td>RYDE-256F</td><td>71.9 K</td><td>26.0 M</td><td>22.7 M</td></tr><tr><td>RYDE-256S</td><td>72.0 K</td><td>105.5 M</td><td>94.9 M</td></tr></tbody></table>

## 7 Known Answer Test Values

Known Answer Test (KAT) values have been generated using the script provided by the NIST and can be retrieved in the KATs/ folder. Both reference and optimized implementations generate the same KATs. In addition, examples with intermediate values have also been provided in these folders. The intermediate values correspond with one execution calling the NIST-provided randombytes function seeded with zero.

Notice that one can generate the test files as mentioned above using the kat and verbose modes of the implementation, respectively. The procedure is detailed in the technical documentation (README file of the provided code).

## 8 Expected security strength

Our scheme relies on the hardness of solving a Rank-SD instance. We expect our parameters to offer the security required for each security category. For the hardness of solving a Rank-SD instance, we refer to the following section, as well as the design document [BCDF+23], where we describe the two best attacks on the Rank-SD problem, namely, the kernel attack and the Support Minor Modeling.

For the hardness of forging the signature, we refer to the following section and the design document, which gives the complexity of the attack on the Fiat-Shamir transform described in [KZ20]. This is the best attack on the Fiat-Shamir signature, and as such, this allows us to choose the parameters $\tau$ and $\eta$ accordingly.

As for the proof of the unforgeability of the scheme, we have the following result in the EUF-CMA model.

**Theorem 1.** Let the PRG used in the signature be $(t, \epsilon_{PRG})$-secure and assume an adversary running in time $t$ has advantage at most $\epsilon_{RSD}$ against the underlying Rank-SD problem. Let $H_0, H_1, H_2, H_3$, and $H_4$ be random oracles with output length $2\lambda$ bits. Let an adversary who makes $q_0, q_1, q_2, q_3, q_4, q_S$ queries to the random oracles and signing oracle respectively. The probability that the adversary running in time at most $t$ in producing an
existential forgery under chosen message attack (EUF-CMA) is upper-bounded as:

$$ \Pr(\text{forge}) \le \frac{3 \cdot (q + \tau \cdot N \cdot q_S)^2}{2 \cdot 2^\lambda} + \frac{q_S \cdot (q_S + 5q)}{2^\lambda} + q_S \cdot \tau \cdot \epsilon_{\text{PRG}} + \Pr(X + Y = \tau) + \epsilon_{\text{RSD}} $$

where: $\tau$ is the number of rounds of the signature, $X = \max_{i \in [0, q_2]} \{X_i\}$ where $X_i \sim \mathcal{B}(\tau, p)$, $Y = \max_{i \in [0, q_4]} \{Y_i\}$ where $Y_i \sim \mathcal{B}(\tau - X, \frac{1}{N})$ and $q = \max\{q_0, q_1, q_2, q_3, q_4\}$.

We refer to the design rationale document for the proof of the theorem and the formal definition of the EUF-CMA security of a signature.

To summarize, we have an EUF-CMA scheme, relying on the hardness of solving the Rank-SD scheme. The parameters are taken such that:

- Solving the Rank-SD instance chosen respects the NIST security level aimed at;

- Building the signature without knowing the secret key respects the NIST security level aimed at;

- Pairs of messages and signatures does not help an attacker to forge a signature

Our signature scheme relies on the security of hash functions and commitments functions as well. In the proofs for the security of the schemes, they are modeled as random oracles. In practice, we use SHAKE and SHA3, which are collision resistant and preimage resistant too. With Grover's algorithm, the complexity to find a preimage is of $O(\frac{n}{2})$ (for an hash function with an $n$ bits output), while collisions can be found in $O(2^{\frac{n}{3}})$ with Brassard's algorithm [BHT98]. However, this last algorithm is unlikely to perform better than $O(2^{\frac{n}{2}})$ in practice. Hence, as in many other cryptosystems, we consider here that a hash function with an output of $2 \cdot \lambda$ bits provides a security of $\lambda$ bits.

## 8.1 Resistance to quantum attacks

There exist two type of attacks for our problem: combinatorial and algebraic attacks.

Since combinatorial attacks rely for their exponential part on guessing special vector spaces of a whole space, they can be improved by a square root factor through the Grover algorithm, which basically means dividing by a factor 2 the exponential part of the complexity. For algebraic attacks, such an improvement cannot be obtained directly. Notice that for the type considered parameters close to the Gilbert-Varshamov bound, combinatorial and algebraic attack behave similarly. So that in practice, resistance to quantum attacks may imply roughly dividing by a factor 2 the classical security.

# 9 Analysis of known attacks

## 9.1 Kales and Zaverucha's attack against Fiat-Shamir Signatures

There are several attacks against signatures from zero-knowledge proofs obtained thanks to the Fiat-Shamir heuristic. [AABN02] propose an attack more efficient than the brute-force one for protocols with more than one challenge, i.e. for protocols of a minimum of 5 rounds.
Kales and Zaverucha describe in [KZ20] an approach which consists in guessing separately the two challenge of the protocol. It results in an additive cost rather than the expected multiplicative cost. The cost associated with forging a transcript that passes the proof of knowledge relies on achieving an optimal trade-off between the work needed for passing the first step and the work needed for passing the second step. Let $C_1$ and $C_2$ the respective cardinals to the first and second challenge sets, the probability $P_1$ of guessing at least $r$ of the $\tau$ first-round challenges correctly is given by the equation:

$$P_1 = \sum_{k=r}^{\tau} \binom{\tau}{k} \left(\frac{1}{C_1}\right)^k \left(\frac{C_1-1}{C_1}\right)^{\tau-k}$$

The optimal number of repetitions to achieve the attack is:

$$\tau' = \arg \min_{0 \le \tau' \le r} \left\{ \frac{1}{P_1} + C_2^{r-\tau'} \right\}$$

then the number of repetitions $\tau$ must be chosen such that this number allows to achieve the desired security.

In the case of the additive case, one obtains:

$$\text{cost}_{\text{forge}} = \min_{0 \le \tau' \le \tau} \left\{ \frac{1}{\sum_{i=\tau'}^{\tau} \binom{\tau}{i} p^i (1-p)^{\tau-i}} + N^{\tau-\tau'} \right\} \quad (1)$$

## 9.2 Combinatorial attacks against Rank-SD problem

We describe in this section the two most efficient combinatorial attacks against Rank-SD problem.

### 9.2.1 Enumeration of basis
Chabaud and Stern proposed an algorithm in [CS96] which solve the problem by enumerating the possible supports for the vector $\boldsymbol{x}$. For each of them, one must translate the equations in $\mathbb{F}_{q^m}$ to equations in $\mathbb{F}_q$ as follows.

If trying all the different possible supports in Hamming metric is inefficient due to their large number (there are $\binom{n}{\omega}$ vectors of weight $\omega$ in $\mathbb{F}_2^n$), this is a viable method in rank metric: there are approximately $q^{(m-r)r}$ linear subspaces in $\mathbb{F}_{q^m}$ of dimension $r$. Moreover, one can always make the assumption that 1 is in the support, since it is enough to multiply by an invertible constant in $\mathbb{F}_{q^m}$ to make it appear in the coefficients of $\boldsymbol{x}$. There are approximately $q^{(m-r)(r-1)}$ linear subspaces in $\mathbb{F}_{q^m}$ which contains 1.

One obtains a system that has $(n-k)m$ independent equations and $nr+m$ variables in $\mathbb{F}_q$. Thanks to the gaussian elimination, this system can be solved with $O((nr+m)^3)$ operations in $\mathbb{F}_q$. It is deduced that the complexity of this attack is upper bounded by $O((nr+m)^3q^{(m-r)(r-1)})$.
**9.2.2 GRS Algorithm** This method is an adaptation of the information set decoding attack used in Hamming metric. From the syndrome $\mathbf{y}$ of length $n-k$, the algorithm consists in guessing a set of $n-k$ coordinates which contains the support of the vector $\mathbf{x}$. One obtains $n-k$ equations and $n-k$ unknown coordinates of $\mathbf{x}$, which can be recovered by inverting an extracted matrix from $H$ of size $(n-k) \times (n-k)$.

In order to adapt this method to coding theory in rank metric, Gaborit, Ruatta and Schrek proposed in [GRS13] to consider a linear subspace in $\mathbb{F}_{q^m}$ of dimension $r' \ge r$, and hope that includes the support of the vector $\mathbf{x}$. The probability that $E$ of dimension $r$ is included in $E'$ of dimension $r'$ (for $r' \ge r$) is $q^{-(m-r')r}$.

Suppose one knows a subspace $E'$ of dimension $r'$ which contains $E = \text{Supp}(\mathbf{x})$. It is possible to recover $\mathbf{x}$ by solving a this linear system as long as: $r'n \le (n-k)m$ i.e. $r' \le \lfloor \frac{(n-k)m}{n} \rfloor$

Choosing the higher possible value $r = \lfloor \frac{(n-k)m}{n} \rfloor$, one gets the probability to obtain a suitable subspace $E'$ equal to $q^{-(m-r')}r = q^{-r\lfloor \frac{km}{n} \rfloor}$. As in the previous attack, one can recover $\mathbf{x}$ by executing gaussian elimination, which can be perform in $O((n-k)^3m^3)$ operations in $\mathbb{F}_q$. This attack can be achieved with an average complexity: $O((n-k)^3m^3q^{r\lfloor \frac{km}{n} \rfloor})$.

**9.2.3 An improvement of GRS Algorithm** The idea proposed in [AGHT18] is, instead of consider a linear subspace in $\mathbb{F}_{q^m}$ which contains 1, choose a completely random subspace $E'$. If $E'$ contains a subspace of the form $\alpha E$, with $\alpha \in \mathbb{F}_{q^m}^*$, then one can retrieve the code word as before.

At the cost of an increase in the dimension of the code ($k$ becomes $k+1$, since we multiply by an element $\alpha$ which does not belong to the code), we can obtain a new subspace that contains $\alpha E$.

This attack can be achieved with an average complexity: $O((n-k)^{\omega}m^{\omega}q^{r\lfloor \frac{(k+1)m}{n} \rfloor-m})$, where $\omega$ is in practice equal to 2.

**9.3 Algebraic attacks against Rank-SD problem**

Algebraic attacks amount to solve the system of equations $H\mathbf{x} = \mathbf{y}$ using computer algebra techniques like Gröbner basis. Today, the best algebraic modelings for solving the Rank-SD problem are the MaxMinors modeling [BBB$^+$20,BBC$^+$20] and the Support Minors modeling [BBC$^+$20,BBB$^+$22]. They can both benefits from a classical improvement that is the hybrid approach, that consists in specializing some variables with all possible values and solving the resulting system with less variables, but the same number of equations. In certain cases, the gain in complexity for solving the specialized system compared to the original one superseeds the lost in complexity coming from the exhaustive search.

*Hybrid methods* As shown in [BBB$^+$22, Section 5], solving a Rank-SD problem of parameters $(q, m, n, k, r)$ amount to solve $q^{ar}$ smaller Rank-SD problems of parameters $(q, m, n - a, k - a, r)$.
MaxMinors Modeling Let $\mathbf{H}, \mathbf{x}, \mathbf{y}$ be a Rank-SD problem with parameters $(q, m, n, k, r)$, i.e. $\mathbf{H} = (\mathbf{I} \ \mathbf{H}') \in \mathbb{F}_{q^m}^{(n-k) \times n}$ is uniformly sampled, $\mathbf{x} \in \mathbb{F}_{q^m}^n$ has rank exactly$^9$ $r$, and $\mathbf{y} = \mathbf{H}\mathbf{x}$.

The idea of the MaxMinors modeling from $[BBB^{+}20]$ is the following: let $\mathbf{E} = (E_1, \dots, E_r)$ be a basis of $\text{Supp}(\mathbf{x})$, and $\mathbf{X} = (x_{i,j}) \in \mathbb{F}_q^{r \times n}$ a matrix representing the coordinates of $\mathbf{x}$ in the basis $\mathbf{E}$, then $\mathbf{x}^{\top} = (E_1, \dots, E_r)\mathbf{X}$. Considering the extended code $\mathcal{C}'$ described in the previous section, and a parity-check $\mathbf{H}' \in \mathbb{F}_{q^m}^{(n-k-1) \times n}$ of this code, we have the relation :

$$ \mathbf{H}'\mathbf{x} = 0, \text{ i.e. } (E_1, \dots, E_r)\mathbf{X}\mathbf{H}'^{\top} = 0. $$

This implies that the matrix $\mathbf{X}\mathbf{H}'^{\top}$ is not full rank, and that all its maximal minors are equal to zero. By using the Cauchy-Binet formula that expresses the determinant of the product of two matrices $A \in \mathbb{K}^{r \times n}$ and $B \in \mathbb{K}^{n \times r}$ as

$$ |AB| = \sum_{T \subset \{1..n\}, \#T=r} |A|_{*,T} |B|_{T,*} \quad (2) $$

each of these maximal minors can be expressed as a linear combination of the maximal minors of the matrix $\mathbf{X}$. Using these minors as new variables, we obtain a system of $\binom{n-k-1}{r}$ linear equations in $\binom{n}{r}$ variables with coefficients over $\mathbb{F}_{q^m}$, that can be unfolded over $\mathbb{F}_q$ as $m\binom{n-k-1}{r}$ equations in the same number of variables (that are searched over $\mathbb{F}_q$).

It is possible to solve the Rank-SD problem with the MaxMinors modeling as soon as

$$ \left\{ \begin{array}{ll} m\binom{n-k-1}{r} \ge \binom{n}{r} - 1, & \text{if the system has 1 solution,} \\ m\binom{n-k-1}{r} \ge \binom{n}{r}, & \text{if the system has no solution.} \end{array} \right. \qquad (3) $$

It is possible to improve slightly the solving by puncturing the code on $p$ positions, as long as

$$ m\binom{n-p-k-1}{r} \ge \binom{n-p}{r} - 1. \qquad (4) $$

With the largest such $p$, the linear system has almost the same number of equations than variables. If (3) is not satisfied, then we use the hybrid approach and specialize $a \in \{0..k\}$ columns of $\mathbf{X}$. The final complexity of the MaxMinors attack is bounded by

$$ O\left(q^{ar}\binom{n-a-p}{r}^{\omega}\right) \qquad (5) $$

as $n \to \infty$, where $\omega$ is the linear algebra constant. In all our estimates, we use conservatively $\omega = 2$, see Table 6.

We observe in Figures 3, 4, 5 that this approach is efficient for small $r$'s, and becomes equivalent or worse than the combinatorial approach for $r$ around the Gibert-Varshamov bound, as in this case $a$ is close to $k$ (see Figure 2).

<footnote>$^9$ We assume the rank $r$ is known. Otherwise, we can try to solve for $r = 1, r = 2, \dots$ until we find the good $r$.</footnote>
<table><caption>Table 6: Complexity of the algebraic attacks for the proposed parameters. $a$ is the hybrid parameter, $p$ the number of columns on which the code is punctured. The complexities are given in $\log_2$ bit operations. We use $\omega = 2$.</caption><thead><tr><th>NIST security level</th><th>q</th><th>m</th><th>n</th><th>k</th><th>r</th><th>combi</th><th>a</th><th>p</th><th>C<sub>MM</sub></th><th>b</th><th>a</th><th>p</th><th>C<sub>SM+</sub></th></tr></thead><tbody><tr><td>1</td><td>2</td><td>31</td><td>33</td><td>15</td><td>10</td><td><b>148</b></td><td>12</td><td>2</td><td>153</td><td>1</td><td>11</td><td>0</td><td>155</td></tr><tr><td>3</td><td>2</td><td>37</td><td>41</td><td>18</td><td>13</td><td><b>217</b></td><td>15</td><td>2</td><td>238</td><td>2</td><td>14</td><td>0</td><td>241</td></tr><tr><td>5</td><td>2</td><td>43</td><td>47</td><td>18</td><td>17</td><td><b>284</b></td><td>15</td><td>2</td><td>308</td><td>-</td><td>-</td><td>-</td><td>317</td></tr></tbody></table>

- For the 256 bits of security parameters, the SM attack does not work: as it needs $a = k$, it amounts to a combinatorial attack

<figure><img src="image_2.png" /><figcaption>Fig. 2: Values of $a$ for the MaxMinors modeling, in terms of $r \in \{0..r_{GV}\}$ below the Gibert-Varshamov bound. The values are given for the three proposed parameter sets $(\lambda, m, n, k, r)$ equal to (128, 31, 33, 15, 10), (192, 37, 41, 18, 13), (256, 43, 47, 18, 17) with $q = 2$. The horizontal lines represent the value of $k$. The black points correspond to the selected value of $r$ for the proposed parameters.</figcaption></figure>

*The Support Minors modeling* The previous modeling is a linearization technique, that only works with a large hybrid parameter $a$ for large $r$. An alternative method is to rely on the Support Minors modeling, which was initially introduced in [BBC+20] to solve generic MinRank instances, and that uses a new set of variables. It has been adapted to instances coming from $\mathbb{F}_{q^m}$-linear codes in $[BBB^{+22}]$.

Write the received vector $v = -mG + x$ with $-mG \in C$ a codeword, and $\text{Rank}(x) = r$. Then, $x = v + mG = (E_1, \dots, E_r)C$ so that any row $r_i$ of $M(v + mG) \in \mathbb{F}_q^{m \times n}$ is in the row space of $C$. Therefore, all the maximal minors of the matrix $\binom{r_i}{C}$ are equal to 0. This system is described and analyzed in $[BBB^{+22}]$, where it is shown that it contains the previous equations from the MaxMinors modeling.
<figure><img src="image_3.png" /><figcaption>Fig. 3: Comparison of the MaxMinors complexity and the combinatorial attacks for the parameters $\lambda = 128$, $(2, 31, 33, 15)$ and $r \in \{2..10\}$. Only the values of the complexities with $a < k$ are plotted.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 4: Comparison of the MaxMinors complexity and the combinatorial attacks for the parameters $\lambda = 192$, $(2, 37, 41, 18)$ and $r \in \{1..13\}$. Only the values of the complexities with $a < k$ are plotted.</figcaption></figure>

It is conjectured in [BBB+22], based on a careful theoretical analysis of the system and some experimental heuristics, that it is possible to solve this bilinear system by linear
<figure><img src="image_5.png" /><figcaption>Fig. 5: Comparison of the MaxMinors complexity and the combinatorial attacks for the parameters $\lambda = 256$, $(2, 43, 47, 18)$ and $r \in \{1..17\}$. Only the values of the complexities with $a < k$ are plotted.</figcaption></figure>

algebra on a matrix with $N$ rows and $M$ columns, as soon as $N \ge M - 1$, with:

$$N = \sum_{i=1}^{k} \binom{n-i}{r} \binom{k+b-1-i}{b-1} - \binom{n-k-1}{r} \binom{k+b-1}{b} \quad (6)$$

$$-(m-1) \sum_{i=1}^{b} (-1)^{i+1} \binom{k+b-i-1}{b-i} \binom{n-k-1}{r+i}. \quad (7)$$

$$M = \binom{k+b-1}{b} \left( \binom{n}{r} - m \binom{n-k-1}{r} \right). \quad (8)$$

In this case, the final cost in $\mathbb{F}_q$ operations is given by

$$\mathcal{O}(m^2 N M^{\omega-1}),$$

where $\omega$ is the linear algebra constant and where the $m^2$ factor comes from expressing each $\mathbb{F}_{q^m}$ operation involved in terms of $\mathbb{F}_q$ operations. As previously, it is possible to use an hybrid approach to reach the constraint $N \ge M - 1$, or to puncture the code to get $N$ and $M$ of the same value. The complexity estimates for the parameters sets are plotted in Figures 3, 4, 5. We can see that for $q = 2$, the MaxMinors modeling is (almost) always better than the Support Minors one.

# 10 Advantages and limitations

## 10.1 Advantages

**Difficulty of the underlying problem:** the security of the signature scheme relies on the genuine problem of decoding in rank metric Rank-SD, and there exists a probabilistic reduction from a generic NP-complete problem to the Rank-SD problem [GZ14]. The
Rank-SD problem has been studied for many years. In particular the security of the problem corresponds to parameters on the Rank-Gilbert-Varshamov bound, the hardest area for parameters in which recent algebraic attacks [BBC$^+$20] behave similarly to classical combinatorial attacks.

**Size of public keys and signature:** the size of our parameters remains low. When comparing to Dilithium level 1, the sum of public key and signature sizes of RYDE is less than 60% higher than Dilithium (the sum for Dilithium reaches 3.7kB compared to 5.9kB for RYDE). It makes RYDE one of the shortest MPCitH signatures.

**Size of the public matrix:** in our case the public matrix can be generated from a random seed. Now independently of this, the properties of rank metric make the size of the public matrix very small (and this without additional cyclic structure), for instance of order 1kB for the first level of parameters: it could be an advantage if one were to choose not to generate the public matrix from a seed.

**No cyclic structure of the underlying problem:** our security is based on a problem which does not rely on cyclic structure for which the quantum security is not fully known.

**Resilience against Rank-SD attacks:** the size of the signature is composed of two parts: a part related to the MPC that only depends on the security level (seeds, hashes) and a part related to the parameters of the chosen RSD instance. Hence, increasing the size of the problem parameters has a limited impact on the total size of the signature. For example, the RYDE-128S instance features a signature size of 5.9kB using the parameters $(q, m, n, k, r) = (2, 31, 29, 14, 10)$ for NIST security level 1. Choosing the parameters $(q, m, n, k, r) = (2, 37, 38, 16, 14)$ would reach more than 192 bits of security for the underlying problem and result in a signature size of 6.9 kB for NIST security level 1. Thus, if one discovers an efficient attack against the Rank-SD problem that forces us to increase the problem parameters, only the problem parameter part will be impacted and the overall effect on the signature length will be mitigated, as explained in the previous example.

## 10.2 Limitations

**Growth rate of the signature size:** the size of the signature grows with a quadratic rate when increasing the security level. This comes from the fact that when the security level increases, both the parameters of the Rank-SD instance and the number of repetitions tau need to be increased. For example, going from security level 1 to 3, the number of repetitions is increased by half (20 to 30) while the quantity of data to be transmitted per turn grows as well since the parameters of the Rank-SD instance also have to be increased. Notice that this limitation is coherent with the Rank-SD resilience advantage from Section 10.1. Indeed in that case only the instance parameters need to be increased and not the number of repetitions nor the size of seeds and hashes.

**Signature speed:** Compared to lattice based signatures, the speed of our scheme is slower even if it compares very well with other signature schemes in general.
**Complex implementation:** this scheme is relatively complex to implement. Although it has potential to perform well on hardware, its implementation could be difficult in embedded systems.
References

[AABN02] Michel Abdalla, Jee Hea An, Mihir Bellare, and Chanathip Namprempre. From Identification to Signatures via the Fiat-Shamir Transform: Minimizing Assumptions for Security and Forward-Security. In Lars R. Knudsen, editor, *Advances in Cryptology — EUROCRYPT 2002*, pages 418–433, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.

[AGHT18] Nicolas Aragon, Philippe Gaborit, Adrien Hauteville, and Jean-Pierre Tillich. A New Algorithm for Solving the Rank Syndrome Decoding Problem. In *ISIT 2018 - IEEE International Symposium on Information Theory*, pages 2421–2425, Vail, United States, June 2018.

[AMGH$^{+22}$] Carlos Aguilar-Melchor, Nicolas Gama, James Howe, Andreas Hülsing, David Joseph, and Dongze Yue. The Return of the SDitH. *Cryptology ePrint Archive, Report 2022/1645*, 2022.

[BBB$^{+20}$] 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 Anne Canteaut and Yuval Ishai, editors, *Advances in Cryptology – EUROCRYPT 2020*, pages 64–93, Cham, 2020. Springer International Publishing.

[BBB$^{+22}$] Magali Bardet, Pierre Briaud, Maxime Bros, Philippe Gaborit, and Jean-Pierre Tillich. Revisiting algebraic attacks on minrank and on the rank decoding problem, 2022.

[BBC$^{+20}$] Magali Bardet, Maxime Bros, Daniel Cabarcas, Philippe Gaborit, Ray Perlner, Daniel Smith-Tone, Jean-Pierre Tillich, and Javier Verbel. Improvements of algebraic attacks for solving the rank decoding and minrank problems. In *Advances in Cryptology - ASIACRYPT 2020, International Conference on the Theory and Application of Cryptology and Information Security, 2020. Proceedings*, pages 507–536, 2020.

[BCDF$^{+23}$] Loïc Bidoux, Jesús-Javier Chi-Domínguez, Thibauld Feneuil, Philippe Gaborit, Antoine Joux, Matthieu Rivain, and Adrien Vinçotte. RYDE: A Digital Signature Scheme based on Rank-Syndrome-Decoding problem with MPCitH paradigm. arXiv, 2023.

[BGRV23] Loïc Bidoux, Philippe Gaborit, Olivier Ruatta, and Adrien Vinçotte. MPCitH-based Signature for the RSD problem using a Hypercube. In *IEEE International Symposium on Information Theory (ISIT)*, 2023.

[BHT98] Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum Cryptanalysis of Hash and Claw-Free Functions. In Claudio L. Lucchesi and Arnaldo V. Moura, editors, *LATIN '98: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings*, volume 1380 of *Lecture Notes in Computer Science*, pages 163–169. Springer, 1998.

[CS96] Florent Chabaud and Jacques Stern. The Cryptographic Security of the Syndrome Decoding Problem for Rank Distance Codes. In *Advances in Cryptology - ASIACRYPT '96, International Conference on the Theory and Applications of Cryptology and Information Security, Kyongju, Korea, November 3-7, 1996, Proceedings*, volume 1163 of *Lecture Notes in Computer Science*, pages 368–381. Springer, 1996.

[Fen22] Thibauld Feneuil. Building MPCitH-based Signatures from MQ, MinRank, Rank SD and PKP. *Cryptology ePrint Archive, Report 2022/1512*, 2022.

[FR22] Thibauld Feneuil and Matthieu Rivain. Threshold Linear Secret Sharing to the Rescue of MPC-in-the-Head. *Cryptology ePrint Archive, Paper 2022/1407*, 2022.

[FS86] Amos Fiat and Adi Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In *International Cryptology Conference (CRYPTO)*, 1986.

[GRS13] Philippe Gaborit, Olivier Ruatta, and Julien Schrek. On the complexity of the Rank Syndrome Decoding problem, 2013.

[GZ14] Philippe Gaborit and Gilles Zémor. On the hardness of the decoding and the minimum distance problems for rank codes, 2014.

[IKOS07] Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Zero-Knowledge from Secure Multiparty Computation. In *Proceedings of the 39th annual ACM symposium on Theory of computing (STOC)*, 2007.

[KZ20] Daniel Kales and Greg Zaverucha. An Attack on Some Signature Schemes Constructed From Five-Pass Identification Schemes. In *International Conference on Cryptology and Network Security (CANS)*, 2020.

[Loi07] Pierre Loidreau. Rank metric and cryptography. *HAL*, 2007, 2007.