# MIRA Specifications

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

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

## To cite this version:

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

HAL Id: hal-04315820

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

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_2.png" /></figure>

Distributed under a Creative Commons CC0 1.0 - Universal - International License
MIRA 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" />, Romaric Neveu<fnref n="5" />, Matthieu Rivain<fnref n="7" />, Jean-Pierre Tillich<fnref n="3" />

<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>
Table of Contents

<table><tr><td>1</td><td>Introduction</td><td>3</td></tr><tr><td>2</td><td>Mathematical Background and Notations</td><td>3</td></tr><tr><td>3</td><td>High-level description of the signature scheme</td><td>4</td></tr><tr><td>3.1</td><td>Description of the MPC protocol</td><td>4</td></tr><tr><td>3.2</td><td>Application of the MPCitH paradigm</td><td>6</td></tr><tr><td>3.2.1</td><td>General view of MPCitH</td><td>6</td></tr><tr><td>3.2.2</td><td>Overview of MIRA</td><td>7</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>8</td></tr><tr><td>4.3</td><td>Randomness generators and hash functions</td><td>11</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>13</td></tr><tr><td>4.7</td><td>Key parsing routines</td><td>14</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>17</td></tr><tr><td>5</td><td>Signature parameters</td><td>20</td></tr><tr><td>5.1</td><td>MIRA-Additive</td><td>20</td></tr><tr><td>5.2</td><td>MIRA-Threshold</td><td>21</td></tr><tr><td>6</td><td>Performance Analysis</td><td>21</td></tr><tr><td>6.1</td><td>Reference Implementation</td><td>22</td></tr><tr><td>6.2</td><td>Optimized Implementation</td><td>22</td></tr><tr><td>7</td><td>Known Answer Test Values</td><td>23</td></tr><tr><td>8</td><td>Expected security strength</td><td>23</td></tr><tr><td>8.1</td><td>Resistance to quantum attacks</td><td>24</td></tr><tr><td>9</td><td>Analysis of known attacks</td><td>24</td></tr><tr><td>9.1</td><td>Kales and Zaverucha attack on the Fiat-Shamir transform</td><td>24</td></tr><tr><td>9.2</td><td>Attacks on MinRank</td><td>25</td></tr><tr><td>9.2.1</td><td>The kernel attack</td><td>26</td></tr><tr><td>9.2.2</td><td>Algebraic attacks</td><td>26</td></tr><tr><td>10</td><td>Advantages and limitations</td><td>28</td></tr><tr><td>10.1</td><td>Advantages</td><td>28</td></tr><tr><td>10.2</td><td>Limitations</td><td>29</td></tr></table>
# 1 Introduction

MIRA is a digital signature protocol based on the MinRank problem and the MPC-in-the-Head paradigm. This document specifies the scheme described in our Design Document, [ABCD+23]. The scheme is quantum-resistant, and is 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, on which the protocol is built. The security of the signature is conditioned by the difficulty of solving the MinRank problem. We apply the Fiat-Shamir transform [FS87] in order to have a signature. MIRA is based on additive secret sharing, and uses the idea of the hypercube structure from [AMGH+22], as well as an MPC protocol using linearized polynomials which is introduced in [Fen22].

We propose two versions of the scheme (the only difference is the number of parties we simulate). One uses less parties and is faster but larger, while the other uses more parties and is shorter but slower.

The name MIRA comes from the MinRank problem.

# 2 Mathematical Background and Notations

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

We denote by $[1, N]$ the set of integer between 1 and $N$. This set can be shortened by writing $[N]$.

Let $\mathbf{E} \in \mathbb{F}_q^{m \times n} = (e_{i,j})$, $e_{i,j} \in \mathbb{F}_q$, $i \in [1, m]$, $j \in [1, n]$, and $\mathcal{B} = \langle b_1 \dots b_m \rangle$ an $\mathbb{F}_q$-basis of $\mathbb{F}_{q^m}$. It is then possible to associate each column of $\mathbf{E}$ to an element of $\mathbb{F}_{q^m}$ by setting

$$e_j = \sum_{i=1}^{m} b_i e_{i,j}$$

for each $j \in [1, n]$

By setting $\mathbf{e} = (e_1 \dots e_n)$, we can say that $\mathbf{e}$ is the vector associated to the matrix $\mathbf{E}$.

The Rank Weight is defined as $W_R(\mathbf{e}) = \text{Rank}(\mathbf{E})$.

The distance between two vectors $\mathbf{x}$ and $\mathbf{y}$ is $d(\mathbf{x}, \mathbf{y}) = W_R(\mathbf{x} - \mathbf{y})$.

The support of $\mathbf{e} = (e_1 \dots e_n)$ is the linear subspace of $\mathbb{F}_{q^m}$ generated by its coordinates: $\text{Supp}(\mathbf{e}) = \langle e_1 \dots e_n \rangle$.

With these notations in mind, we can define the MinRank Problem, on which MIRA is based:
### MinRank:

Let $\mathbb{F}_q$ be the finite field of size $q$, and $m, n, k, r \in \mathbb{N}^*$. The computational MinRank Problem with parameters $(q, m, n, k, r)$ is

Let $\mathbf{M}_0, \dots, \mathbf{M}_k, \mathbf{E} \in \mathbb{F}_q^{m \times n}$ and $\mathbf{x} \in \mathbb{F}_q^k$ sampled uniformly at random such that:

$$ \mathbf{M}_0 = \mathbf{E} - \sum_{i=1}^{k} \mathbf{M}_i x_i \quad \text{and} \quad \text{Rank}(\mathbf{E}) \le r. $$

Knowing $\mathbf{M}_0, \dots, \mathbf{M}_k$, retrieve $\mathbf{x}$.

The public key is the list of matrices $\mathbf{M}_0, \dots, \mathbf{M}_k$, and the secret key is the vector $\mathbf{x}$. The principle of the signature is based on a transformation of a proof of knowledge of $\mathbf{x}$ into a non-interactive protocol thanks to the Fiat-Shamir Transform. Iterating the process multiple times gives the verifier a high assurance that the verifier knows $\mathbf{x}$.

The interactive proof relies on a prover simulating a MultiParty Computation (MPC) protocol, where each party has a share of the witness $\mathbf{x}$. The sharing of a secret $s$ among $N$ parties is denoted $(s[1], \dots, s[N])$ where $s[i]$ is the share possessed by the party $i$. $s[J]$ where $J \subset [1, N]$ is the subset of shares $(s[j])_{j \in J}$. When we do not specify which party receives the share (as is the case in Fig.1), we note the share as $s[\cdot]$.

Below is the secret sharing scheme we are going to use.

**Additive Secret Sharing.** Let $\mathbb{F}$ a field and $s \in \mathbb{F}$ a secret.

An additive secret sharing with $N$ parties satisfies:

$$ s[i] = r_i \quad \text{for } i \in [1, N-1], \text{ where } r_i \leftarrow \mathbb{F} $$

$$ s[N] = s - \sum_{i=1}^{N-1} s[i] $$

The Reconstruct$_{[1,N]}$ algorithm takes as inputs all the shares, and outputs the sum of all the shares.

## 3 High-level description of the signature scheme

As mentioned earlier, the scheme relies on a MinRank instance. Hence, the public key $pk$ is a list of matrices $\mathbf{M}_0, \dots, \mathbf{M}_k$, and the private key $sk$ is the vector $\mathbf{x}$, of size $k$.

In order to sign a message one has to:

- Build the proof of knowledge;

- Apply the Fiat-Shamir transform.

The proof of knowledge relies on the MPC protocol of [Fen22] (see $[ABCD^+23]$).

### 3.1 Description of the 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 of $\mathbf{x}$ they received at the
begin of the protocol, and each get a share of $f(x)$. 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 an hint which depends on the witness $w$ and the previous elements sent;

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

- Broadcasting: the parties can broadcast their shares of a given value which is then publicly recomputed by all the parties. This opening should be done in a way that do not leak information about the witness $w$.

Due to application to zero-knowledge proofs as detailed below, the MPC protocol only needs to be secure in the semi-honest model in which all the parties honestly follow the different steps of the protocol.

The MPC protocol we use here allows $N$ parties to verify that a matrix, $\mathbf{E}$, built using the secret $\mathbf{x}$, is of a certain rank. It works this way:

- Each party receives their shares of the witness $\mathbf{x}$, as well as shares of some elements that will be used to execute the protocol;

- Each party computes their share of $\mathbf{E}$;

- After some other computations, each party computes a value $v$, which is a combination of evaluations of a linearized polynomial. If $v = 0$, $\mathbf{x}$ is the witness corresponding to the MinRank instance;

- The view of $N - 1$ parties gives no information whatsoever about $\mathbf{x}$.

Concretely, if $v = 0$, this means that $\mathbf{E}$ is of rank at most $r$ if the computations and the inputs are from an honest party. This comes from the properties of a linearized polynomial (see [ABCD+23] or [Fen22]).

Formally, we can describe the MPC protocol with the following figure:
<figure><img src="image_3.png" /><figcaption>Fig. 1: Protocol $\Pi^{\eta}$ to check that an input is solution of an instance of MinRank</figcaption></figure>

Steps 2 and 3 are the computation of $\mathbf{E}$ and its support, and steps 4 to 7 are the computation of $v$. The parties open an element, $\boldsymbol{\alpha}$, during the process, in order to make sure the computation is done honestly. Note that in step 3, the computation is done in regards to the columns of $\mathbf{E}$. Depending on the parameters $m$ and $n$, it might be better to do it with the rows instead.

We refer to [ABCD$^+$23] or [Fen22] for the proof of false positive of this MPC protocol and its correctness.

## 3.2 Application of the MPCitH paradigm

### 3.2.1 General view of MPCitH

The zero-knowledge proof relies on the application of the MPCitH paradigm [IKOS07].

The MPCitH paradigm consists in committing the views of all the parties, and revealing as much as possible without leaking information about $\boldsymbol{x}$. Generally, an MPCitH protocol works as follows:

- The prover commits the shares of the parties;

- He receives a challenge in order to execute the MPC protocol;

- He sends the hash of the results of the MPC protocol for each party;

- He receives a challenge to know what to reveal;

- He reveals what he has to according to the second challenge.

We refer to [FR22] for a more formal definition.

We will now describe the proof of knowledge.
### 3.2.2 Overview of MIRA

The hypercube structure is used in this case. The idea, introduced in [AMGH$^{+22}$], is the following:

The prover builds $N = 2^D$ shares, using additive sharing, and organises them in a hypercube with $D$ dimensions. Then, it is possible to sum shares, in order to get 2 *main shares* per dimension only. Since it is an additive scheme, all that is left to do for him is to execute the MPC protocol $D$ times on the 2 *main shares* of the dimension. Moreover, since the $D$ MPC protocols use the same secret, one can get further savings by only performing the MPC computation for one main share per dimension as well as the MPC computation on the plain values. This makes a total of $D + 1$ MPC computations instead of $2^D$. The interested reader can find more details in our design documentation [ABCD$^{+23}$] and in [AMGH$^{+22}$] regarding the hypercube approach. We obtain the following zero-knowledge proof of knowledge protocol:

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

- He then commits the states of the parties, computes the *main shares*, and receives a first challenge corresponding to some random values;

- Thanks to this challenge, he simulates the $D-1$ MPC computations on main shares (one per dimension), and 1 MPC computation on plain values, and sends the hash of 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 the broadcast shares of the party whose view is not revealed;

- The verifier checks that the computations of the MPC protocol was done honestly and that the MPC protocol would accept the shared input solution;

This zero-knowledge proof of knowledge can then be turned into a signature scheme using the Fiat-Shamir transform [FS87].

## 4 Detailed algorithmic description

This section is dedicated to a low-level algorithmic description of the three algorithms of our scheme: *MIRA_Keygen*, *MIRA_Sign* and *MIRA_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$</td><td>[1, N]</td><td>Index of a leaf party.</td></tr><tr><td>$\delta$</td><td>[1, D]</td><td>Index of a main party.</td></tr><tr><td>$e$</td><td>[1, $\tau$]</td><td>Index of an iteration.</td></tr><tr><td colspan="3"><strong>Seeds:</strong></td></tr><tr><td>seed_pk</td><td>{0, 1}$^{\lambda}$</td><td>Seed for generation of the matrix $\mathbf{H}$ in the public key.</td></tr><tr><td>seed_sk</td><td>{0, 1}$^{\lambda}$</td><td>Seed for generation of the secret vector $\mathbf{x}$ and secret annihilator polynomial $\beta$.</td></tr><tr><td>mseed</td><td>{0, 1}$^{\lambda}$</td><td>Master seed for generation of the seeds $\text{seed}^{(e)}$</td></tr><tr><td>seed<sup>(e)</sup></td><td>{0, 1}$^{\lambda}$</td><td>Root seed of the PRG tree.</td></tr><tr><td>seed<sub>i</sub><sup>(e)</sup></td><td>{0, 1}$^{\lambda}$</td><td>Leaf seed of the PRG tree.</td></tr><tr><td>ptree<sup>(e)</sup></td><td>{0, 1}$^{\lambda D}$</td><td>Partial seeds of the PRG tree masking an index $i^{*(e)}$.</td></tr><tr><td colspan="3"><strong>Constants:</strong></td></tr><tr><td>DS_M</td><td>{0, 1}$^{\lambda}$</td><td>Domain separator for the message.</td></tr><tr><td>DS_T</td><td>{0, 1}$^{\lambda}$</td><td>Domain separator for the PRG tree.</td></tr><tr><td>DS_C</td><td>{0, 1}$^{\lambda}$</td><td>Domain separator for the PRG commitments.</td></tr><tr><td>DS_1</td><td>{0, 1}$^{\lambda}$</td><td>Domain separator for the first response.</td></tr><tr><td>DS_2</td><td>{0, 1}$^{\lambda}$</td><td>Domain separator for the second response.</td></tr><tr><td colspan="3"><strong>Bytestring variables:</strong></td></tr><tr><td>cmt<sub>i</sub><sup>(e)</sup></td><td>{0, 1}$^{2\lambda}$</td><td>Leaf commitments.</td></tr><tr><td>$h_1$</td><td>{0, 1}$^{2\lambda}$</td><td>First commitment.</td></tr><tr><td>$h_2$</td><td>{0, 1}$^{2\lambda}$</td><td>Second commitment.</td></tr><tr><td colspan="3"><strong>Field elements, vectors and matrices:</strong></td></tr><tr><td>$M_i$</td><td>$\mathbb{F}_q^{m \times n}$</td><td>Public matrix</td></tr><tr><td>$\mathbf{E}$</td><td>$\mathbb{F}_q^{m \times n}$</td><td>Secret error matrix of rank $r$</td></tr><tr><td>$e$</td><td>$\mathbb{F}_q^m$</td><td>$\mathbb{F}_{q^m}$-vector associated to the $\mathbb{F}_{q^m}$-matrix $\mathbf{E}$</td></tr><tr><td>$\mathbf{x}$</td><td>$\mathbb{F}_q^k$</td><td>Secret coefficients of the secret linear combination</td></tr><tr><td>$\beta$</td><td>$\mathbb{F}_q^r$</td><td>Annulator polynomial of the support of $e$.</td></tr><tr><td>$\mathbf{a}$</td><td>$\mathbb{F}_q^{r^m}$</td><td>Vector used in the MPC rank checking protocol.</td></tr><tr><td>$\mathbf{w}$</td><td>$\mathbb{F}_q^{r^m}$</td><td>Vector used in the MPC rank checking protocol.</td></tr><tr><td>$\gamma$</td><td>$\mathbb{F}_q^{n^m}$</td><td>Vector from the first challenge.</td></tr><tr><td>$c$</td><td>$\mathbb{F}_q^{n^m}$</td><td>Element used in the MPC rank checking protocol.</td></tr><tr><td>$z$</td><td>$\mathbb{F}_q^{n^m}$</td><td>Element used in the MPC rank checking protocol.</td></tr><tr><td>$\epsilon$</td><td>$\mathbb{F}_q^{n^m}$</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 $\delta$ (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 = \mathbb{F}_{16}$. We define $\mathbb{F}_q$ as $\mathbb{F}_2[X]/\langle P \rangle$ where $P = X^4 + X + 1$. Elements of $\mathbb{F}_q$ are represented in the polynomial basis.

Converting a byte stream into elements of $\mathbb{F}_q$

When sampling randomness, we want to convert a byte stream $b_0, b_1, \dots$ into elements of $\mathbb{F}_q$. Sampling $n$ elements in $\mathbb{F}_q$ is done using the `FqArrayFromBytes(n)` function 1.

**Algorithm 1 FqArrayFromBytes**

**Input:** Size $n$, $l = \lceil \frac{n}{2} \rceil$ bytes $b_0, \dots, b_{l-1}$

**Output:** An array $\boldsymbol{x}$ of $n$ elements of $\mathbb{F}_q$

1: **for** $i$ from 0 to $\lfloor \frac{n}{2} \rfloor - 1$ **do**

2: $\boldsymbol{x}_{2i} = b_i \& 0xf$

3: $\boldsymbol{x}_{2i+1} = (b_i >> 4)$

4: **if** $n%2 == 1$ **then**

5: $\boldsymbol{x}_{n-1} = b_{l-1} \& 0xf$

We also define the `FqArrayToBytes(A)` 2 to go from an array of $n$ elements of $\mathbb{F}_q$ to a byte array.

**Algorithm 2 FqArrayToBytes**

**Input:** An array $\boldsymbol{x}$ of $n$ elements of $\mathbb{F}_q$

**Output:** A byte array $b_0, \dots, b_{l-1}$ where $l = \lceil \frac{n}{2} \rceil$

1: **for** $i$ from 0 to $\lfloor \frac{n}{2} \rfloor - 1$ **do**

2: $b_i = (\boldsymbol{x}_{2i} \& 0xf) + (\boldsymbol{x}_{2i+1} << 4)$

3: **if** $n%2 == 1$ **then**

4: $b_{l-1} = \boldsymbol{x}_{n-1} \& 0xf$

Using these core functions we can define how matrices over $\mathbb{F}_q$ and arrays of elements in $\mathbb{F}_{q^m}$ are parsed:

- We process arrays of $r$ elements of $\mathbb{F}_{q^m}$ as arrays of $rm$ elements of $\mathbb{F}_q$,

- We process $m \times n$ matrices over $\mathbb{F}_q$ as arrays of $mn$ elements of $\mathbb{F}_q$.

We refer to the resulting functions as `FqmArrayFromBytes(size)`, `FqmArrayToBytes(x)`, `FqMatrixFromBytes(lines, columns)` and `FqMatrixToBytes(M)`.

Defining extensions of $\mathbb{F}_q$

In order to perform operations in $\mathbb{F}_{q^m}$ we define how $\mathbb{F}_{q^m}$ is defined as an extension of $\mathbb{F}_q$.

- For $m = 16$:

We define $\mathbb{F}_{q^2}$, $\mathbb{F}_{q^4}$, $\mathbb{F}_{q^8}$ and $\mathbb{F}_{q^{16}}$ as follows:

$$ \mathbb{F}_{q^2} = \mathbb{F}_{q}[Z]/\langle Z^2 + Z + X^3 \rangle $$
$$
\begin{align*}
\mathbb{F}_{q^4} &= \mathbb{F}_{q^2}[A]/\langle A^2 + A + (ZX^3) \rangle \\
\mathbb{F}_{q^8} &= \mathbb{F}_{q^4}[B]/\langle B^2 + B + (ZAX^3) \rangle \\
\mathbb{F}_{q^{16}} &= \mathbb{F}_{q^8}[Y]/\langle Y^2 + Y + (ZABX^3) \rangle
\end{align*}
$$

- For $m$ prime:

When $m$ is prime we define $\mathbb{F}_{q^{16}}$ as $\mathbb{F}_q[Y]/\langle P \rangle$ where $P$ is an irreducible polynomial of degree $m$ over $\mathbb{F}_2$. 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>19</td><td>Y<sup>19</sup> + Y<sup>5</sup> + Y<sup>2</sup> + Y + 1</td></tr><tr><td>23</td><td>Y<sup>23</sup> + Y<sup>5</sup> + 1</td></tr></tbody></table>

Conversion from $\mathbb{F}_q$-arrays to $\mathbb{F}_{q^m}$-elements is done using a $\mathbb{F}_q$-basis of $\mathbb{F}_{q^m}$ ($g_1, \dots, g_m$) that is defined as follows:

- For $m = 16$, the basis consists of elements $Z^{b_0} A^{b_1} B^{b_2} Y^{b_3}$ for every possible 4-bitstring $b_0b_1b_2b_3$ in increasing order.

- For $m$ prime, the basis is the standard polynomial basis $(1, Y, \dots, Y^{m-1})$.

This basis ($g_1, \dots, g_m$) allows converting between an $\mathbb{F}_q$-matrix of size $m \times n$ and an $\mathbb{F}_{q^m}$-vector of size $n$:

**Algorithm 3 FqMatrixToFqmVector**

**Input:** A matrix $M \in \mathbb{F}_q^{m \times n}$

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

1: **for** $j \in [n]$ **do**

2: $x_j = \sum_{i=1}^{m} M_{i,j} g_i$

3: **return** $x$

**Algorithm 4 FqmVectorToFqMatrix**

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

**Output:** A matrix $M \in \mathbb{F}_q^{m \times n}$

1: **for** $j \in [n]$ **do**

2: Fill the $j$-th column of $M$ with the coefficients of $x_j$ in the basis ($g_1, \dots, g_m$).

$$x_j = \sum_{i=1}^{m} M_{i,j} g_i$$

3: **return** $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.

<caption>**Algorithm 5 ComputeAnnihilatorPolynomial**</caption>

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

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

for $i$ from 1 to $r$ do

$$T = P_i^q$$

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

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

return $P_{r+1}$

## 4.3 Randomness generators and hash functions

- **RandomBytes**($\ell$) is instantiated 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,

* **PRG.GetBytes**($\ell$) outputs $\ell$ bytes from the generator and updates its internal state.

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

## 4.4 Sampling routines

These routines sample from a seed some set of elements needed in the scheme. Recall that we only consider the case where $q = 16$.
Algorithm 6 SampleSecretInstance

Input: Size $(m, n)$, dimension $k$, rank weight $r$, a seed `seed`

Output: $E \in \mathbb{F}_q^m \times n$ a matrix of rank $r$ and its support $\text{supp} \in \mathbb{F}_{q^m}^r$, $x \in \mathbb{F}_q^k$.

1: PRG.Init(seed)

2: $r\_bytes = \lceil \frac{rm}{2} \rceil$

3: repeat

4: $\text{supp}[1, r] = \text{FqmArrayFromBytes}(r, \text{PRG}.GetBytes(r\_bytes)) \quad \triangleright \text{Sampling the support}$

5: until Rank($\text{FqmVectorToFqMatrix}(\text{supp})$) = $r$

6: $e = (0, \dots, 0) \quad \triangleright \text{Initialize } e$ with zeros

7: repeat

8: coordinates = $\text{FqArrayFromBytes}(nr, \text{PRG}.GetBytes(\lceil \frac{nr}{2} \rceil))$

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

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

11: $e_i = e_i + \text{coordinates}[(i - 1)r + j] \cdot \text{supp}[j]$

12: $E = \text{FqmVectorToFqMatrix}(e)$

13: until Rank($E$) = $r$

14: $k\_bytes = \lceil \frac{k}{2} \rceil$

15: $x = \text{FqArrayFromBytes}(k, \text{PRG}.GetBytes(k\_bytes))$

16: return $E, \text{supp}, x$

Algorithm 7 SampleSeeds

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

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

PRG.Init(seed)

for $i \in [\tau]$ do

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

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

Algorithm 8 SampleShares

Input: A seed `seed`

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

PRG.Init(seed)

xbytes = PRG.GetBytes(\lceil \frac{k}{2} \rceil)

x = FqArrayFromBytes(k, xbytes)

bbytes = PRG.GetBytes(\lceil \frac{rm}{2} \rceil)

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

abytes = PRG.GetBytes(\lceil \frac{rm}{2} \rceil)

a = FqmArrayFromBytes(r, abytes)

cbytes = PRG.GetBytes(\lceil \frac{m}{2} \rceil)

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

return $(x, \beta, a, c)$
**Algorithm 9 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($\lceil \frac{(n+1)m}{2} \rceil$)

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

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

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

**Algorithm 10 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 11 MPC-MinRank ComputeAlpha**

**Input:**

- A set of shares $(e, a)$

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

**Output:** $\alpha$

1: for $k \in [1, r]$ do

2: $w_k = \sum_{j=1}^{n} \gamma_j (e_j^{q^{k-1}})$

3: $\alpha = \epsilon \cdot w + a$

4: return $\alpha$
**Algorithm 12 MPC-MinRank 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 matrices $M_0, \dots, M_k$

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

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

2: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{E}[\delta] = M_0 + \sum_{i=1}^k \hat{x}_i[\delta] M_i$

3: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{e}[\delta] = \text{FqMatrixToFqmVector}(\hat{E}[\delta])$

4: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{\alpha}[\delta] = \text{MPC-RSD}\cdot\text{ComputeAlpha}(\hat{e}[\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{e}_j[\delta]^{q_r})$

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 13 Hypercube MainShares Compute**

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

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

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

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

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

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

5: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{c}[\delta] = \sum_{\text{bit}(i-1, \delta)=0}^{i \in [N]} c[i]$
Algorithm 14 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_{\text{bit}(i-1, \delta)=0}^{i \in [N]} \alpha[i]$

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

4.7 Key parsing routines

Algorithm 15 ParseSecretKey

Input: Secret key sk

Output: $M_0, \dots, M_k, x$, the annihilator polynomial $\beta$ and $e$

1: $(\text{sk}\_\text{seed}, \text{pk}\_\text{seed}) = \text{sk}$

2: $\text{pk\_PRG}_\text{Init}(\text{pk\_seed})$

3: $\text{L\_bytes} = \lceil \frac{k(mn-k)}{2} \rceil$

4: $\mathbf{L}' = \text{FqMatrixFromBytes}(k, mn-k, \text{pk\_PRG}.\text{GetBytes}(\text{L\_bytes}))$

5: $\mathbf{L} = (I_k | \mathbf{L}')$

6: for $i \in [k]$ do

7:     for $j \in [m]$ do

8:         for $\ell \in [n]$ do

9:             $(M_i)_{j,\ell} = \mathbf{L}_{i,(j-1)n+\ell}$

10: $(E, \text{supp}, y) = \text{SampleSecretInstance}(\text{sk\_seed})$

11: $F = E - \sum_{i=1}^k y_i M_i$

12: for $i \in [k]$ do

13:     $f_i = \mathbf{F}_{1+\lfloor \frac{i-1}{n} \rfloor, 1+((i-1) \bmod n)}$

14: $M_0 = F - \sum_{i=1}^k f_i M_i$

15: $x = y + f$

16: $e = \text{FqMatrixToFqmVector}(E)$

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

18: return $(M_0, \dots, M_k, x, \beta, e)$
## Algorithm 16 ParsePublicKey

**Input:** Public key pk

**Output:** $M_0, \dots, M_k$

1: $(pk\_seed, m\_bytes) = pk$

2: PRG.Init(pk\_seed)

3: $L\_bytes = \lceil \frac{k(mn-k)}{2} \rceil$

4: $L' = \text{FqMatrixFromBytes}(k, mn-k, \text{PRG}.GetBytes}(L\_bytes))$

5: $L = (I_k|L')$

6: for $i \in [k]$ do

7: &nbsp;&nbsp;&nbsp;&nbsp;for $j \in [m]$ do

8: &nbsp;&nbsp;&nbsp;&nbsp;for $\ell \in [n]$ do

9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(M_i)_{j,\ell} = L_{i,(j-1)n+\ell}$

10: $M_0 = \text{FqMatrixFromBytes}(m, n, m\_bytes)$

11: return $(M_0, \dots, M_k)$

## 4.8 PRG tree routines

## Algorithm 17 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: &nbsp;&nbsp;&nbsp;&nbsp;return `seed`

3: else

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

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

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

7: &nbsp;&nbsp;&nbsp;&nbsp;return $(seed_i)_{i \in [N]}$
Algorithm 18 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 19 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

<caption>**Algorithm 20 MIRA_keygen**</caption>

**Input:** Security level $\lambda$
**Output:** Secret key sk, public key pk
1: sk_seed = RandomBytes($\lambda$)
2: pk_seed = RandomBytes($\lambda$)
3: pk_PRG.Init(pk_seed)
4: L_bytes = ⌈$\frac{k(mn-k)}{2}$⌋
5: L' = FqMatrixFromBytes(k, mn-k, pk_PRGZXGetBytes(L_bytes))
6: L = (I_k|L')
7: for i ∈ [k] do
8:     for j ∈ [m] do
9:         for ℓ ∈ [n] do
10:         (M_i)_{j,ℓ} = L_{i,(j-1)n+ℓ}
11:     (E,_, y) = SampleSecretInstance(sk_seed)
12:     F = E - $\sum_{i=1}^k y_i M_i$
13:     for j ∈ [k] do
14:         $f_i = F_{1+\lfloor\frac{i-1}{n}\rfloor,1+((i-1) \bmod n)}$
15:     $M_0 = F - \sum_{i=1}^k f_i M_i$
16:     pk = pk_seed || FqMatrixToBytes(M_0)
17:     sk = sk_seed || pk_seed
18: return sk, pk
Algorithm 21 MIRA_Sign

Input: Secret key sk, public key pk, message m ∈ {0, 1}*

Output: Signature σ ∈ {0, 1}*

▷ Step 0: Parse keys

1: $(M_0, \dots, M_k, \mathbf{x}, \boldsymbol{\beta}, \boldsymbol{e}) = \text{ParseSecretKey}(\text{sk})$

▷ Step 1: Commitment

2: salt = RandomBytes(2λ)

3: mseed = RandomBytes(λ)

4: md = Hash(DS_M, m)

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

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

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

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

▷ Compute leaf shares

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

10: cmt<sub>i</sub><sup>(e)</sup> = Hash(DS_C, salt, e, i, seed<sub>i</sub><sup>(e)</sup>)

11: PRG.Init(seed<sub>N</sub><sup>(e)</sup>)

12: abytes = PRG.GetBytes(\lceil \frac{rm}{2} \rceil)

13: $\mathbf{a}^{(e)}[N] = \text{FqmArrayFromBytes}(r, abytes)$

▷ Compute final leaf shares

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

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

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

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

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

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

20: $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)})$ ▷ Commit hypercube

▷ Step 2: First challenge

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

▷ Step 3: First response

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

23: $\alpha^{(e)} = \text{MPC-MinRank}\cdot\text{ComputeAlpha}(e, \mathbf{a}^{(e)}, \gamma^{(e)}, \epsilon^{(e)})$

24: $(\hat{\alpha}^{(e)}[\delta], \hat{v}^{(e)}[\delta])_{\delta \in [D]} = \text{MPC-MinRank}\cdot\text{Exec}[(\hat{\mathbf{x}}^{(e)}[\delta], \hat{\boldsymbol{\beta}}^{(e)}[\delta], \hat{\mathbf{a}}^{(e)}[\delta], \hat{c}^{(e)}[\delta])_{\delta \in [D]}, \gamma^{(e)}, \epsilon^{(e)}, \alpha^{(e)}, M_0, \dots, M_k]$

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

▷ Step 4: Second challenge

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

▷ Step 5: Second response

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

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

29: $\mathbf{E}^{(e)}[i^{*(e)}] = \begin{cases} M_0 + \sum_{j=1}^k \mathbf{x}^{(e)}[i^{*(e)}] M_j & \text{if } i^{*(e)} = 1 \\ \sum_{j=1}^k \mathbf{x}^{(e)}[i^{*(e)}] M_j & \text{otherwise} \end{cases}$

30: $e^{(e)}[i^{*(e)}] = \text{FqMatrixToFqmVector}(\mathbf{E}^{(e)}[i^{*(e)}])$

31: MPC-MinRank ComputeAlpha(e^{(e)}[i^{*(e)}], a^{(e)}[i^{*(e)}], γ^{(e)}, ϵ^{(e)})

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

33: rsp<sub>i^{*(e)}</sub><sup>(e)</sup> = (ptree<sub>i^{*(e)}</sub><sup>(e)</sup>, cmt<sub>i^{*(e)}</sub><sup>(e)</sup>, α<sub>i^{*(e)}</sub><sup>(e)</sup>[i^{*(e)}], 0, 0, 0)

34: else

35: rsp<sub>i^{*(e)}</sub><sup>(e)</sup> = (ptree<sub>i^{*(e)}</sub><sup>(e)</sup>, cmt<sub>i^{*(e)}</sub><sup>(e)</sup>, α<sub>i^{*(e)}</sub><sup>(e)</sup>[i^{*(e)}], x<sub>i^{*(e)}</sub><sup>(e)</sup>[N], β<sub>i^{*(e)}</sub><sup>(e)</sup>[N], c<sub>i^{*(e)}</sub><sup>(e)</sup>[N])

▷ Step 6: Signature

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

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

Output: ACCEPT or REJECT

▷ Step 0: Parse keys

1: $(M_0, \dots, M_k) = \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: &nbsp;&nbsp;&nbsp;&nbsp;**if** $i^{*(e)} = N$ **then**

6: &nbsp;&nbsp;&nbsp;&nbsp;Check that $(\boldsymbol{x}^{(e)}[N], \boldsymbol{\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: &nbsp;&nbsp;&nbsp;&nbsp;$(\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: &nbsp;&nbsp;&nbsp;&nbsp;**if** $i \neq N$ **then**

12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(\boldsymbol{x}^{(e)}[i], \boldsymbol{\beta}^{(e)}[i], \boldsymbol{a}^{(e)}[i], c^{(e)}[i]) = \text{SampleShares}(\text{seed}_i^{(e)})$

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

14: **else**

15: &nbsp;&nbsp;&nbsp;&nbsp;PRG.Init($\text{seed}_N^{(e)}$)

16: &nbsp;&nbsp;&nbsp;&nbsp;abytes = PRG.GetBytes($\lceil \frac{rm}{2} \rceil$)

17: &nbsp;&nbsp;&nbsp;&nbsp;**a**$^{(e)}[N] = \text{FqmArrayFromBytes}(r, \text{abytes})$

18: &nbsp;&nbsp;&nbsp;&nbsp;**cmt**$_N^{(e)} = \text{Hash}(\text{DS\_C}, \text{salt}, e, N, \text{seed}_i^{(e)}, \boldsymbol{x}^{(e)}[N], \boldsymbol{\beta}^{(e)}[N], c^{(e)}[N])$

19: $\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$

20: **for** $e \in [\tau]$ **do**

21: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i \in [N], i \neq i^{*(e)}$ **do**

22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\boldsymbol{E}^{(e)}[i] = \begin{cases} M_0 + \sum_{j=1}^k \boldsymbol{x}^{(e)}[i]M_j & \text{if } i=1 \\ \sum_{j=1}^k \boldsymbol{x}^{(e)}[i]M_j & \text{otherwise} \end{cases}$

23: &nbsp;&nbsp;&nbsp;&nbsp;$\boldsymbol{e}^{(e)}[i] = \text{FqMatrixToFqmVector}(\boldsymbol{E}^{(e)}[i])$

24: &nbsp;&nbsp;&nbsp;&nbsp;$z^{(e)}[i] = - \sum_{j=1}^n \gamma_j^{(e)} e_j^{(e)}[i] q^r$

25: &nbsp;&nbsp;&nbsp;&nbsp;$\boldsymbol{\alpha}^{(e)}[i] = \text{MPC-MinRank}\cdot\text{ComputeAlpha}(\boldsymbol{e}^{(e)}[i], \boldsymbol{a}^{(e)}[i], \boldsymbol{\gamma}^{(e)}, \boldsymbol{\epsilon}^{(e)})$

26: &nbsp;&nbsp;&nbsp;&nbsp;$\boldsymbol{\alpha}^{(e)} = \sum_i \boldsymbol{\alpha}^{(e)}[i]$

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

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

29: &nbsp;&nbsp;&nbsp;&nbsp;$v^{(e)}[i^{*(e)}] = - \sum_{i \neq i^{*(e)}} v^{(e)}[i]$

30: &nbsp;&nbsp;&nbsp;&nbsp;$(\hat{\boldsymbol{\alpha}}^{(e)}[\delta], \hat{v}^{(e)}[\delta])_{\delta \in [D]} = \text{Hypercube}\cdot\text{MainAlphaAndV-Compute}((\boldsymbol{\alpha}^{(e)}[i], v^{(e)}[i])_{i \in [N]}$

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

▷ Step 4: Verify commitments

32: **return** $\bar{h}_1 \stackrel{?}{=} h_1 \land \bar{h}_2 \stackrel{?}{=} h_2$
# 5 Signature parameters

Our signature scheme uses the following parameters:

- the power of a prime number, $q \in \mathbb{N}$, to build $\mathbb{F}_q$;

- a positive integer, $m \in \mathbb{N}$, the number of rows of our matrices;

- a positive integer, $n \in \mathbb{N}$, the number of columns of our matrices;

- a positive integer, $k \in \mathbb{N}$, the length of the secret vector $\mathbf{x}$, and $k + 1$ is the number of matrices in the public key;

- a positive integer, $r \in \mathbb{N}$, the rank of the matrix $\mathbf{E}$;

- a positive integer, $N \in \mathbb{N}$, the number of parties simulated in the MPC protocol;

- a positive integer, $\eta \in \mathbb{N}$, the extension degree to build $\mathbb{F}_{q^{m \cdot \eta}}$;

- a positive integer, $\tau \in \mathbb{N}$, the number of rounds in the signature.

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

- The security of the MinRank 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 MIRA-Additive

We quickly remind here the choice of parameters, as it is already explained in [ABCD+23].
$q = 16$ is the most efficient value, and $m$ and $n$ are chosen without constraint. Then, $r$ is
chosen (5 to 6 here), and $k$ is set as $k = (m-r)(n-r)-1$, i.e, the Rank Gilbert-Varshamov
bound. Then, the security of the parameter set must be high enough.

Once the MinRank instance parameters are chosen, we set $N = 256$ for a short version of
the signature, and $N = 32$ for a fast one. Then, $\tau$ and $\eta$ need to be such that the security
level of the signature is high enough (Section 9.1). 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. Finally, we settled on the following parameters:
<table><caption>Table 3: Parameters for MIRA 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>MIRA-128F</td><td>1</td><td>16</td><td>16</td><td>16</td><td>120</td><td>5</td><td>32</td><td>1</td><td>28</td><td>16 B</td><td>84 B</td><td>7.376 B</td></tr><tr><td>MIRA-128S</td><td>1</td><td>16</td><td>16</td><td>16</td><td>120</td><td>5</td><td>256</td><td>1</td><td>18</td><td>16 B</td><td>84 B</td><td>5.640 B</td></tr><tr><td>MIRA-192F</td><td>3</td><td>16</td><td>19</td><td>19</td><td>168</td><td>6</td><td>32</td><td>1</td><td>41</td><td>24 B</td><td>121 B</td><td>15.540 B</td></tr><tr><td>MIRA-192S</td><td>3</td><td>16</td><td>19</td><td>19</td><td>168</td><td>6</td><td>256</td><td>1</td><td>26</td><td>24 B</td><td>121 B</td><td>11.779 B</td></tr><tr><td>MIRA-256F</td><td>5</td><td>16</td><td>23</td><td>22</td><td>271</td><td>6</td><td>32</td><td>1</td><td>54</td><td>32 B</td><td>150 B</td><td>27.678 B</td></tr><tr><td>MIRA-256S</td><td>5</td><td>16</td><td>23</td><td>22</td><td>271</td><td>6</td><td>256</td><td>1</td><td>34</td><td>32 B</td><td>150 B</td><td>20.762 B</td></tr></tbody></table>

One should note that we obtain slightly larger signature size, due to rounding of bytes when *m* is odd. For MIRA-192F, we have 15.560 B, MIRA-192S gives 11.792 B, MIRA-256F, 27.732 B and MIRA-256S 20.796 B.

We also give some theoretical signature sizes for other parameters, such as the following one, used in [ARZV22] achieving the security level 1. With $(q, m, n, k, r) = (16, 16, 16, 142, 4)$, it is possible to obtain 5.550 Bytes (with short MIRA).

For the security level 3, it would also be possible to use the parameter (16, 19, 19, 195, 5), which gives a size of 11.636 Bytes, however, the security of the instance is lower than the parameter we chose.

Overall, although it is possible to obtain slightly smaller signature sizes with other parameters, we choose to get slightly bigger signature (less than 100 bytes of difference) with a more conservative security (around 10 bits higher). We refer to the section 9.2, Table6 for the security of our parameter sets.

## 5.2 MIRA-Threshold

Note that in [ABCD$^{+}$23], two different variant of MIRA 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 MinRank problem: with the threshold technique, we obtain faster verification but with a degraded signature size, for similar signing time. 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 MIRA.

*Benchmark platform.* Benchmark platform. The benchmarks have been performed on an Intel 13th Gen Intel (R) Core(TM) i9-13900K machine with 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 10 random instances. To minimize biases from background tasks running on the benchmark platform, each instance has been repeated 10 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 MIRA reference implementation.</caption><thead><tr><th>Instance</th><th>Key Generation</th><th>Sign</th><th>Verify</th></tr></thead><tbody><tr><td>MIRA-128F</td><td>104.5 K</td><td>38.9 M</td><td>38.0 M</td></tr><tr><td>MIRA-128S</td><td>104.3 K</td><td>53.9 M</td><td>50.0 M</td></tr><tr><td>MIRA-192F</td><td>281.6 K</td><td>134.3 M</td><td>134.1 M</td></tr><tr><td>MIRA-192S</td><td>280.3 K</td><td>154.6 M</td><td>152.9 M</td></tr><tr><td>MIRA-256F</td><td>675.6 K</td><td>342.4 M</td><td>350.0 M</td></tr><tr><td>MIRA-256S</td><td>665.7 K</td><td>387.6 M</td><td>376.4 M</td></tr></tbody></table>

## 6.2 Optimized Implementation

The performance concerning the reference 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 MIRA optimized implementation.</caption><thead><tr><th>Instance</th><th>Key Generation</th><th>Sign</th><th>Verify</th></tr></thead><tbody><tr><td>MIRA-128F</td><td>112.0 K</td><td>37.4 M</td><td>36.7 M</td></tr><tr><td>MIRA-128S</td><td>112.0 K</td><td>46.8 M</td><td>43.9 M</td></tr><tr><td>MIRA-192F</td><td>288.8 K</td><td>107.2 M</td><td>107.0 M</td></tr><tr><td>MIRA-192S</td><td>286.3 K</td><td>119.7 M</td><td>116.2 M</td></tr><tr><td>MIRA-256F</td><td>706.0 K</td><td>322.3 M</td><td>323.2 M</td></tr><tr><td>MIRA-256S</td><td>694.8 K</td><td>337.7 M</td><td>331.4 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 MinRank instance. We expect our parameters to offer the security required for each security category. For the hardness of solving a MinRank instance, we refer to the following section, as well as the design document [ABCD+23], where we describe the best attacks on the MinRank problem, namely, the kernel attack, the Support Minor Modeling, and the Minors 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.

Moreover, our signature scheme originates from a zero-knowledge proof of knowledge. The proofs of soundness and zero-knowledge of the proof of knowledge can be found in [ABCD+23].

For the unforgeability of the scheme, we have the following theorem (the hash functions $H_i$ correspond, in order, to the hash function we use in the scheme):

**Theorem 1.** Let the PRG used be $(t, \epsilon_{PRG})$-secure, and assume an adversary running in time $t$ has advantage at most $\epsilon_{MR}$ against the underlying MinRank problem. Let further assume that $H_0, H_1, H_2, H_3, H_4$ behave as random oracles, with an output of $2\lambda$ bits. Then,
if an adversary makes $q_i$ queries to $H_i$, $q_S$ queries to the signing oracle, and runs in time at most $t$, their probability to produce a forgery (EUF-CMA) for the MIRA Additive Signature Scheme is upper bounded as:

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

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

We refer to the design document ([ABCD+23]) for a proof of this theorem.

To resume, we have an EUF-CMA secure signature scheme, relying on the hardness of solving the MinRank scheme. For each security level (1,3, and 5), the parameters are taken such that:

- Solving the MinRank instance comply to the target NIST security category;

- Forging a valid signature without knowing the secret key (with high probability) requires $2^{\lambda}$ hash computations under the best known forgery attack;

- Access to a signing oracle 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 unforgeability security proof, they are modelled as random oracles. In practice, we use SHAKE and SHA3 functions, which are collision resistant and preimage resistant. With Grover's algorithm, the complexity to find a preimage is of $O(2^{\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 (see [Ber09]). Hence, as many other cryptosystems, we consider here that a hash function with an output of $2 \cdot \lambda$ bits provides a quantum 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 of parameters we consider which are close to the Gilbert-Varshamov bound, combinatorial and algebraic attack behave similarly. Therefore, in practice, resistance to quantum attacks shall be obtained by roughly dividing by 2 the classical security level.

# 9 Analysis of known attacks

## 9.1 Kales and Zaverucha attack on the Fiat-Shamir transform

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. However, it is not the most efficient.

Kales and Zaverucha proposed in [KZ20] a forgery achieved by guessing separately the two challenge of the protocol. It results an additive cost rather than the expected multiplicative cost. The cost associated with forging a transcript that passes the first 5 rounds of the Proof of Knowledge relies on achieving an optimal tradeoff between the work needed for passing the first step and the work needed for passing the second step. To achieve the attack, one can find an optimal number of repetitions with the formula:

$$ \tau' = \arg \min_{0 \le \tau' \le \tau} \left\{ \frac{1}{P_1} + \left( \frac{1}{P_2} \right)^{\tau - \tau'} \right\} $$

where $P_1$ and $P_2$ are the probabilities to pass respectively the first challenge $\tau'$ times among the $\tau$ repetitions and the second challenge one time.

In our case, one obtains the following cost of forgery:

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

where $p$ is the false positive rate of the protocol $\Pi^\eta$, i.e, $p = \frac{2}{q^{m\eta}} - \frac{1}{q^{2m\eta}}$

## 9.2 Attacks on MinRank

We describe in this section the most effective attacks on MinRank. To begin with, there is an approach, which is efficient on all the attacks, namely, the hybrid approach.

*Hybrid approach* As shown in [BBB+22, Section 5], solving a MinRank problem of parameters $(q, m, n, K, r)$ amount to solve $q^{ar}$ smaller MinRank problems of parameters $(q, m, n - a, K - am, r)$. The idea is to multiply the matrix $M$ on the right by a random $n \times n$ invertible matrix $P$ and make the bet that the new matrix has its first $a$ columns equal to zero:

$$ MP = (0_{m \times a} \tilde{M}). $$

As $M$ has rank $r$, it can be written $M = SC$ with $S \in \mathbb{F}_q^{m \times r}$ of rank $r$ and $C \in \mathbb{F}_q^{r \times n}$, and cancelling the first $a$ columns of $MP$ corresponds to the cancellation of the first $a$ columns of $CP$, which has a probability $\Omega(q^{-ar})$ to happen. This leads to a smaller MinRank problem, obtained by eliminating $am$ variables $x_i$ (using the $am$ linear equations coming from the cancellation of the $a$ columns of $MP$) in the matrix $\tilde{M}$, that has still rank $r$. This new problem has parameters $(q, m, n - a, K - am, r)$.

If a solution to the small instance is found, then the solution of the original problem can be recovered by multiplying it on the right by $P^{-1}$. The cost of this approach is

$$ \min_a (q^{ar} \mathbb{C}_A(q, m, n - a, K - am, r)) \quad (1) $$
where $C_A(q, m, n, K, r)$ is the cost of an algorithm $A$ to solve a MinRank problem.

The cost of the transformation is $2mn^{\omega-1} + 3n^{\omega}$ (for the multiplication by $P$, computation and multiplication by $P^{-1}$) + $3(am)^{\omega-1}K$ (for the linearization of the $am$ linear equations) + $am^2(n-a)(K-am)$ (for the elimination of $am$ variables $x$), which is negligible.

### 9.2.1 The kernel attack

The kernel attack was described by Goubin and Courtois in [GC00]. The idea of the attack is to take random vectors, and hoping that they are in the kernel of $E$. Since $E$ is of size $m \times n$, and is of rank at most $r$, $\text{Ker}(E)$ will be a matrix of dimensions $n \times (n-r)$ at least. Thus, if $v \leftarrow \mathbb{F}_q^n$, $\text{Pr}[v \in \text{Ker}(E)] = \frac{q^{n-r}}{q^n} = \frac{1}{q^r}$. Then, if we get $l$ independent vectors in $\text{Ker}(E)$, and set the matrix $X$ whose columns are the $l$ vectors, we can compute $(M_0 + \sum_{i=1}^k x_i M_i)X$, which gives us a linear system in $x_1...x_k$, and $m \cdot l$ equations (since we have $(M_0 + \sum_{i=1}^k x_i M_i)X = 0$). Thus with $l = \lfloor \frac{k}{m} \rfloor$, we have a unique solution to the system, which we can find with linear algebra.

As to the complexity of the attack, it is quite obvious that it is in $O(q^{r \lfloor \frac{k}{m} \rfloor})$ to find the vectors in the kernel, and in $O(k^\omega)$ to solve the linear system. Hence, the total complexity is

$$O(q^{r \lfloor \frac{k}{m} \rfloor} k^{\omega})$$

### 9.2.2 Algebraic attacks

*Kipnis-Shamir Modeling* The first algebraic modeling was proposed in [KS99]. It consists in solving with algebraic techniques the system coming from the kernel attack, the unknowns being the $x_i$'s and the entries of the matrix $X$. However, its complexity is not well understood, in particular because, according to [BB22], the Gröbner basis computation will produce the Minors and Support Minors equations that we describe below. It is then more interesting from the computational point of view to directly consider the Minors or Support Minors modelings.

*Minors Modeling* This modeling was presented and analyzed in [FSS10, FSS13]. The algebraic system consists of all the minors of size $r+1$ of the formal matrix $M = M_0 + \sum_{i=1}^k x_i M_i$, whose entries are linear forms in the unknowns $x_i$'s. This is a determinantal system, whose Hilbert series is given by

$$HS(t) \stackrel{\text{def}}{=} \left[ (1-t)^{(m-r)(n-r)-(k+1)} \frac{\det(A(t))}{t^{\binom{k}{2}}} \right], \\ \text{with } A(t) = \left( \sum_{\ell=0}^{\max(m-i,n-j)} \binom{m-i}{\ell} \binom{n-j}{\ell} t^{\ell} \right)_{1 \le i \le r, 1 \le j \le r}$$
where for a series $S \in \mathbb{Z}[[t]]$, $[S]$ denotes the series obtained by truncating $S$ at the first non-positive coefficient.

As long as $k < (m-r)(n-r)$, the series is a polynomial, and the degree of regularity $D$ of the system is $\deg(HS) + 1$. The complexity of the Gröbner basis computation can then be estimated as the cost of computing the echelon form on the Macaulay matrix of the system in degree $D$ that has $\binom{k+D}{D}$ columns and almost the same rank. As shown in [GND23], it is possible to refine the F5 algorithm to construct subs-matrices of the Macaulay matrices with a number of rows equal to its rank. Even if this algorithm has not been designed yet for the Minors modeling for any parameters set, we estimate the complexity of computing the echelon form as

$$O\left(\binom{k+D}{D}^{\omega}\right), \quad D = \deg(HS(z)) + 1.$$

with $\omega$ the linear algebra constant. In all our estimates, we use conservatively $\omega = 2$.

*Support Minors Modeling* The Support Minors modeling was introduced in [BBC$^+$20]. The idea is to consider the vector space generated by the rows of $M$, that has rank $r$, to introduce a formal matrix $C \in \mathbb{F}_q[c_{i,j}]^{r \times n}$ representing a generator matrix of this vector space. As $C$ is a basis for the rows of $M$, each row $m_i$ of $M$ is a linear combination of the rows of $C$. This leads to the algebraic system

$$\text{SupportMinors} = \left\{ \text{MaximalMinors} \left( \binom{m_i}{C} \right) : m_i \text{ row of } M \right\}.$$

Considering the maximal minors of $C$ as new variables, the system consists of bilinear equations in the $x_i$'s and the minors of $C$. It is conjectured in [BBC$^+$20], based on a theoretical analysis of the system and some experimental heuristics, that it is possible to solve this bilinear system by linear algebra on a sub-matrix of the Macaulay matrix at augmented degree $b \le \min(q-1, r+1)$ in the $x_i$'s, that contains $N_b$ rows and $M_b$ columns:

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

$$M_b = \binom{k+b-1}{b} \binom{n}{r}. \qquad (3)$$

The degree $b$ is computed as the smallest degree such that $N_b \ge M_b - 1$. In this case, the final cost in $\mathbb{F}_q$ operations is given by

$$\mathcal{O}(N_b M_b^{\omega-1}),$$

where $\omega$ is the linear algebra constant.
<table><caption>Table 6: Complexity of the MinRank attacks for the proposed parameters. $a$ is the hybrid parameter used for each attack, $b$ the degree for the Support Minors modeling, $D$ the degree for the Minors modeling. The complexities are given in $\log_2$ bit operations. We use $\omega = 2$.</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>a</th><th>kernel</th><th>a</th><th>b</th><th>SM</th><th>a</th><th>D</th><th>Minors</th></tr></thead><tbody><tr><td>MIRA-128</td><td>1</td><td>16</td><td>16</td><td>16</td><td>120</td><td>5</td><td>8</td><td>167</td><td>7</td><td>1</td><td>169</td><td>4</td><td>9</td><td><strong>164</strong></td></tr><tr><td>MIRA-192</td><td>3</td><td>16</td><td>19</td><td>19</td><td>168</td><td>6</td><td>9</td><td>225</td><td>6</td><td>7</td><td>231</td><td>6</td><td>9</td><td><strong>221</strong></td></tr><tr><td>MIRA-256</td><td>5</td><td>16</td><td>23</td><td>22</td><td>271</td><td>6</td><td>12</td><td>297</td><td>10</td><td>4</td><td>302</td><td>7</td><td>13</td><td><strong>290</strong></td></tr></tbody></table>

We observe in Table 6 that in the range of parameters around the Rank Gibert-Varshamov bound ($k = (n-r)(m-r) - 1$), all attacks give the same order of complexity, the Minors modeling being a little more efficient as it uses only one set of variables.

# 10 Advantages and limitations

## 10.1 Advantages

The MIRA scheme enjoys the following advantages:

**Difficulty of the problem.** MinRank is an NP-Complete problem that has been significantly studied for some time. It already has a central role in cryptography, being used in several cryptosystems, and in some attacks in multivariate cryptography. The MIRA scheme relies on the hardness of random non-structured MinRank instance which is a conservative assumption.

**No cyclic structure.** In particular, and unlike other cryptosystems, the MinRank instance used in MIRA does not rely on a cyclic structure for which the quantum security is more questionable.

**Size of public keys + signature.** The sum of the sizes of public keys and signature is, for example, less than twice as big as in Dilithium for the NIST security level 1, thanks to our small public key (3.7 kB for Dilithium2 compared to 5.7 kB for our level 1 security instance). As a result, it is one of the shortest signature among the MPCitH-based schemes.

**Resilience against MinRank attacks:** Because of the way the size of the signature is obtained: one part is related to the MPC and only dependent on the security level and one part is related to the parameters of the problem in themselves, increasing the size of the problem parameters has a mitigated impact on the total size of the signature. For example, the short signature size's is 5.6 kB for the set of parameters $(q, m, n, k, r) = (16, 16, 16, 120, 5)$ for the level 1 of security. If we choose the parameters $(q, m, n, k, r) = (16, 19, 19, 168, 6)$, which reaches more than 192 bits of security for the underlying cryptographic problem, the
signature size will only be 6.3 kB to reach the level 1 of security. Thus, if one later discovers
effective attacks against the MinRank problem that force us to increase the parameters,
the size of the signatures will only be impacted that much.

**10.2 Limitations**

MIRA also suffers the following 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 both the MinRank instance and the number of repetitions need to increase linearly, since both the Fiat-Shamir transform and the MinRank instance need to be secure (we see that going from level 1 to 3, the number of repetitions is increased by almost half, while the MinRank instance grows as well).

**Signature speed.** Our scheme is slower than lattice-based signature schemes but compares well in general with other signature schemes.

**Implementation.** This scheme is relatively complex to implement. It might be particularly heavy for low-cost devices such as smart cards or embedded systems, although it has potential to perform well on hardware as being highly parallelizable.
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. Cryptology ePrint Archive, Paper 2002/022, 2002. https://eprint.iacr.org/2002/022.

ABCD<sup>+23</sup>. Nicolas Aragon, Loïc Bidoux, Jesús-Javier Chi-Domínguez, Thibauld Feneuil, Philippe Gaborit, Romaric Neveu, and Matthieu Rivain. MIRA: a Digital Signature Scheme based on the MinRank problem and the MPC-in-the-Head paradigm. arXiv, 2023.

AMGH<sup>+22</sup>. Carlos Aguilar-Melchor, Nicolas Gama, James Howe, Andreas Hülsing, David Joseph, and Dongze Yue. The Return of the SDitH. Cryptology ePrint Archive, Paper 2022/1645, 2022. https://eprint.iacr.org/2022/1645.

ARZV22. Gora Adj, Luis Rivera-Zamarripa, and Javier Verbel. MinRank in the Head: Short Signatures from Zero-Knowledge Proofs. Cryptology ePrint Archive, Paper 2022/1501, 2022. https://eprint.iacr.org/2022/1501.

BB22. Magali Bardet and Manon Bertin. Improvement of Algebraic Attacks for Solving Superdertermined MinRank Instances. In Jung Hee Cheon and Thomas Johansson, editors, pqcrypto 2022, volume 13512 of lncs, pages 107-123, Cham, September 2022. Springer International Publishing.

BBB<sup>+22</sup>. Magali Bardet, Pierre Briaud, Maxime Bros, Philippe Gaborit, and Jean-Pierre Tillich. Revisiting Algebraic Attacks on MinRank and on the Rank Decoding Problem. Cryptology ePrint Archive, Paper 2022/1031, 2022. https://eprint.iacr.org/2022/1031.

BBC<sup>+20</sup>. 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, pages 507-536. Springer International Publishing, 2020.

Ber09. Daniel Bernstein. Cost analysis of hash collisions: Will quantum computers make sharcs obsolete. 01 2009.

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.

Fen22. Thibauld Feneuil. Building MPCitH-based Signatures from MQ, MinRank, Rank SD and PKP. Cryptology ePrint Archive, Paper 2022/1512, 2022. https://eprint.iacr.org/2022/1512.

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. https://eprint.iacr.org/2022/1407.

FS87. Amos Fiat and Adi Shamir. How to prove yourself : practical solutions to identification and signature problems. In Andrew M. Odlyzko, editor, CRYPTO'86, volume 263 of LNCS, pages 186-194. Springer, Heidelberg, 1987.

FSS10. Jean-Charles Faugère, Mohab Safey El Din, and Pierre-Jean Spaenlehauer. Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology. In International Symposium on Symbolic and Algebraic Computation, ISSAC 2010, Munich, Germany, July 25-28, 2010, pages 257-264, 2010.

FSS13. Jean-Charles Faugère, Mohab Safey El Din, and Pierre-Jean Spaenlehauer. On the complexity of the generalized minrank problem. JSC, 55:30-58, 2013.

GC00. Louis Goubin and Nicolas T. Courtois. Cryptanalysis of the TTM Cryptosystem. In International Conference on the Theory and Application of Cryptology and Information Security, 2000.

GND23. Sriram Gopalakrishnan, Vincent Neiger, and Mohab Safey El Din. Refined $f_5$ algorithms for ideals of minors of square matrices, 2023.

IKOS07. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Zero-knowledge from secure multiparty computation. In David S. Johnson and Uriel Feige, editors, 39th ACM STOC, pages 21-30. ACM Press, 2007.
KS99. Aviad Kipnis and Adi Shamir. Cryptanalysis of the HFE public key cryptosystem by re-linearization. In *crypto '99*, volume 1666 of LNCS, pages 19–30, Santa Barbara, California, USA, August 1999. Springer.

KZ20. Daniel Kales and Greg Zaverucha. An Attack on Some Signature Schemes Constructed From Five-Pass Identification Schemes. Cryptology ePrint Archive, Paper 2020/837, 2020. https://eprint.iacr.org/2020/837.

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