11institutetext:  Naquidis Center, Talence, France 22institutetext: Technology
Innovation Institute, UAE 33institutetext: Sorbonne Université, CNRS, INRIA,
Institut de Mathématiques
de Jussieu-Paris Rive Gauche, Ouragan, Paris, France 44institutetext:
CryptoExperts, Paris, France 55institutetext: University of Limoges, France

# MIRA: a Digital Signature Scheme based on the MinRank problem and the MPC-
in-the-Head paradigm

Nicolas Aragon 11 Loïc Bidoux 22 Jesús-Javier Chi-Domínguez 22 Thibauld
Feneuil 3344
Philippe Gaborit 55 Romaric Neveu 55 Matthieu Rivain 44

###### Abstract

We exploit the idea of [Fen22] which proposes to build an efficient signature
scheme based on a zero-knowledge proof of knowledge of a solution of a MinRank
instance. The scheme uses the MPCitH paradigm, which is an efficient way to
build ZK proofs. We combine this idea with another idea, the hypercube
technique introduced in [AMGH+22], which leads to more efficient MPCitH-based
scheme. This new approach is more efficient than classical MPCitH, as it
allows to reduce the number of party computation. This gives us a first scheme
called MIRA-Additive. We then present an other scheme, based on low-threshold
secret sharings, called MIRA-Threshold, which is a faster scheme, at the price
of larger signatures. The construction of MPCitH using threshold secret
sharing is detailed in [FR22]. These two constructions allows us to be faster
than classical MPCitH, with a size of signature around $5.6$kB with MIRA-
Additive, and $8.3$kB with MIRA-Threshold. We detail here the constructions
and optimizations of the schemes, as well as their security proofs.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Notations and Conventions
      1. 2.1.1 Pseudorandom Generators
      2. 2.1.2 Collision-Resistant Hash Functions
      3. 2.1.3 Commitments Schemes
      4. 2.1.4 Merkle Trees
      5. 2.1.5 Secret Sharing Schemes
    2. 2.2 Proof of Knowledge and Digital Signature Schemes
      1. 2.2.1 Zero-Knowledge Proof of Knowledge
      2. 2.2.2 Fiat-Shamir Transformation
      3. 2.2.3 Useful Lemmas
      4. 2.2.4 q-Polynomials and Rank Metric definition
    3. 2.3 MPC-in-the-Head and Proof of Knowledge
    4. 2.4 The MinRank Problem
      1. 2.4.1 Key Generation
    5. 2.5 Rank Checking MPC protocol
  3. 3 Description of the Protocols
    1. 3.1 Description of MIRA-Additive
      1. 3.1.1 Proof of Knowledge with Additive Secret Sharing Scheme
      2. 3.1.2 MIRA-Additive
    2. 3.2 Description of MIRA-Threshold
      1. 3.2.1 Proof of Knowledge with Threshold Secret Sharing
      2. 3.2.2 MIRA-Threshold
  4. 4 Parameter Sets
    1. 4.1 Parameters Choice
    2. 4.2 Key and Signature Sizes
      1. 4.2.1 Additive Protocol Signature Size
      2. 4.2.2 Threshold Protocol Signature Size
  5. 5 Security Analysis
    1. 5.1 Security Proofs for the Proofs of Knowledge
      1. 5.1.1 Security Proofs for the Additive Protocol
      2. 5.1.2 Security Proofs for the Threshold Sharing Protocol
    2. 5.2 Security proofs for the Signature Schemes
      1. 5.2.1 Security Analysis of MIRA-Additive
      2. 5.2.2 Security Analysis of MIRA-Threshold
  6. 6 Known Attacks
    1. 6.1 Attacks against Fiat-Shamir Signatures
      1. 6.1.1 Cost of forgery of MIRA-Additive
      2. 6.1.2 Cost of forgery of MIRA-Threshold
    2. 6.2 Attacks against MinRank
      1. 6.2.1 The Kernel Attack
      2. 6.2.2 Algebraic Attacks

##  1 Introduction

MIRA is a signature scheme designed to be secure against attacks from a
quantum computer. The scheme is based on the MPC-in-the-Head paradigm and its
security relies on the hardness to solve the MinRank problem. The underlying
proof of knowledge uses symmetric functions as ingredients, such as hash
functions and commitment schemes.

In section 2, we remind the reader some notations and definitions. We remind
as well the MPC protocol we will use. In section 3, we describe the two
variants of the MPCitH scheme, one using additive secret sharing, the other
using threshold secret sharing. Then, section 4 explains the choice of
parameters, and the obtained theoretical sizes. Section 5 deals with the
security proofs of both schemes. Finally, section 6 is dedicated to the
security of the scheme regarding to the Fiat-Shamir transform and the MinRank
problem.

In our schemes, the MPC protocol we use is the linearized-polynomial protocol
on MinRank described in [Fen22]. The hypercube MPCitH idea comes from
[AMGH+22], while the threshold MPCitH one from [FR22].

##  2 Preliminaries

###  2.1 Notations and Conventions

Let $A$ a randomized algorithm. We write $y\leftarrow A(x)$ the output of the
algorithm for the output $x$. If $S$ is a set, we write
$x\overset{\;\$}{\longleftarrow}S$ the uniform sampling of a random element
$x$ in $S$. We write $x\overset{\;\$,s}{\longleftarrow}S$ the pseudo-random
sampling in $S$ with seed $s$.

We denote the set of integers between $1$ and $N$ by $[1,N]$, which can be
shortened in $[N]$.

We denote by $\mathbb{F}_{q}$ the finite field of order $q$. We use bold
letters to denote vectors or matrices (for example,
$\bm{u}\in\mathbb{F}_{q}^{n}$ and $u\in\mathbb{F}_{q}$).

A function $\mu:\mathbb{N}\rightarrow\mathbb{R}$ is said negligible if, for
every positive polynomial $p(\cdot)$, there exists an integer $N_{p}>0$ such
that for every $\lambda>N_{p}$, we have $|\mu(\lambda)|<1/p(\lambda)$. When
not made explicit, a negligible function in $\lambda$ is denoted
$negl(\lambda)$ while a polynomial function in $\lambda$ is denoted
$poly(\lambda)$. We further use the notation poly($\lambda_{1}$,
$\lambda_{2}$, …) for a polynomial function in several variables.

Two distributions $\\{D_{\lambda}\\}_{\lambda}$ and
$\\{E_{\lambda}\\}_{\lambda}$ indexed by a security parameter $\lambda$ are
$(t,\epsilon)$-indistinguishable (where $t$ and $\epsilon$ are
$\mathbb{N}\leftarrow\mathbb{R}$ functions) if, for any algorithm
$\mathcal{A}$ running in time at most $t(\lambda)$ we have

$\mathsf{Pr}[\mathcal{A}^{D_{\lambda}}()=1]-\mathsf{Pr}[\mathcal{A}^{E_{\lambda}}()=1]\leq\epsilon(\lambda)$

with $\mathcal{A}^{Dist}$ meaning that $\mathcal{A}$ has access to a sampling
oracle of distribution $Dist$.

The two distributions are said

  * •

computationally indistinguishable if $\epsilon\in\mathsf{negl}(\lambda)$ for
every $t\in\mathsf{poly}(\lambda)$;

  * •

statistically indistinguishable if $\epsilon\in\mathsf{negl}(\lambda)$ for
every unbounded $t$;

  * •

perfectly indistinguishable if $\epsilon=0$ for every unbounded $t$.

####  2.1.1 Pseudorandom Generators

######  Definition 1 (Pseudorandom Generators)

Let $G:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{*}$, $\ell$ a polynomial such that
$G(s)\in\\{0,1\\}^{\ell(\lambda)}$. G is a $(t,\epsilon)$-secure pseudorandom
generator if:

  * •

$\ell(\lambda)>\lambda$,

  * •

the distributions $\\{G(s),s\leftarrow\\{0,1\\}^{\lambda}\\}$ and
$\\{r,r\overset{\;\$}{\longleftarrow}\\{0,1\\}^{\ell(\lambda)}\\}$ are
indistinguishable.

In some protocols, we are going to use TreePRG, which is a pseudorandom
generator, which uses a root seed to generate $N$ other seeds in a structured
way. This can be illustrated quite easily with the following figure:

$seed_{\text{root}}$ $seed_{int_{1}}$ $seed_{1}$ $seed_{2}$ $seed_{int_{2}}$
$seed_{3}$ $seed_{4}$

Figure 1: Example of TreePRG

Now, imagine one is looking to reveal $seed_{1}$, $seed_{3}$ , and $seed_{4}$,
and hide $seed_{2}$. Then, all he has to do is reveal $seed_{int_{2}}$ and
$seed_{1}$. It is impossible to retrieve $seed_{2}$, as we don’t know the
previous seed, but it is possible to retrieve the others. In this small
example, we took $N=4$. This is especially interesting when, as in the
additive-based MPCitH transformation we will see later, we reveal $N-1$
leaves. This means that we can do this operation by revealing only
$\log_{2}(N)$ leaves instead of $N-1$. In general, for a TreePRG with $N$
final seeds and given a subset $I\subset[1,N]$, it is possible to reveal all
the leaves but the ones in $I$ by revealing at most
$|I|\log_{2}(\frac{N}{|I|})$ tree nodes.

We thus have three functions in order to deal with a TreePRG:

  * •

the root seed expansion, which generates $N$ seeds from a root seed;

  * •

the sibling path derivation, which generates a sibling path from a leaf seed;

  * •

the leaf seeds retrieval from a sibling path.

####  2.1.2 Collision-Resistant Hash Functions

We are going to use hash functions in the zero-knowledge protocols. We define
below what is a collision resistant hash function.

######  Definition 2 (Collision-Resistant Hash Function)

Let $h:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{\lambda}$. It is a collision-
resistant hash function if $h$ can be computed in a polynomial time, and, for
any polynomial algorithm $\mathcal{A}$,

$\mathsf{Pr}[(x_{1},x_{2})\leftarrow\mathcal{A}(\lambda),x_{1}\neq
x_{2},h(x_{1})=h(x_{2})]<\epsilon(\lambda)$

where $\epsilon(\lambda)$ is negligeable.

####  2.1.3 Commitments Schemes

The security of the proof of knowledge relies on commitments, in order to
avoid an attacker to forge a valid transcript. The commitment scheme should
satisfy two properties: the commitment should reveal no information about the
data we committed (hiding property), and there should be only one way to open
the commitment (binding property).

######  Definition 3 (Commitment Scheme)

A commitment scheme is defined by the function $\mathsf{Com}$, which takes as
inputs ${m},\rho$ with $m$, and $\rho$, and outputs ${c}$, for some message
space, randomness space, and commitment space.

######  Definition 4 (Hiding)

A commitment scheme $Com$ is computationally (resp. statistically, resp.
perfectly) hiding if, for every $m_{0},m_{1}$, the distributions of

$\\{\mathsf{Com}(m_{0},\rho),\rho\leftarrow\mathrel{\mkern-2.0mu}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle\textnormal{\$\hskip-0.50003pt
plus 5.0pt}$}}}{\vbox{\hbox{$\textstyle\textnormal{\$\hskip-0.50003pt plus
5.0pt}$}}}{\vbox{\hbox{$\scriptstyle\textnormal{\$\hskip-0.35002pt plus
3.5pt}$}}}{\vbox{\hbox{$\scriptscriptstyle\textnormal{\$\hskip-0.25002pt plus
2.5pt}$}}}}\\}\text{ and
}\\{\mathsf{Com}(m_{1},\rho),\rho\leftarrow\mathrel{\mkern-2.0mu}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle\textnormal{\$\hskip-0.50003pt
plus 5.0pt}$}}}{\vbox{\hbox{$\textstyle\textnormal{\$\hskip-0.50003pt plus
5.0pt}$}}}{\vbox{\hbox{$\scriptstyle\textnormal{\$\hskip-0.35002pt plus
3.5pt}$}}}{\vbox{\hbox{$\scriptscriptstyle\textnormal{\$\hskip-0.25002pt plus
2.5pt}$}}}}\\}$

are computationally (resp. statistically, resp. perfectly) indistinguishable.

######  Definition 5 (Binding)

A commitment scheme $Com$ is binding if, for every PPT algorithm
$\mathcal{A}$, we have

$\mathsf{Pr}[\mathsf{Com}(m,\rho)=\mathsf{Com}(m^{\prime},\rho^{\prime})\cap
m\neq
m^{\prime},(m,\rho,m^{\prime},\rho^{\prime})\leftarrow\mathcal{A}]<\mu(\lambda)$

where $\mu$ is a negligible function. If we restrict $\mathcal{A}$ to a PPT,
it is computationally binding. If the computation time is unbounded, it is
statistically binding.

####  2.1.4 Merkle Trees

A collision-resistant hash function (that we will note $\mathsf{H}_{M}$) can
be used to build a Merkle Tree. Given inputs $v_{1}\dots v_{N}$, we define
$\mathsf{Merkle}(v_{1}\dots v_{N})$ as:

$\mathsf{Merkle}(v_{1}\dots
v_{N})=\begin{cases}\mathsf{H}_{M}\Big{(}{\mathsf{Merkle}(v_{1}\dots
v_{\frac{N}{2}})}\|{\mathsf{Merkle}(v_{\frac{N}{2}+1}\dots
v_{N})}\Big{)}\text{ if }N>1\\\ \mathsf{H}_{M}(v_{1})\text{ if }N=1\\\
\end{cases}$ (1)

Thanks to Merkle Trees, similarly to the TreePRG described above, it is
possible to verify that some given data is correct in an easy way. Given
$I\subset[1,N]$, it is possible to verify that the $(v_{i})_{i\in I}$ were
indeed used to build the Merkle Tree only by revealing at most
$|I|\log_{2}\Big{(}\frac{N}{|I|}\Big{)}$ hash values, by revealing the sibling
paths of the $(v_{i})_{i\in I}$. This path is called the authentification path
and is denoted $\mathsf{auth}((v_{1}\dots v_{N}),I)$.

####  2.1.5 Secret Sharing Schemes

The interactive proof relies on a prover simulating a MultiParty Computation
(MPC) protocol, where each party has a share of the witness $\bm{x}$. We
detail here the formalism from [FR22]. The sharing of a secret $s$ among $N$
parties is denoted $(\llbracket s\rrbracket_{1},\dots,\llbracket
s\rrbracket_{N})$ where $\llbracket s\rrbracket_{i}$ is the share of the $i$th
party. Given $J\subset[1,N]$, $\llbracket s\rrbracket_{J}$ is the subset of
shares $\\{\llbracket s\rrbracket_{j}\\}_{j\in J}$.

######  Definition 6 (Threshold Linear Secret Sharing)

Let $\mathbb{F}$ a finite field. Let $1<t\leq N$. A $(t,N)$-threshold linear
secret sharing scheme (TLSSS) is a scheme to share a secret, $s\in\mathbb{F}$,
in a sharing $\llbracket s\rrbracket=(\llbracket
s\rrbracket_{1}\dots\llbracket s\rrbracket_{N})\in\mathbb{F}^{N}$, where only
$t$ coordinates of $\llbracket s\rrbracket$ need to be known in order to
reconstruct the secret $s$, while the knowledge of $t-1$ coordinates of
$\llbracket s\rrbracket$ reveals no information.

We can write this the following way:

$\begin{cases}\mathsf{Share}:\mathbb{F}\times R\rightarrow\mathbb{F}^{N}\\\
\mathsf{Reconstruct}_{J}:\mathbb{F}^{t}\rightarrow\mathbb{F}\\\ \end{cases}$
(2)

$R$ corresponds to the randomness space used to build the shares. $J$ is a
subset of $\\{1\dots N\\}$, with $|J|=t$. The two algorithms of a TLSSS must
satisfy some properties:

  * •

Correctness. For every $s\in\mathbb{F},r\in R,J\subset[1,N]$ such that $|J|=t$
and for $\llbracket s\rrbracket\leftarrow\mathsf{Share}(s;r)$, we have:

$\mathsf{Reconstruct}_{J}(\llbracket s\rrbracket_{J})=s$

  * •

Perfect ($t-1$)-privacy. For every $s_{0},s_{1}\in\mathbb{F},I\subset[1,N]$
with $|I|=t-1$, the two distributions:

$\displaystyle\left\\{\llbracket s_{0}\rrbracket_{I}\text{ }\Big{|}\text{
}\genfrac{}{}{0.0pt}{0}{r\overset{\;\$}{\longleftarrow}R}{\text{ }\llbracket
s_{0}\rrbracket_{[1,N]}\longleftarrow\mathsf{Share}(s_{0},r)}\right\\}\text{
and }\left\\{\llbracket s_{1}\rrbracket_{I}\text{ }\Big{|}\text{
}\genfrac{}{}{0.0pt}{0}{r\overset{\;\$}{\longleftarrow}R}{\text{ }\llbracket
s_{1}\rrbracket_{[1,N]}\longleftarrow\mathsf{Share}(s_{1},r)}\right\\}$

are perfectly indistinguishable.

  * •

Linearity. For every
$v_{0},v_{1}\in\mathbb{F}^{t},\alpha\in\mathbb{F},J\subset[1,N]$ with $|J|=t$,

$\mathsf{Reconstruct}_{J}(\alpha\cdot
v_{0}+v_{1})=\alpha\cdot\mathsf{Reconstruct}_{J}(v_{0})+\mathsf{Reconstruct}(v_{1}).$

We recall below two among the most used secret sharing schemes.

######  Definition 7 (Additive Secret Sharing)

Let $\mathbb{F}$ a field and $s\in\mathbb{F}$ a secret. An additive secret
sharing with $N$ parties is a $(N,N)$-threshold sharing scheme such that:

  * •

$\llbracket s\rrbracket_{i}=r_{i}$ for $i\in[1,N-1]$, where
$r_{i}\overset{\;\$}{\longleftarrow}\mathbb{F}$;

  * •

$\llbracket s\rrbracket_{N}=s-\sum_{i=1}^{N-1}\llbracket s\rrbracket_{i}$.

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

######  Definition 8 (Shamir’s Secret Sharing)

Let $\mathbb{F}$ a field and $s\in\mathbb{F}$ a secret. A Shamir’s secret
sharing is the following $(\ell+1,N)$-threshold sharing scheme:

  * •

Sample
$(r_{1},\ldots,r_{\ell})\overset{\;\$}{\longleftarrow}\mathbb{F}^{\ell}$;

  * •

Compute $P(X)=s+\sum_{i=1}^{\ell}r_{i}X^{i}$;

  * •

Compute $\llbracket s\rrbracket_{i}=P(e_{i})$ where the
$(e_{i})_{i\in\\{1,\dots,N\\}}$ are distinct and non-zero public values.

For $J$ a subset of $[1,N]$ with $|J|=\ell+1$, the $\mathsf{Reconstruct}_{J}$
algorithm corresponds to the interpolation of the polynomial P, when taking in
inputs $\llbracket s\rrbracket_{i}$ for $i\in J$, and outputs the constant
term, $s$.

###### Proposition 1

Let an $(\ell+1,N)$-threshold LSSS. For each $v\in\mathbb{F}^{\ell+1}$ and
each subset $J\subset[1,N]$ of $\ell+1$ elements, there exists a unique
sharing $\llbracket x\rrbracket_{[1,N]}\in\mathbb{F}^{N}$ such that
$\llbracket x\rrbracket_{J}=v$, and such that for all
$\mathcal{J}\subset[1,N]$ of $\ell+1$ elements:

$\mathsf{Reconstruct}_{\mathcal{J}}(\llbracket
x\rrbracket_{\mathcal{J}})=\mathsf{Reconstruct}_{J}(v)$

###### Proof

See [FR22].

One deduces there exists an algorithm $\mathsf{Expand}_{J}$ which returns the
unique sharing from a subset $J$ of the shares. For example, in the Shamir’s
secret sharing, $\mathsf{Expand}_{J}$ builds the Lagrange polynomial from the
known evaluations and outputs the image of each party’s point.

###  2.2 Proof of Knowledge and Digital Signature Schemes

####  2.2.1 Zero-Knowledge Proof of Knowledge

We define here the concept of proof of knowledge. Let
$R\subset\\{0,1\\}^{*}\times\\{0,1\\}^{*}$ an NP-relation. $(x,\omega)\in R$
is a statement-witness pair where $x$ is the statement and $\omega$ an
associated witness. The set of valid witnesses for a statement $x$ is
$R(x)=\\{\omega:(x,\omega)\in R\\}$. A prover $\mathcal{P}$ wants to use a
proof of knowledge to convince a verifier $\mathcal{V}$ that he knows a
witness $\omega$ for a statement $x$.

######  Definition 9 (Proof of knowledge)

A proof of knowledge for a relation $R$ with soundness $\epsilon$ is a two-
party protocol between a prover $\mathcal{P}$ and a verifier $\mathcal{V}$
with a public statement $x$, where $\mathcal{P}$ want to convince
$\mathcal{V}$ that he knows $\omega$ such that $(x,\omega)\in R$. We denote
$\\{\mathcal{P}(x,\omega),\mathcal{V}(x)\\}$ the transcript between
$\mathcal{P}$ and $\mathcal{V}$. A proof of knowledge has the following
properties:

  * •

Perfect completeness:  If $(x,\omega)\in\mathcal{R}$, then a prover
$\mathcal{P}$ who knows a witness $\omega$ for $x$ succeeds in convincing the
verifier $\mathcal{V}$ of his knowledge. This means that the prover convinces
the verifier with probability 1, i.e,

$\mathsf{Pr}[\langle\mathcal{P}(x,\omega),\mathcal{V}(x)\rangle\rightarrow\text{ACCEPT}]=1.$

  * •

Soundness:  If there exists a PPT prover $\tilde{\mathcal{P}}$ such that

$\tilde{\epsilon}=\mathsf{Pr}[\langle\tilde{\mathcal{P}}(x),\mathcal{V}(x)\rangle\rightarrow\text{ACCEPT}]>\epsilon,$

then there exists an algorithm which, given rewindable black-box access to
$\tilde{\mathcal{P}}$, outputs a witness $\omega^{\prime}$ for x in time
$\mathsf{poly}(\lambda,(\tilde{\epsilon}-\epsilon)^{-1})$ with probability at
least $\frac{1}{2}$.

To be zero-knowledge while the prover interacts with a honest verifier (i.e.,
a verifier sending his messages according to the definition of the protocol),
the PoK must verify the following property :

######  Definition 10 (Honest-Verifier Zero-Knowledge)

A PoK satisfies the Honest-Verifier Zero-Knowledge (HZVK) property if there
exists a polynomial-time simulator $\mathsf{Sim}$ that given as input a
statement $x$ and random challenges $(\mathsf{ch}_{1},...,\mathsf{ch}_{n})$,
outputs a transcript
$\\{\mathsf{Sim}(x,\mathsf{ch}_{1},...,\mathsf{ch}_{n}),\mathcal{V}(x)\\}$
which is computationally indistinguishable from the probability distribution
of transcripts of honest executions between a prover $\mathcal{P}(x,w)$ and a
verifier $\mathcal{V}(x)$.

######  Definition 11 (Digital Signature Scheme)

A digital signature scheme $\mathsf{DSS}$ with security parameter $\lambda$ is
a triplet of polynomial time algorithms
$(\mathsf{KeyGen},\mathsf{Sign},\mathsf{Verif})$ such that:

  * •

The key-generation algorithm $\mathsf{KeyGen}$ is a probabilistic algorithm
which outputs a pair of keys $(\mathsf{pk},\mathsf{sk})$.

  * •

The signing algorithm $\mathsf{Sign}$, eventually probabilistic, which takes
as inputs a message $m$ to sign and the secret key $\mathsf{sk}$, and outputs
a signature $\sigma$.

  * •

The verification algorithm $\mathsf{Verif}$ which takes as inputs the public
key $\mathsf{pk}$, the message $m$ and its signature $\sigma$, and outputs a
bit $b$. The output $1$ means that the signature is considered as valid.

A correct signature scheme satisfies the following property: if
$(\mathsf{\vphantom{p}pk},\mathsf{\vphantom{p}sk})\leftarrow\mathsf{KeyGen}$,
for all messages $m$ signed by
$\sigma\leftarrow\mathsf{Sign}(\mathsf{\vphantom{p}pk},m)$, we have
$1\leftarrow\mathsf{Verif}(\mathsf{\vphantom{p}sk},m,\sigma)$. This means, if
a signature is correctly generated, then it is always accepted.

The standard security notion for digital signature schemes is existential
unforgeability under adaptive chosen message attacks (EUF-CMA) is defined as
follows:

######  Definition 12 (EUF-CMA)

We can define the following game $G_{\textsc{euf-cma}}$ where
${\mathsf{Sign}(sk,\cdot)}$ is an oracle that sign messages:

$\displaystyle\textsl{($\mathsf{\vphantom{p}pk}$,$\mathsf{\vphantom{p}sk}$)}\leftarrow\mathsf{KeyGen}()$
$\displaystyle(m^{*},\sigma^{*})\leftarrow\mathcal{A}^{\mathsf{Sign}(\mathsf{\vphantom{p}sk},\cdot)}(\textsf{pk})$
$\displaystyle(m,\sigma)\leftarrow\mathcal{A}$

The game returns $1$ if $\mathsf{Verif}(m,\sigma,\textsf{pk})=1$ and $m$ was
not queried to ${\mathsf{Sign}(\mathsf{\vphantom{p}sk},\cdot)}$. The signature
scheme is EUF-CMA secure if, for every polynomial adversary $\mathcal{A}$,
$\mathsf{Pr}[G_{\textsc{euf-cma}}(\mathcal{A})=1]$ is negligible.

####  2.2.2 Fiat-Shamir Transformation

The Fiat-Shamir (FS) transformation is a generic process allowing to convert
an interactive identification scheme into a signature. The main adaptation
lies in the removal of the interactions in the protocol: one needs to pull the
challenges in a deterministic way to sign a message without the assistance of
a verifier. Note that the protocol must be repeated several times to achieve
the desired level of security. We note $\tau$ the number of repetitions. One
will see in section 6.1 that there is an effective attack if $\tau$ is too
small.

Let us describe the FS tranformation on a 5-round zero-knowledge proof of
knowledge. Concretely, the prover begins as in the zero-knowledge proof by
committing all the auxiliary information. At the end of the first step, the
prover computes:

$h_{1}=\mathsf{H}_{1}(\mathsf{salt},m,(h^{(e)}_{0})_{e\in[1,\tau]})$

where $\mathsf{H}_{1}$ is an hash function, $h^{(e)}_{0}$ is the first step
commitment of the $e^{\text{th}}$ execution of the protocol, and
$\mathsf{salt}$ a random value in $\\{0,1\\}^{2\lambda}$. The prover obtains
the first challenge (one challenge per execution $e\in[1,\tau]$) from $h_{1}$
by using a XOF (Extendable Output Function).

The second challenge is generated in a similar way: the prover computes an
element $h_{2}$ thanks to an other hash function $\mathsf{H}_{2}$ and the
other information computed during the step 3. The prover obtains the second
challenge (one challenge per execution $e\in[1,\tau]$) from $h_{2}$ by using a
XOF as well.

The signature $\sigma$ therefore consists of sending:

  * •

the salt $\mathsf{salt}$;

  * •

$h_{1}$ as commitment of the initial values;

  * •

$h_{2}$ as hash of all responses of the first challenge;

  * •

each response $\mathsf{rsp}$ of the second challenge.

The signature is:

$\sigma=(\mathsf{salt},h_{1},h_{2},(\mathsf{rsp}^{(e)})_{e\in[1,\tau]}).$

####  2.2.3 Useful Lemmas

######  Lemma 1 (Splitting Lemma)

Let $A\subset X\times Y$ such that $\mathsf{Pr}[(x,y)\in A]\geq\epsilon$. For
any $\alpha<\epsilon$, let us define

$B=\Big{\\{}(x,y)\in X\times Y\mid\mathsf{Pr}_{y^{\prime}\in
Y}[(x,y^{\prime})\in A]\geq\epsilon-\alpha\Big{\\}}\text{ and
}\bar{B}=(X\times Y)\setminus B.$

Then we have

  * •

$\mathsf{Pr}[B]\geq\alpha$,

  * •

$\forall(x,y)\in B,\mathsf{Pr}_{y^{\prime}\in Y}[(x,y^{\prime})\in
A]\geq\epsilon-\alpha$,

  * •

$\mathsf{Pr}[B|A]\geq\frac{\alpha}{\epsilon}$.

###### Proof

An interested reader can refer to [PS00].

####  2.2.4 q-Polynomials and Rank Metric definition

One of the main tools we are going to use are q-polynomials, as they allow us
to characterize linear subspaces.

######  Definition 13 (q-polynomial)

A q-polynomial of q-degree $r$ is a polynomial in $\mathbb{F}_{q^{m}}[X]$ of
the form:

$P(X)=X^{q^{r}}+\sum_{i=0}^{r-1}p_{i}\cdot X^{q^{i}}\qquad\text{with
}p_{i}\in\mathbb{F}_{q^{m}}.$

###### Proposition 2

Let P a q-polynomial, $\alpha,\beta\in\mathbb{F}_{q}$,
$x,y\in\mathbb{F}_{q^{m}}$. We then have:

$P(\alpha x+\beta y)=\alpha P(x)+\beta P(y)$

###### Proof

This comes directly from the fact that the Frobenius endomorphism:
$x\xmapsto{}x^{q}$ is linear over $\mathbb{F}_{q}$

We can see q-polynomials as $\mathbb{F}_{q}$-linear applications from
$\mathbb{F}_{q}^{m}$ to $\mathbb{F}_{q^{m}}$. It is then possible to define a
linear subspace of $\mathbb{F}_{q^{m}}$ from a q-polynomial.

###### Proposition 3

The set of roots of a non-zero q-polynomial of q-degree r forms a linear
subspace of dimension lower than or equal to $r$.

###### Proof

Let $P$ a q-polynomial of degree $r$. One can see $P$ as a linear application
from $\mathbb{F}_{q}^{m}$ to $\mathbb{F}_{q}^{m}$. As an endomorphism kernel,
the set of zeros forms a linear space. Since it is a polynomial of degree
$q^{r}$, $P$ has at most $q^{r}$ roots, giving the upper bound on the subspace
dimension.

######  Proposition 4 ([Ore33])

Let $E$ a linear subspace of $\mathbb{F}_{q^{m}}$ of dimension $r\leq m$. Then
there exists a unique monic q-polynomial of q-degree $r$ such that every
element in $E$ is a root of $P$.
$P$ is called the annihilator polynomial of $E$.

Let us define the usual notions of the rank metric:

###### Definition 14

Let $\bm{E}\in\mathbb{F}_{q}^{m\times n}=\Big{(}e_{i,j}\Big{)}$ with
$e_{i,j}\in\mathbb{F}_{q}$ for $(i,j)\in[1,m]\times[1,n]$, and let
$\mathcal{B}=(b_{1}\dots b_{m})$ an $\mathbb{F}_{q}$-basis of
$\mathbb{F}_{q^{m}}$. It is then possible to associate each column of $\bm{E}$
to an element of $\mathbb{F}_{q^{m}}$ using

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

for each $j\in[1,n]$. By defining $\bm{e}=(e_{1}\dots e_{n})$, we can say that
$\bm{e}$ is the vector associated to the matrix $\bm{E}$.

The _rank weight_ is defined as
$\operatorname{W}_{R}(\bm{e})=\mathsf{Rank}(\bm{E})$. The _distance_ between
two vectors $\bm{x}$ and $\bm{y}$ is then
$d(\bm{x},\bm{y})=\operatorname{W}_{R}(\bm{x}-\bm{y})$. The _support_ of
$\bm{e}=(e_{1}\dots e_{n})$ is the linear subspace of $\mathbb{F}_{q^{m}}$
generated by its coordinates: $\mathsf{Supp}(\bm{e})=\langle e_{1}\dots
e_{n}\rangle$.

###### Remark 1

The choice of the basis $\mathcal{B}$ does not change anything to the weight
of $\bm{e}$ or the rank of $\bm{E}$. The rank of $\bm{E}$ is obviously equal
to the dimension of $\mathsf{Supp}(\bm{e})$. Moreover, in the above
definition, we are working on the columns of $\bm{E}$. We stress that it is
possible to work with the rows instead, as it may be more efficient, depending
on the values of $m$ and $n$. We will also abuse notations, and sometimes note
$\mathsf{Supp}(\bm{e})$ as $\mathsf{Supp}(\bm{E})$.

The number of supports possible of dimension $r$ when working in
$\mathbb{F}_{q^{m}}$ is

$\begin{bmatrix}\textit{m}\\\
\textit{r}\end{bmatrix}_{q}=\prod_{i=0}^{r-1}\frac{q^{m}-q^{i}}{q^{r}-q^{i}}\approx
q^{r(m-r)}.$

###  2.3 MPC-in-the-Head and Proof of Knowledge

The following explanation of the MPCitH paradigm comes from [Fen22, Section
2.1].

The MPC-in-the-Head (MPCitH) paradigm introduced in [IKOS07] offers a way to
build zero-knowledge proofs from secure multi-party computation (MPC)
protocols. Let us assume we have an MPC protocol in which $N$ parties
$\mathcal{{P}}_{1},\ldots,\mathcal{{P}}_{N}$ securely and correctly evaluate a
function $f$ on a secret input $w$ with the following properties:

  * •

the secret witness $w$ is encoded as a sharing $\llbracket w\rrbracket$ and
each $\mathcal{{P}}_{i}$ takes a share $\llbracket w\rrbracket_{i}$ as input;

  * •

the function $f$ outputs Accept or Reject;

  * •

the views of $t$ parties leak no information about the secret $w$, where $t+1$
is the threshold of the secret sharing.

We can use this MPC protocol to build a zero-knowledge proof of knowledge of a
witness $w$ for which $f(w)$ evaluates to Accept. The prover proceeds as
follows:

  * •

she builds a random sharing $\llbracket w\rrbracket$ of $w$;

  * •

she simulates locally (“in her head”) all the parties of the MPC protocol;

  * •

she sends commitments to each party’s view, i.e, party’s input share, secret
random tape and sent and received messages, to the verifier;

  * •

she sends the output shares $\llbracket f(w)\rrbracket$ of the parties, which
should correspond to Accept.

Then the verifier randomly chooses $t$ parties and asks the prover to reveal
their views. After receiving them, the verifier checks that they are
consistent with an honest execution of the MPC protocol and with the
commitments. Since only $t$ parties are opened, revealed views leak no
information about the secret $w$, while the random choice of the opened
parties makes the cheating probability upper bounded by $(N-t)/N$, thus
ensuring the soundness of the zero-knowledge proof.111We implicitly assume
here that the communication between parties is broadcast.

In our case, the parties take as input a linear sharing $\llbracket
w\rrbracket$ of the secret $w$ (one share per party) and they compute one or
several rounds in which they perform three types of actions:

Receiving randomness:

the parties receive a random value $\epsilon$ from a randomness oracle
$\mathcal{O}_{R}$. When calling this oracle, all the parties get the same
random value $\epsilon$.

Receiving hint:

the parties can receive a sharing $\llbracket\beta\rrbracket$ (one share per
party) from a hint oracle $\mathcal{O}_{H}$. The hint $\beta$ can depend on
the witness $w$ and the previous random values sampled from $\mathcal{O}_{R}$.

Computing & broadcasting:

the parties can locally compute
$\llbracket\alpha\rrbracket:=\llbracket\varphi(v)\rrbracket$ from a sharing
$\llbracket v\rrbracket$ where $\varphi$ is an $\mathbb{F}$-linear function,
then broadcast all the shares $\llbracket\alpha\rrbracket_{1}$, …,
$\llbracket\alpha\rrbracket_{N}$ to publicly reconstruct $\alpha:=\varphi(v)$.
The function $\varphi$ can depend on the previous random values
$\\{\epsilon^{i}\\}_{i}$ from $\mathcal{O}_{R}$ and on the previous
broadcasted values. One should note that in the case of additive sharing, only
one party needs to compute the addition by a constant.

We restrain here to threshold linear sharings, i.e, additive secret sharing
and low-threshold linear secret sharing, which is the framework in which
[FR22] and [Fen22] are set.

In [AMGH+22], another way to verify the parties’ computation (in the case of
additive sharing) has been introduced which is more efficient. This is the
hypercube technique, which we will detail here.

The idea of the hypercube construction is the following:

  * •

Generate $N=2^{D}$ parties with an additive sharing. Those parties can be
indexed either by an integer in $[1,N]$ or by a vector in $[1,2]^{D}$. For
example, the $i$-th leaf can be written as the leaf $i$, or as the leaf
$(i_{1},\dots,i_{D})$;

  * •

For each dimension of the hypercube, compute the main shares by summing up the
$2^{D-1}$ shares of a slice of the hypercube. We have $2$ main parties per
dimension, i.e, $2\cdot D$ main parties in total. We can also establish a
mapping between the main parties and the leaves of the hypercube, by writing a
main party $p=(k,j)$ $\in[1,D]\times[1,2]$. Concretely, for a witness $w$, the
share of the main party $p=(k,j)$ can be built (and written) $\llbracket
w\rrbracket_{(k,j)}=\sum_{i:i_{k}=j}\llbracket w\rrbracket_{i}$. These main
shares will be written either as $\llbracket w\rrbracket_{(k,j)}$ or as
$\llbracket w\rrbracket_{(p_{1},p_{2})}$, depending on the indices we use.

  * •

Execute the MPC protocol for all the dimension, i.e, execute $D$ times the MPC
protocol, each time with the $2$ main parties of the dimension.

Since we built the hypercube with an additive sharing, we know that the sum of
all the leaves gives us the secret. This means that we can sum them up in
every way we want (the way in which we sum them depends on the dimension).
This is an improvement compared to the standard MPC in the head, as instead of
simulating one protocol with $256$ parties, we can simulate $8$ MPC protocols,
with only 2 parties each. Furthermore, since the used secret is the same for
every dimension and since the broadcasted plaintext values are the same for
every protocol, it is possible to:

  * •

Execute the MPC protocol for the two parties for one dimension;

  * •

For $D-1$ dimensions:

    * –

Execute the MPC protocol for one party $\mathcal{P}_{1}$;

    * –

Subtract the share broadcasted by $\mathcal{P}_{1}$ to the broadcast plaintext
value;

    * –

Set the resulting share as the broadcasted share of the second party
$\mathcal{P}_{2}$.

Even though this doesn’t reduce the size of the communication cost, this is an
improvement as the computations are faster (we avoid the computation for $D-1$
parties). Moreover, we can observe that taking a hypercube with edge size
larger than $2$ brings no advantage over a power of $2$ (see [AMGH+22]). This
is why $N$ is always a power of $2$ in the case of the hypercube scheme.

###  2.4 The MinRank Problem

######  Definition 15 (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 the following problem:
Let $\bm{M}_{1},\dots,\bm{M}_{k},\bm{E}\in\mathbb{F}_{q}^{m\times n}$ and
$\bm{x}\in\mathbb{F}_{q}^{k}$ be uniformly sampled such that

$\operatorname{W}_{R}(\bm{E})\leq
r~{}~{}~{}\text{with}~{}~{}~{}\bm{M}_{0}:=\bm{E}-\sum_{i=1}^{k}x_{i}\bm{M}_{i}.$

Given $\bm{M}_{0},\dots,\bm{M}_{k}$, retrieve the vector $\bm{x}$.

The MinRank problem was proven to be NP-Complete by [BFS99], and plays a
central role in cryptography. It is used in the attacks on HFE, and appears in
syndrome decoding in rank metric. It was also used in some signatures, such as
Courtois’ signature [Cou01], MR-DSS [BESV22], or MinRank in the Head [ARZV22]
for instance.

####  2.4.1 Key Generation

In practice, to generate a MinRank instance, one has to:

  * •

Sample $\bm{x}$ uniformly in $\mathbb{F}_{q}^{k}$;

  * •

for all $i\in[1,k]$, sample $\bm{M}_{i}\in\mathbb{F}_{q}^{m\times n}$;

  * •

Sample $\bm{E}\in\mathbb{F}_{q}^{m\times n}$ such that
$\operatorname{W}_{R}(\bm{E})\leq r$;

  * •

Define $\bm{M}_{0}$ as $\bm{E}-\sum_{i=1}^{k}\bm{M}_{i}x_{i}$.

From this, we can quickly explicit a $\mathsf{KeyGen}$ algorithm:

Figure 2: Key generation – Simple version

The size of the public key will be $m\cdot n\cdot\log_{2}q+\lambda$ bits
($\bm{M}_{0}$ and the seed used for the random matrices), and the size of the
secret key will be $\lambda$ bits (if we sample $\bm{x}$ from a seed).

However, it is possible to optimize this key generation. First, we need to
define the systematic form of a MinRank problem. Let $\bm{L}_{1}$ be the
$(k+1)\times mn$ matrix, composed of $\bm{M}_{0},\dots,\bm{M}_{k}$ written in
lines, following the row order. Then, if the first $k$ columns and $k$ rows of
$\bm{L}_{1}$ form a full rank matrix, we can obtain a matrix
$\bm{L}=\begin{bmatrix}\begin{matrix}\bm{I}_{k}\\\ 0\dots
0\end{matrix}&\bm{L^{\prime}}_{1}\end{bmatrix}$ where $\bm{I}_{k}$ is the
$k\times k$ identity matrix, using row operations. Row operations on the
matrix $\bm{L}_{1}$ correspond to a linear combination of
$\bm{M}_{0},\dots,\bm{M}_{k}$, meaning they don’t change the number of
solutions of the instance.

For a generic MinRank instance (i.e, with high probability, as noted in
[BESV22] and used in [BBB+22]), this transformation will be possible. This
means we can generate the instance directly in this systematic form, without
changing the difficulty of the problem. To proceed, we will use the procedure
described in [BESV22]:

  * •

Sample $\bm{L}\in\mathbb{F}_{q}^{k\times mn}$ uniformly such that
$\bm{L}=\begin{bmatrix}\bm{I}_{k}&\bigg{|}L^{\prime}\end{bmatrix}$ where
$\bm{I}_{k}$ is the $k\times k$ identity matrix and $\bm{L^{\prime}}$ is an
$k\times(mn-k)$ matrix;

  * •

Set $\bm{M}_{i}$ as the i-th line of $\bm{L}$, written in a matrix form (in
row order, i.e, the first row of the matrix is the first $n$ entries of the
lines, the second row is the next $n$ entries and so on);

  * •

Sample $\bm{E}\overset{\;\$}{\longleftarrow}\mathbb{F}_{q}^{m\times n}$
uniformly such that $\operatorname{W}_{R}(\bm{E})\leq r$ and
$\bm{\beta}\overset{\;\$}{\longleftarrow}\mathbb{F}_{q}^{k}$;

  * •

Compute $\bm{F}=\bm{E}-\sum_{i=1}^{k}\beta_{i}\bm{M}_{i}$;

  * •

Compute $\bm{M}_{0}=\bm{F}-\sum_{i=1}^{k}f_{i}\bm{M}_{i}$ where
$\bm{f}=(f_{1}\dots f_{k})$ are the first $k$ entries, in row order, of
$\bm{F}$;

  * •

Set $\bm{x}=\bm{\beta}+\bm{f}$.

It is clear that we have $\bm{M}_{0}=\bm{E}-\sum_{i=1}^{k}x_{i}\bm{M}_{i}$ and
that the first $k$ entries of $\bm{M}_{0}$ are zeros. Since $\bm{L}$ comes
from a random seed, our secret key $\bm{x}$ can be retrieved from the used
seed, and is thus of size $\lambda$ bits. For our public key, we have
$\bm{M}_{1},\dots,\bm{M}_{k}$ of size $\lambda$ bits, plus $\bm{M}_{0}$, of
size $(mn-k)\cdot\log_{2}q$ bits.

Figure 3: Key generation – Optimized version

###  2.5 Rank Checking MPC protocol

It is necessary to build a protocol allowing us to verify that the space
generated by a list of $n\geq r$ elements is at most $r$. We will build here a
MPCitH ZK-proof based on Feneuil’s protocol using q-polynomials [Fen22], that
we will remind here. We want to check that a list of elements
$(e_{j})_{j\in[1,n]}$, where $e_{j}\in\mathbb{F}_{q^{m}}$, leads to a
$\mathbb{F}_{q}$-linear subspace $U$ of dimension at most $r$.

Given $U$, let $L_{U}$ be the polynomial:

$L_{U}=\prod_{u\in U}(X-u)\in\mathbb{F}_{q^{m}}[X].$

It is possible to show that all the $e_{j}$ are roots of $L_{U}$, which is a
q-polynomial. It means that $L_{U}$ is of the form:

$L_{U}(X)=\sum_{i=0}^{r-1}\beta_{i}X^{q^{i}}+X^{q^{r}}$

Rather than checking separately that each $e_{j}$ is a root of $L_{U}$, we
will batch all these verifications by uniformly sampling
$\gamma_{1},...,\gamma_{n}$ in an extension $\mathbb{F}_{q^{m\eta}}$ of
$\mathbb{F}_{q^{m}}$ and check that:

$\sum_{j=1}^{n}\gamma_{j}L_{U}(e_{j})=0$

If one or more of the $e_{j}$ is not a root of $L_{U}$, the above equation is
satisfied with probability at most $\frac{1}{q^{m\eta}}$. Then,

$\displaystyle\sum_{j=1}^{n}\gamma_{j}L_{U}(e_{j})$
$\displaystyle=\sum_{j=1}^{n}\gamma_{j}\left(\sum_{i=0}^{r-1}\beta_{i}e_{j}^{q^{i}}+e_{j}^{q^{r}}\right)$
$\displaystyle=\sum_{j=1}^{n}\gamma_{j}e_{j}^{q^{r}}+\sum_{i=0}^{r-1}\beta_{i}\sum_{j=1}^{n}\gamma_{j}e_{j}^{q^{i}}$

Defining $z=-\sum_{j=1}^{n}\gamma_{j}e_{j}^{q^{r}}$ and
$w_{i}=\sum_{j=1}^{n}\gamma_{j}e_{j}^{q^{i}}$, proving the equation is
equivalent to prove that

$z=\langle\bm{\beta},\bm{w}\rangle.$

The latter equation will be checked thanks to the multiplication protocol from
[BN20] (adapted in the matrix setting, see [Fen22]). In the case of MinRank,
we want to apply this protocol to $\bm{E}$, which we will have to compute. In
what follows, we work on the columns of $\bm{E}$ and in $\mathbb{F}_{q^{m}}$.
Depending on the parameters, it might also be easier to work on the rows of
$\bm{E}$. This gives us the following protocol from [Fen22]:

Figure 4: Protocol $\Pi^{\eta}$ to check that an input is solution of an
instance of MinRank

One should stress that we can locally compute shares to the power $q^{i}$.
Since we are in $\mathbb{F}_{q}$, this operation is linear, and thus this
operation is basically “free” in multiparty computation.

######  Proposition 5 ([Fen22])

If $\operatorname{W}_{R}\>(\bm{E})\leq r$, then the protocol $\Pi^{\eta}$
always accepts. If $\operatorname{W}_{R}\>(\bm{E})>r$, the protocol accepts
with probability at most:
$p_{\Pi,\eta}=\frac{2}{q^{m\eta}}-\frac{1}{q^{2m\eta}}$ (we call
$p_{\Pi,\eta}$ the false positive rate of $\Pi^{\eta}$).

###### Proof

The proof is the same as the one in [Fen22, Section 5.1]

Thanks to this MPC protocol, we can build a zero-knowledge proof of knowledge
protocol, using either additive secret sharing (Fig.5) or threshold secret
sharing (Fig.10).

##  3 Description of the Protocols

###  3.1 Description of MIRA-Additive

####  3.1.1 Proof of Knowledge with Additive Secret Sharing Scheme

We describe here the idea of the hypercube technique introduced by [AMGH+22].

  * •

The prover generates $N=2^{D}$ shares of the inputs of the $\Pi^{\eta}$
protocol (Fig.4), using an additive secret sharing scheme;

  * •

He then computes the shares associated to the “main parties”, i.e, the parties
associated to each dimension, by summing up the $2^{D-1}$ shares that have the
same index on the dimension (in the same way as explained in section 2.3);

  * •

There are $D$ dimensions, each of them having $2$ main parties. The prover
sends the commitments of all the $N$ shares;

  * •

He then receives the first challenge, which is some random values for the
computation of the $\Pi^{\eta}$ protocol;

  * •

Then, for $D+1$ main parties, he executes the protocol $\Pi^{\eta}$. For the
$D-1$ other parties, he will use the broadcasted values of $\bm{\alpha}$ and
$v$ in order to compute their shares of $\bm{\alpha}$ and of $v$. He will hash
these values;

  * •

He sends to the verifier the hash of these values (it is possible to hash them
twice, as is done in the description of Fig.6, or not);

  * •

He receives the second challenge, which is a single leaf, $i^{*}$;

  * •

He reveals every commitment except the $i^{*}$th one, and sends the share
$\llbracket\bm{\alpha}\rrbracket_{i^{*}}$ broadcast by the party $i^{*}$;

  * •

The verifier can then reconstruct the broadcast shares of the main parties,
i.e the $2$ shares for each dimension, and then check that everything is
correct. Similarly to the prover, he can avoid the computation of the protocol
for $D-1$ parties.

One detail to notice is that in Fig.6, we use an hash function to output the
broadcast shares. We stress that this hash function is not mandatory. The
security of the protocol with or without it is the same. Depending on the
implementation, using it can be more convenient (for example, to save memory
when the used implementation of the hash functions is not incremental). In our
security proofs, we will consider that such hash function is used.

Finally, if $i^{*}\neq N$, the prover has to send
$\llbracket\bm{x}\rrbracket_{N},\llbracket\bm{\beta}\rrbracket_{N},\llbracket
c\rrbracket_{N}$ in addition to the sibling path. This comes from the fact
that these shares are not completely random.

This gives us the protocol provided in Fig.5. We insist on the fact that, as
mentioned in section 2.3, a prover doesn’t need to simulate $2D$ parties in
step 10, but only $D+1$, as the values of $\bm{\alpha}$ and $v$ are the same,
no matter the dimension. In fact, for $D-1$ dimensions in step 10, it is
possible to retrieve $\llbracket\bm{\alpha}\rrbracket_{(k,2)}$ by computing
$\bm{\alpha}-\llbracket\bm{\alpha}\rrbracket_{(k,1)}$ instead of simulating
the MPC protocol. We emphasize on this optimisation, as this is a crucial
advantage of the hypercube structure.

\- Public data $\bm{M}_{0},\dots,\bm{M}_{k}\in\mathbb{F}_{q}^{m\times n}$
$\displaystyle\@pc@lb$ The prover wants to convince the verifier that he knows
a solution $\bm{x}\in\mathbb{F}_{q}^{k}$ of the MinRank instance, i.e such as
$\bm{E}=\bm{M}_{0}+\sum_{i=1}^{k}(\bm{M}_{i}x_{i})$ and
$\operatorname{W}_{R}(\bm{E})\leq r$ $\displaystyle\@pc@lb[]$ Step 1:
Commitment $\displaystyle\@pc@lb$ 1\. The prover sets $U=\langle e_{1}\dots
e_{n}\rangle$, and computes $L(X)=\prod_{u\in
U}(X-u)=X^{q^{r}}+\sum_{i=0}^{r-1}\beta_{i}\cdot X^{q^{i}}$ for some
$\beta_{i}\in\mathbb{F}_{q^{m}}^{r}$ $\displaystyle\@pc@lb$ 2\. The prover
samples a root seed:
$\mathsf{seed}\overset{\;\$}{\longleftarrow}\\{0,1\\}^{\lambda}$
$\displaystyle\@pc@lb$ 3\. The prover expands the root seed recursively using
TreePRG to obtain $N$ leaves, from which he derives $N$ seeds and $N$
commitment random tapes $(\mathsf{seed}_{i^{\prime}},\rho_{i^{\prime}})$
$\displaystyle\@pc@lb$ 4\. For each $i\in[1,N-1]$: $\displaystyle\@pc@lb$ \-
Sample
$(\llbracket\bm{x}\rrbracket_{i},\llbracket\bm{\beta}\rrbracket_{i},\llbracket\bm{a}\rrbracket_{i}\llbracket
c\rrbracket_{i})\overset{\;\$,\mathsf{seed}_{i}}{\longleftarrow}PRG$ where PRG
is a pseudo-random generator $\displaystyle\@pc@lb$ \-
${\mathsf{\vphantom{p}state}}_{i}=\mathsf{seed}_{i}$ $\displaystyle\@pc@lb$
5\. For the share $N$: $\displaystyle\@pc@lb$ \- Sample
$\llbracket\bm{a}\rrbracket_{N}\overset{\;\$,\mathsf{seed}_{N}}{\longleftarrow}PRG$
$\displaystyle\@pc@lb$ \- Compute
$\llbracket\bm{x}\rrbracket_{N}=\bm{x}-\sum_{i=1}^{N-1}\llbracket\bm{x}\rrbracket_{i}$,
$\llbracket\bm{\beta}\rrbracket_{N}=\bm{\beta}-\sum_{i=1}^{N-1}\llbracket\bm{\beta}\rrbracket_{i}$
and $\llbracket
c\rrbracket_{N}=-\langle\bm{a},\bm{\beta}\rangle-\sum_{i=1}^{N-1}\llbracket
c\rrbracket_{i}$ $\displaystyle\@pc@lb$ \-
${\mathsf{\vphantom{p}state}}_{N}=(\mathsf{seed}_{N},\llbracket\bm{x}\rrbracket_{N},\llbracket\bm{\beta}\rrbracket_{N},\llbracket
c\rrbracket_{N})$ $\displaystyle\@pc@lb$ 6\. The prover computes the
commitments:
$\mathsf{cmt}_{i}=\mathsf{Com}\big{(}{\mathsf{\vphantom{p}state}}_{i},\rho_{i}\big{)}$,
for each $i\in[1,N]$. $\displaystyle\@pc@lb$ 7\. The prover computes and sends
$h_{0}=\mathsf{H}(\mathsf{cmt}_{1},\cdots,\mathsf{cmt}_{N})$ to the verifier.
$\displaystyle\@pc@lb$ 8\. The prover computes the input shares of the main
parties by summing all the associated leaves. We index each party by its
coordinates on the hypercube: $i=(i_{1},...,i_{D})$ where $i_{k}\in[1,2]$. For
all main party index $p\in\\{(1,1),...,(D,2)\\}$:
$\llbracket\bm{x}\rrbracket_{(p_{1},p_{2})}=\sum_{i:i_{p_{1}}=p_{2}}\llbracket\bm{x}\rrbracket_{i}$,
$\llbracket\bm{\beta}\rrbracket_{(p_{1},p_{2})}=\sum_{i:i_{p_{1}}=p_{2}}\llbracket\bm{\beta}\rrbracket_{i}$,
$\llbracket\bm{a}\rrbracket_{(p_{1},p_{2})}=\sum_{i:i_{p_{1}}=p_{2}}\llbracket\bm{a}\rrbracket_{i}$
and $\llbracket c\rrbracket_{(p_{1},p_{2})}=\sum_{i:i_{p_{1}}=p_{2}}\llbracket
c\rrbracket_{i}$. $\displaystyle\@pc@lb[]$ Step 2: First Challenge
$\displaystyle\@pc@lb$ 9\. The verifier sends
$\big{(}(\gamma_{j})_{j\in[1,n]},\epsilon\big{)}\in\mathbb{F}_{q^{m\cdot\eta}}^{n}\times\mathbb{F}_{q^{m\cdot\eta}}$
to the prover. $\displaystyle\@pc@lb[]$ Step 3: First Response
$\displaystyle\@pc@lb$ 10\. For each dimension $k\in[1,D]$, the prover
executes the algorithm in Fig. 6 on the set of the main parties of the
dimension. This set is denoted $P_{k}$. He computes
$\big{(}(\llbracket\bm{\alpha}\rrbracket_{(k,i)},\llbracket
v\rrbracket_{(k,i)})_{i\in[1,2]},H_{k}\big{)}\longleftarrow\text{Algorithm
Fig.\ref{exec_pi_hypercube}}(\big{(}P_{k},(\gamma_{j})_{j\in[1,n]},\epsilon\big{)}$.
He only needs to execute the algorithm $D+1$ times, as explained above.
$\displaystyle\@pc@lb$ 11\. The prover commits the executions:
$h_{1}=\mathsf{H}(H_{1},...,H_{D})$. $\displaystyle\@pc@lb[]$ Step 4: Second
Challenge $\displaystyle\@pc@lb$ 12\. The verifier gets a random leaf
$i^{*}\in[1,N]$ and sends it to the prover. $\displaystyle\@pc@lb[]$ Step 5:
Second Response and Verification $\displaystyle\@pc@lb$ 13\. The prover sends
to the verifier:
$\left(\mathsf{cmt}_{i^{*}},\llbracket\bm{\alpha}\rrbracket_{i^{*}},({\mathsf{\vphantom{p}state}}_{j},\rho_{j})_{j\neq
i^{*}}\right)$, where $({\mathsf{\vphantom{p}state}}_{j},\rho_{j})_{j\neq
i^{*}}$ corresponds to the sibling path to this commitment. If $i^{*}\neq N$,
he also has to send
$\llbracket\bm{x}\rrbracket_{N},\llbracket\bm{\beta}\rrbracket_{N}$ and
$\llbracket c\rrbracket_{N}$. $\displaystyle\@pc@lb$ 14\. The verifier can
deduce all the leaves (with the exception of index $i^{*}$), and recover
$h_{0}$ using the sibling path and $\mathsf{cmt}_{i^{*}}$.
$\displaystyle\@pc@lb$ 15\. For all dimension $k\in[1,D]$, the verifier runs
the algorithm in Fig. 7 to get
$(\llbracket\bm{\alpha}\rrbracket_{(k,i)},\llbracket
v\rrbracket_{(k,i)})_{i\in[1,2]}$ and $H_{k}$. Then he checks that
$\displaystyle\@pc@lb$ \- $v=0$ for all dimensions. $\displaystyle\@pc@lb$ \-
$\bm{\alpha}$ is the same for all dimensions. $\displaystyle\@pc@lb$

Figure 5: MinRank Proof of Knowledge with additive-sharing MPCitH

Inputs: A set of main shares for the dimension $k$:
$\big{(}(\llbracket\bm{x}\rrbracket_{(k,i)},\llbracket\bm{\beta}\rrbracket_{(k,i)},\llbracket\bm{a}\rrbracket_{(k,i)},\llbracket
c\rrbracket_{(k,i)})\big{)}_{i\in[1,2]}$ and a protocol challenge
$\big{(}(\gamma_{j})_{j\in[1,n]},\epsilon\big{)}$ $\displaystyle\@pc@lb$
Outputs: A set of main shares $\big{(}\bm{\alpha}_{(k,i)},\llbracket
v\rrbracket_{(k,i)}\big{)}_{i\in[1,2]}$ and a commitment $H_{k}$ of the
execution $\displaystyle\@pc@lb[]$ For each main party $i\in\\{1,2\\}$:
$\displaystyle\@pc@lb$ \- Compute
$\llbracket\bm{E}\rrbracket_{(k,i)}=\bm{M}_{0}+\sum_{j=1}^{k}[\\![x_{j}]\\!]_{(k,i)}\bm{M}_{j}$
$\displaystyle\@pc@lb$ \- Set $[\\![e_{j}]\\!]_{(k,i)}$ as the element in
$\mathbb{F}_{q^{m}}$ associated to the j-th column of
$[\\![\bm{E}]\\!]_{(k,i)}$ $\displaystyle\@pc@lb$ \- Compute
$[\\![z]\\!]_{(k,i)}=-\sum_{j=1}^{n}\gamma_{j}\cdot[\\![e_{j}]\\!]_{(k,i)}^{q^{r}}$
$\displaystyle\@pc@lb$ For $l$ from $0$ to $r-1$: $\displaystyle\@pc@lb$
$\diamond$ Compute
$[\\![w_{l}]\\!]_{(k,i)}=\sum_{j=1}^{n}\gamma_{j}\cdot[\\![e_{j}]\\!]_{(k,i)}^{q^{l}}$
$\displaystyle\@pc@lb$ \- Compute
$[\\![\bm{\alpha}]\\!]_{(k,i)}=\epsilon\cdot[\\![\bm{w}]\\!]_{(k,i)}+[\\![\bm{a}]\\!]_{(k,i)}$
and reveal $\bm{\alpha}$ $\displaystyle\@pc@lb$ \- Compute
$[\\![v]\\!]_{(k,i)}=\epsilon\cdot[\\![z]\\!]_{(k,i)}-\langle\bm{\alpha},[\\![\bm{\beta}]\\!]_{(k,i)}\rangle-[\\![c]\\!]_{(k,i)}$
$\displaystyle\@pc@lb$

Figure 6: Execution of the MPC protocol $\Pi^{\eta}$ on a set of main shares

Inputs: A leaf $i^{*}$ that one does not reveal. $\tilde{i}$ is the index
depending on the leaf $i^{*}$. The share
$\llbracket\bm{\alpha}\rrbracket_{i^{*}}$, and all the main parties shares
$\big{(}(\llbracket\bm{x}\rrbracket_{(k,i)},\llbracket\bm{\beta}\rrbracket_{(k,i)},\llbracket\bm{a}\rrbracket_{(k,i)},\llbracket
c\rrbracket_{(k,i)})\big{)}_{i\in[1,2]}$. For $i=\tilde{i}$, the main shares
correspond to the usual main party shares, except the share $i^{*}$ is
missing. $\displaystyle\@pc@lb$ Outputs:
$(\llbracket\bm{\alpha}\rrbracket_{(k,i)},\llbracket
v\rrbracket_{(k,i)})_{i\in[1,2]}$ and a commitment $H_{k}$ of the execution
$\displaystyle\@pc@lb[]$ For $i\in[1,2]$: $\displaystyle\@pc@lb$ If
$i=\tilde{i}$: $\displaystyle\@pc@lb$ Set $\llbracket v\rrbracket_{i^{*}}$
such that $v=0$ and compute $\llbracket v\rrbracket_{(k,\tilde{i})}$
$\displaystyle\@pc@lb$ Compute
$\llbracket\bm{\alpha}\rrbracket_{(k,\tilde{i})}=\sum_{j:j_{k}=\tilde{i},j\neq
i^{*}}\llbracket\bm{\alpha}\rrbracket_{j}+\llbracket\bm{\alpha}\rrbracket_{i^{*}}$
where $\sum_{j:j_{k}=\tilde{i},j\neq
i^{*}}\llbracket\bm{\alpha}\rrbracket_{j}$ is obtained by applying
$\Pi^{\eta}$ to the partially-aggregated input shares. $\displaystyle\@pc@lb$
Else: $\displaystyle\@pc@lb$ Do the same computations as in $\Pi^{\eta}$ to
obtain the correct shares $\llbracket\bm{\alpha}\rrbracket_{(k,i)}$ and
$\llbracket v\rrbracket_{(k,i)}$ $\displaystyle\@pc@lb$

Figure 7: Check the executions of the MPC protocol $\Pi^{\eta}$ on the main
parties

We prove that our scheme satisfies the necessary security properties in the
proof of theorem 5.1 in section 5.1.

####  3.1.2 MIRA-Additive

From the zero-knowledge protocol, we can simply deduce a signature scheme,
using the Fiat-Shamir transform. The protocol is now non-interactive, and we
deterministically sample the challenge thanks to a hash function. We must
repeat the zero-knowledge protocol several times, in order to reach a certain
level of security. Note that we use a value $\mathsf{salt}$, as in [FJR22], in
order to increase the security of the scheme as it reduces the probability to
have seeds collisions. Moreover, simarly than in the proof of knowledge, the
hash function $\mathsf{H}_{3}$ is not mandatory and depends only of
implementation choices. The signature protocol obtained is described in Fig.8
and Fig.9. As aforementioned in the proof of knowledge, the signature process
avoid the computation of the MPC protocol for $D-1$ parties in step 8. The
verification process avoids it in step 6 as well.

Inputs $\displaystyle\@pc@lb$ \- Secret key
$\mathsf{\vphantom{p}sk}=(\bm{x})\in\mathbb{F}_{q}^{k}$,
$(\bm{E})\in\mathbb{F}_{q}^{m\times n}$ such that
$\operatorname{W}_{R}(\bm{E})\leq r$ $\displaystyle\@pc@lb$ \- Public data
$\bm{M}_{0},\dots,\bm{M}_{k}\in\mathbb{F}_{q}^{m\times n}$ with
$\bm{E}=\bm{M}_{0}+\sum_{i=1}^{k}\bm{M}_{i}x_{i}$ $\displaystyle\@pc@lb$ \-
Message $m\in\\{0,1\\}^{*}$ $\displaystyle\@pc@lb[]$ Step 1: Commitment
$\displaystyle\@pc@lb$ 1\. Sample a random salt value
$\mathsf{salt}\overset{\;\$}{\longleftarrow}\\{0,1\\}^{2\lambda}$
$\displaystyle\@pc@lb$ 2\. Set $U=\langle e_{1},\dots,e_{n}\rangle$ and
compute $\bm{\beta}=(\beta_{k})_{k\in[0,r-1]}\in\mathbb{F}_{q^{m}}^{r}$ the
coefficients of the annihilator q-polynomial $L(X)$ associated to $\bm{{E}}$
such that $L(X)=\prod_{u\in U}(X-u)=X^{q^{r}}+\sum_{k=0}^{r-1}\beta_{k}\cdot
X^{q^{k}}$ and $\forall j\in[1,n],L({{e}}_{j})=0$ where each $e_{j}$ is the
element in $\mathbb{F}_{q^{m}}$ associated to the j-th column of $\bm{E}$
$\displaystyle\@pc@lb$ 3\. For each iteration $e\in[1,\tau]$:
$\displaystyle\@pc@lb$ \- Sample a root seed:
$\mathsf{seed}^{(e)}\leftarrow\\{0,1\\}^{\lambda}$ $\displaystyle\@pc@lb$ \-
Expand root seed recursively with TreePRG to obtain $N$ seeds and randomness
$(\mathsf{seed}^{(e)}_{i^{\prime}},\rho_{i^{\prime}})$ $\displaystyle\@pc@lb$
For each $i\in[1,N]$: $\displaystyle\@pc@lb$ If $i\neq N$:
$\displaystyle\@pc@lb$ $\diamond$ Sample
$(\llbracket\bm{x}\rrbracket^{(e)}_{i},\llbracket\bm{\beta}\rrbracket^{(e)}_{i},\llbracket\bm{a}\rrbracket^{(e)}_{i}\llbracket
c\rrbracket^{(e)}_{i})\overset{\;\$,\mathsf{seed}_{i}^{(e)}}{\longleftarrow}PRG$
where PRG is a pseudo-random generator $\displaystyle\@pc@lb$ $\diamond$
${\mathsf{\vphantom{p}state}}^{(e)}_{i}=\mathsf{seed}^{(e)}_{i}$
$\displaystyle\@pc@lb$ Else: $\displaystyle\@pc@lb$ $\diamond$ Sample
$\llbracket\bm{a}\rrbracket^{(e)}_{N}\overset{\;\$,\mathsf{seed}^{(e)}_{N}}{\longleftarrow}PRG$
$\displaystyle\@pc@lb$ $\diamond$ Compute
$\llbracket\bm{x}\rrbracket^{(e)}_{N}=\bm{x}-\sum_{i=1}^{N-1}\llbracket\bm{x}\rrbracket^{(e)}_{i}$,
$\llbracket\bm{\beta}\rrbracket^{(e)}_{N}=\bm{\beta}-\sum_{i=1}^{N-1}\llbracket\bm{\beta}\rrbracket^{(e)}_{i}$
and $\llbracket
c\rrbracket^{(e)}_{N}=-\langle\bm{a},\bm{\beta}\rangle-\sum_{i=1}^{N-1}\llbracket
c\rrbracket^{(e)}_{i}$ $\displaystyle\@pc@lb$ $\diamond$
${\mathsf{\vphantom{p}state}}_{N}^{(e)}=(\mathsf{seed}_{N}^{(e)},\llbracket\bm{x}\rrbracket^{(e)}_{N},\llbracket\bm{\beta}\rrbracket^{(e)}_{N},\llbracket
c\rrbracket^{(e)}_{N})$ $\displaystyle\@pc@lb$ \- Compute
$\mathsf{cmt}_{i}^{(e)}=\mathsf{H}_{0}(\mathsf{salt},e,i,{\mathsf{\vphantom{p}state}}_{i}^{(e)})$
$\displaystyle\@pc@lb$ 4\. For all main party index
$p=(p_{1},p_{2})\in\\{(1,1),...(D,2)\\}$:
$\llbracket\bm{x}\rrbracket_{(p_{1},p_{2})}=\sum_{i:i_{p_{1}}=p_{2}}\llbracket\bm{x}\rrbracket_{i}$,
$\llbracket\bm{\beta}\rrbracket_{(p_{1},p_{2})}=\sum_{i:i_{p_{1}}=p_{2}}\llbracket\bm{\beta}\rrbracket_{i}$,
$\llbracket\bm{a}\rrbracket_{(p_{1},p_{2})}=\sum_{i:i_{p_{1}}=p_{2}}\llbracket\bm{a}\rrbracket_{i}$
and $\llbracket c\rrbracket_{(p_{1},p_{2})}=\sum_{i:i_{p_{1}}=p_{2}}\llbracket
c\rrbracket_{i}$. $\displaystyle\@pc@lb$ 5\. Compute and commit
$h_{0}^{(e)}=\mathsf{H}_{1}(\mathsf{salt},e,\mathsf{cmt}_{1}^{(e)},...,\mathsf{cmt}_{N}^{(e)})$
$\displaystyle\@pc@lb$ 6\. Compute
$h_{1}=\mathsf{H}_{2}\left(\mathsf{salt},m,h_{0}^{(1)},...,h_{0}^{(\tau)}\right)$
$\displaystyle\@pc@lb[]$ Step 2: First Challenge $\displaystyle\@pc@lb$ 7\.
Sample
$\big{(}(\gamma^{(e)}_{j})_{j\in[1,n]},\epsilon^{(e)}\big{)}_{e\in[1,\tau]}\overset{\;\$}{\longleftarrow}PRG(h_{1})$
where
$\big{(}(\gamma^{(e)}_{j})_{j\in[1,n]},\epsilon^{(e)}\big{)}_{e\in[1,\tau]}\in(\mathbb{F}_{q^{m\cdot\eta}}^{n}\times\mathbb{F}_{q^{m\cdot\eta}})^{\tau}$
$\displaystyle\@pc@lb[]$ Step 3: First Response $\displaystyle\@pc@lb$ 8\. For
each iteration $e\in[1,\tau]$: $\displaystyle\@pc@lb$ For each each dimension
$k\in[1,D]$: $\displaystyle\@pc@lb$ \- Execute the algorithm in Fig.6 to
obtain $\big{(}\llbracket\bm{\alpha}^{(e)}\rrbracket_{(k,i)},\llbracket
v^{(e)}\rrbracket_{(k,i)}\big{)}_{i\in[1,2]}$ and $H_{k}^{(e)}$, with the hash
function $\mathsf{H}_{3}$ $\displaystyle\@pc@lb$ 9\. Compute
$h_{2}=\mathsf{H}_{4}(m,\mathsf{\vphantom{p}pk},\mathsf{salt},h_{1},(H_{1}^{(e)}\dots
H_{D}^{(e)})_{e\in[1,\tau]})$ $\displaystyle\@pc@lb[]$ Step 4: Second
Challenge $\displaystyle\@pc@lb$ 10\. Sample
$i^{*(e)}\overset{\;\$}{\longleftarrow}PRG(h_{2})$ where
$i^{*(e)}\in[1,N]^{\tau}$ $\displaystyle\@pc@lb[]$ Step 5: Second Response
$\displaystyle\@pc@lb$ 11.For each iteration $e\in[1,\tau]$:
$\displaystyle\@pc@lb$ \- Compute
$\mathsf{rsp}^{(e)}=\left(({\mathsf{\vphantom{p}state}}_{j})^{(e)}_{j\neq
i^{*}},\mathsf{cmt}_{i^{*(e)}},\llbracket\bm{\alpha}^{(e)}\rrbracket_{i^{*(e)}}\right)$
where $({\mathsf{\vphantom{p}state}}_{j})^{(e)}_{j\neq i^{*}}$ corresponds to
the sibling path. If $i^{*}\neq N$, he also has to send
$\llbracket\bm{x}\rrbracket_{N},\llbracket\bm{\beta}\rrbracket_{N}$ and
$\llbracket c\rrbracket_{N}$. $\displaystyle\@pc@lb$

Figure 8: MIRA Signature Scheme based on additive sharing MPCitH - Signature
Algorithm

Inputs $\displaystyle\@pc@lb$ \- Public data
$\bm{M}_{0},\dots,\bm{M}_{k}\in\mathbb{F}_{q}^{m\times n}$ such that there is
$\bm{x}\in\mathbb{F}_{q}^{k}$ such that
$\bm{E}=\bm{M}_{0}+\sum_{i=1}^{k}(\bm{M}_{i}x_{i})$ and
$\operatorname{W}_{R}(\bm{E})\leq r$ $\displaystyle\@pc@lb$ \- Message
$m\in\\{0,1\\}^{*}$ $\displaystyle\@pc@lb$ \- Signature
$\sigma=(\mathsf{salt},h_{1},h_{2},(\bar{\mathsf{rsp}}^{(e)})_{e\in[1,\tau]})$
$\displaystyle\@pc@lb[]$ Step 1: Parse signature $\displaystyle\@pc@lb$ 1\.
Sample
$\big{(}(\gamma^{(e)}_{j})_{j\in[1,n]},\epsilon^{(e)}\big{)}_{e\in[1,\tau]}\overset{\;\$}{\longleftarrow}PRG(h_{1})$
where
$\big{(}(\gamma^{(e)}_{j})_{j\in[1,n]},\epsilon^{(e)}\big{)}_{e\in[1,\tau]}\in(\mathbb{F}_{q^{m\cdot\eta}}^{n}\times\mathbb{F}_{q^{m\cdot\eta}})^{\tau}$
$\displaystyle\@pc@lb$ 2\. Sample
$i^{*(e)}\overset{\;\$}{\longleftarrow}PRG(h_{2})$ where $i^{*(e)}\in[1,N]$
$\displaystyle\@pc@lb$ 3\. Parse
$\left(({\mathsf{\vphantom{p}state}}_{j})^{(e)}_{j\neq
i^{*}},\mathsf{cmt}_{i^{*(e)}},\llbracket\bm{\alpha}^{(e)}\rrbracket_{i^{*(e)}}\right)\leftarrow\mathsf{rsp}^{(e)}$
$\displaystyle\@pc@lb[]$ Step 2: Recompute $h_{1}$ $\displaystyle\@pc@lb$ 4\.
For each iteration $e\in[1,\tau]$: $\displaystyle\@pc@lb$ \- For each $i\neq
i^{*(e)}$: $\displaystyle\@pc@lb$ $\diamond$
$\mathsf{cmt}_{i}^{(e)}=\mathsf{H}_{0}(\mathsf{salt},e,i,{\mathsf{\vphantom{p}state}}_{i}^{(e)})$
$\displaystyle\@pc@lb$ \- Compute
$h_{0}^{(e)}=\mathsf{H}_{1}\left(\mathsf{salt},e,\mathsf{cmt}_{1}^{(e)},...,\mathsf{cmt}_{N}^{(e)}\right)$
$\displaystyle\@pc@lb$ 5\. Compute
$\bar{h}_{1}=\mathsf{H}_{2}\left(\mathsf{salt},m,h_{0}^{(1)},...,h_{0}^{(\tau)}\right)$
$\displaystyle\@pc@lb[]$ Step 3: Recompute $h_{2}$ $\displaystyle\@pc@lb$ 6\.
For each iteration $e\in[1,\tau]$: $\displaystyle\@pc@lb$ \- Simulate MPC
protocol $\Pi^{\eta}$ on main parties. $\displaystyle\@pc@lb$ \- For each
dimension $k\in[1,D]$: $\displaystyle\@pc@lb$ $\diamond$ Run the algorithm in
Fig. 7 to get $\bar{H_{k}^{(e)}}$, in which
$\llbracket\bm{\alpha}^{(e)}\rrbracket_{i^{*(e)}}$ is used to compute the
share of $\bm{\alpha}$ of the main party relying on $i^{*}$.
$\displaystyle\@pc@lb$ 7\. Compute
$\bar{h}_{2}=\mathsf{H}_{4}\left(m,\mathsf{\vphantom{p}pk},\mathsf{salt},\bar{h}_{1},\left(\bar{H_{1}^{(e)}},...,\bar{H_{D}^{(e)}}\right)_{e\in[1,\tau]}\right)$
$\displaystyle\@pc@lb[]$ Step 4: Verify signature $\displaystyle\@pc@lb$ 8\.
Return $(\bar{h}_{1}=h_{1})\wedge(\bar{h}_{2}=h_{2})$ $\displaystyle\@pc@lb$

Figure 9: MIRA Signature Scheme based on additive MPCitH - Verification
Algorithm

We prove that the scheme is EUF-CMA secure in the proof of theorem 5.3 in
section 5.2.

###  3.2 Description of MIRA-Threshold

####  3.2.1 Proof of Knowledge with Threshold Secret Sharing

Once we have this zero-knowledge protocol (and signature scheme) with additive
sharing, one may wonder if it is possible to use other secret sharing schemes
to build MPCitH-based signature schemes. The answer is positive and given in
[FR22]: we can use any threshold linear secret sharing scheme. (Ligero
[AHIV17] already considered Shamir’s secret sharing but this scheme is only
interesting for “medium-size circuits”, which is not the case of circuits
involved to build signature schemes.) When dealing with threshold secret
sharing, we will consider (except when told otherwise) that we are referring
to Shamir’s secret sharing scheme. As reminded earlier (see Definition 8), in
order to build a sharing of a secret in this setting, one has to build the
random polynomial with the secret as the constant term, and then evaluate this
polynomial in the evaluation points. Since most of our secrets in our case are
vectors, this has to be done for every coordinates, and so the notation can be
pretty heavy. For the sake of simplicity, this process is not made explicit in
the description of our protocols.

The protocol with threshold secret sharing works in the following way:

  * •

Using a $(\ell+1,N)$-threshold secret sharing scheme, the prover computes the
shares of the inputs of the protocol $\Pi^{\eta}$, computes the commitments,
and then computes the Merkle tree root of the commitments;

  * •

He then receives the first challenge, i.e, the randomness for the protocol
$\Pi^{\eta}$;

  * •

He then chooses a set $S$ of $\ell+1$ parties, for which he executes the
protocol $\Pi^{\eta}$, and computes the hash value of the executions;

  * •

He then receives the second challenge. This challenge is a set $I$ of $\ell$
parties (instead of just $1$ as in the additive protocol). For these $\ell$
parties, he sends the authentication path of the commitments, and the elements
to rebuild their shares. He then chooses one party, $i^{*}$, in $S\setminus
I$, and reveal the value $\llbracket\bm{\alpha}\rrbracket_{i^{*}}$ computed
for this party;

  * •

Thanks to this value, the verifier can recover everything he needs, and can
then authenticate, or not, the prover.

Note that the knowledge of $\ell$ shares provides no information on the
secret, since we use a $(\ell+1,N)$-threshold secret sharing. Moreover, this
method permits to reduce the number of operations, for the cost a larger
signature size (we refer to [FR22] for more details).

However, one limitation arises: when using Shamir’s secret sharings (or any
low-threshold LSSS), we need to have $N\leq q$ to share values of
$\mathbb{F}_{q}$. Finally, this gives us the proof of knowledge of Fig.10.

\- Public data $\bm{M}_{0},\dots,\bm{M}_{k}\in\mathbb{F}_{q}^{m\times n}$
$\displaystyle\@pc@lb$ The prover wants to convince the verifier that he knows
a solution $\bm{x}\in\mathbb{F}_{q}^{k}$ of the MinRank instance, i.e such as
$\bm{E}=\bm{M}_{0}+\sum_{i=1}^{k}\bm{M}_{i}x_{i}$ and
$\operatorname{W}_{R}(\bm{E})\leq r$ $\displaystyle\@pc@lb[]$ Step 1:
Commitment $\displaystyle\@pc@lb$ 1\. The prover builds a set of shares into a
$(\ell+1,N)-$threshold secret sharing of $\bm{x}$. The prover also builds
shares of the annihilator polynomial
$L(X)=X^{q^{r}}+\sum_{i=0}^{r-1}\beta_{i}\cdot X^{q^{i}}$ by setting
$U=\langle e_{1}\dots e_{n}\rangle$, where $\bm{e}=(e_{1},\dots,e_{n})$ is the
vector associated to $\bm{E}=\bm{M}_{0}+\sum_{i=1}^{k}\bm{M}_{i}x_{i}$, and
computing $L(X)=\prod_{u\in
U}(X-u)=X^{q^{r}}+\sum_{i=0}^{r-1}\beta_{i}(X^{q^{i}})$. He also builds a
vector $\bm{a}$ uniformly sampled from $\mathbb{F}_{q^{m\cdot\eta}}^{r}$, and
$c=-\langle\bm{\beta},\bm{a}\rangle$. Each party takes one share of the
previous elements. $\displaystyle\@pc@lb$ 2\. For each $i\in[1,N]$:
$\displaystyle\@pc@lb$ \-
${\mathsf{\vphantom{p}state}}_{i}=(\llbracket\bm{x}\rrbracket_{i},\llbracket\bm{\beta}\rrbracket_{i},\llbracket\bm{a}\rrbracket_{i}\llbracket
c\rrbracket_{i})$ $\displaystyle\@pc@lb$ 3\. The prover computes the
commitments:
$\mathsf{cmt}_{i}=\mathsf{Com}\big{(}{\mathsf{\vphantom{p}state}}_{i},\rho_{i}\big{)}$,
where $\rho_{i}$ is a randomization sampled from $\\{0,1\\}^{\lambda}$ for
each $i\in[1,N]$. $\displaystyle\@pc@lb$ 4\. The prover computes and sends the
Merkle tree root:
$h_{0}=\textsf{Merkle}(\mathsf{cmt}_{1},\cdots,\mathsf{cmt}_{N})$
$\displaystyle\@pc@lb[]$ Step 2: First Challenge $\displaystyle\@pc@lb$ 5\.
The verifier sends
$\big{(}(\gamma_{j})_{j\in[1,n]},\epsilon\big{)}\in\mathbb{F}_{q^{m\cdot\eta}}^{n}\times\mathbb{F}_{q^{m\cdot\eta}}$
to the prover. $\displaystyle\@pc@lb[]$ Step 3: First Response
$\displaystyle\@pc@lb$ 6\. The prover chooses a public subset $S$ of parties
such that $|S|=\ell+1$: $\displaystyle\@pc@lb$ 7\. The prover executes the
algorithm described in Fig.11 for the shares $i\in S$, and obtains
$(\llbracket\bm{\alpha}\rrbracket_{i},\llbracket v\rrbracket_{i})_{i\in S}$.
$\displaystyle\@pc@lb$ 8\. The prover computes the value
$h_{1}=\mathsf{H}\left((\llbracket\bm{\alpha}\rrbracket_{i},\llbracket
v\rrbracket_{i})_{i\in S}\right)$ $\displaystyle\@pc@lb[]$ Step 4: Second
Challenge $\displaystyle\@pc@lb$ 9\. The verifier sends a subset
$I\subset[1,N]$ of parties such that $|I|=\ell$ to the prover
$\displaystyle\@pc@lb[]$ Step 5: Second Response $\displaystyle\@pc@lb$ 10\.
The prover sends $({\mathsf{\vphantom{p}state}}_{i},\rho_{i})_{i\in I}$, and
the authentication path to these commitments, to allow the verifier to rebuild
the Merkle tree. The verifier deduces a value $\tilde{h}_{0}$.
$\displaystyle\@pc@lb$ 11\. The prover chooses a public party $i^{*}\in
S\backslash I$, and sends $\llbracket\bm{\alpha}\rrbracket_{i^{*}}$ to allow
the verifier to recover
$\bm{\alpha}=\mathsf{Reconstruct}_{I\bigcup\\{i^{*}\\}}(\llbracket\bm{\alpha}\rrbracket_{I\bigcup\\{i^{*}\\}})$
$\displaystyle\@pc@lb$ 12\. The verifier computes $\tilde{h}_{1}$ by choosing
$\llbracket v\rrbracket_{i^{*}}$ such that $v=0$. $\displaystyle\@pc@lb$

Figure 10: MinRank Proof of Knowledge based on Threshold MPCitH

Inputs: A set of shares
$\big{(}\llbracket\bm{x}\rrbracket_{i},\llbracket\bm{\beta}\rrbracket_{i},\llbracket\bm{a}\rrbracket_{i},\llbracket
c\rrbracket_{i}\big{)}_{i\in S}$ and a protocol challenge
$\big{(}(\gamma_{j})_{j\in[1,n]},\epsilon\big{)}$ $\displaystyle\@pc@lb$
Outputs: A set of shares $\llbracket v\rrbracket$ and a commitment $H$ of the
execution $\displaystyle\@pc@lb[]$ For each party $i\in S$:
$\displaystyle\@pc@lb$ \- Compute
$\llbracket\bm{E}\rrbracket_{i}=\bm{M}_{0}+\sum_{j=1}^{k}[\\![x_{j}]\\!]_{i}\bm{M}_{j}$
$\displaystyle\@pc@lb$ \- Set $[\\![e_{j}]\\!]_{i}$ as the element in
$\mathbb{F}_{q^{m}}$ associated to the j-th column of $[\\![E]\\!]_{i}$
$\displaystyle\@pc@lb$ \- Compute
$[\\![z]\\!]_{i}=-\sum_{j=1}^{n}\gamma_{j}\cdot[\\![e_{j}]\\!]_{i}^{q^{r}}$
$\displaystyle\@pc@lb$ \- For $k$ from $0$ to $r-1$: $\displaystyle\@pc@lb$
$\diamond$ Compute
$[\\![w_{k}]\\!]_{i}=\sum_{j=1}^{n}\gamma_{j}\cdot[\\![e_{j}]\\!]_{i}^{q^{k}}$
$\displaystyle\@pc@lb$ \- Compute
$[\\![\bm{\alpha}]\\!]_{i}=\epsilon\cdot[\\![\bm{w}]\\!]_{i}+[\\![\bm{a}]\\!]_{i}$
and reveal $\bm{\alpha}$ $\displaystyle\@pc@lb$ \- Compute
$[\\![v]\\!]_{i}=\epsilon\cdot[\\![z]\\!]_{i}-\langle\bm{\alpha},[\\![\bm{\beta}]\\!]_{i}\rangle-[\\![c]\\!]_{i}$
$\displaystyle\@pc@lb$

Figure 11: Execution of the MPC protocol $\Pi^{\eta}$ on a set of shares

Let us look at the soundness of the protocol. If the probability of a false
positive of the MPC protocol was equal to $0$ (i.e, the probability of a false
positive of $\Pi^{\eta}$ was $0$), then a malicious prover (who doesn’t know a
solution of the MinRank instance) would need to cheat for exactly $N-\ell$
parties. Indeed, if he cheated for less parties, then at least $\ell+1$ shares
would be consistent. Since we suppose the probability of false-positive is
$0$, this means he would know a good witness. If he cheated for more than
$N-\ell$ parties, the verifier would always ask for the opening of a corrupted
party, hence he would always discover the cheat. This means that the malicious
prover needs to cheat on exactly $N-\ell$ parties, and the only way that the
verifier is convinced is when the verifier asks the opening of the exact set
of the $\ell$ honest parties. This means that the probability that the
verifier does not detect the cheat is $\frac{1}{\binom{N}{\ell}}$.
However, $p$ is not $0$ in our case. We can make the same reasoning, and
furthermore, consider this false positive rate. We would expect to get a
probability for a malicious prover to convince a verifier of
$\frac{1}{\binom{N}{\ell}}+(1-\frac{1}{\binom{N}{\ell}})\cdot p$ (We remind
the reader that $p=\frac{2}{q^{m\eta}}-\frac{1}{q^{2m\eta}}$).
Unfortunately, it is just a lower bound of the soundness of the protocol. As
remarked in [FR22], there is a more effective way for a malicious prover to
cheat at the protocol, as we will see in the proof of the theorem 5.2 in
section 5.1.

####  3.2.2 MIRA-Threshold

From the zero-knowledge protocol, we can deduce a signature scheme thanks to
the Fiat-Shamir transformation. The resulting scheme is non-interactive and we
deterministically sample the challenge using a hash function. We must repeat
the zero-knowledge protocol several times ($\tau$ times), in order to achieve
a certain level of security. The obtained signature scheme is described in
Fig.12 and Fig.13.

Inputs $\displaystyle\@pc@lb$ \- Public data
$\bm{M}_{0},\dots,\bm{M}_{k}\in\mathbb{F}_{q}^{m\times n}$
$\displaystyle\@pc@lb$ \- Secret key
$\mathsf{\vphantom{p}sk}=(\bm{x})\in\mathbb{F}_{q}^{k}$,
$(\bm{E})\in\mathbb{F}_{q}^{m\times n}$ such that
$\operatorname{W}_{R}(\bm{E})\leq r$ and
$\bm{E}=\bm{M}_{0}+\sum_{i=1}^{k}\bm{M}_{i}x_{i}$ $\displaystyle\@pc@lb$ \-
Message $m\in\\{0,1\\}^{*}$ $\displaystyle\@pc@lb[]$ Step 1: Commitment
$\displaystyle\@pc@lb$ 1\. Sample a random salt value
$\mathsf{salt}\overset{\;\$}{\longleftarrow}\\{0,1\\}^{2\lambda}$
$\displaystyle\@pc@lb$ 2\. Compute
$\bm{\beta}=(\beta_{k})_{k\in[0,r-1]}\in\mathbb{F}_{q^{m}}^{r}$ the
coefficients of the annihilator q-polynomial $L(X)$ associated to $\bm{{E}}$
such that $L(X)=X^{q^{r}}+\sum_{k=0}^{r-1}\beta_{k}(X^{q^{k}})$ and $\forall
j\in[1,n],L(\bm{{e}}_{j})=0$ where each $\bm{{e}_{j}}$ is the element in
$\mathbb{F}_{q^{m}}$ associated to the j-th column of $E$
$\displaystyle\@pc@lb$ 3\. For each iteration $e\in[1,\tau]$:
$\displaystyle\@pc@lb$ \- Sample
$\bm{a}^{(e)}\overset{\;\$}{\longleftarrow}\mathbb{F}_{q^{m\cdot\eta}}^{r}$
and compute $c^{(e)}$ such that $c^{(e)}\in\mathbb{F}_{q^{m\cdot\eta}}$ and
$c^{(e)}=-\langle\bm{\beta},\bm{a}^{(e)}\rangle$ $\displaystyle\@pc@lb$ \- For
each party $i\in[1,N]$: $\displaystyle\@pc@lb$ $\diamond$ Compute the
$(\ell+1,N)$-threshold sharings
$\llbracket\bm{x}^{(e)}\rrbracket,\llbracket\bm{\beta}^{(e)}\rrbracket,\llbracket\bm{a}^{(e)}\rrbracket,\llbracket
c^{(e)}\rrbracket$ of $\bm{x},\bm{\beta},\bm{a}^{(e)}$ and $c^{(e)}$
$\displaystyle\@pc@lb$ $\diamond$ Compute
${\mathsf{\vphantom{p}state}}^{(e)}_{i}=(\llbracket\bm{x}^{(e)}\rrbracket_{i},\llbracket\bm{\beta}^{(e)}\rrbracket_{i},\llbracket\bm{a}^{(e)}\rrbracket_{i},\llbracket
c^{(e)}\rrbracket_{i})$ and
$\mathsf{cmt}^{(e)}_{i}=\mathsf{H}_{0}(\mathsf{salt},e,i,{\mathsf{\vphantom{p}state}}^{(e)}_{i})$
$\displaystyle\@pc@lb$ \- Compute the Merkle tree root
$h^{(e)}_{0}=\textsf{Merkle}(\mathsf{cmt}^{(e)}_{1},\cdots,\mathsf{cmt}^{(e)}_{N})$
$\displaystyle\@pc@lb$ 4\. Compute
$h_{1}=\mathsf{H}_{1}(m,\mathsf{\vphantom{p}pk},\mathsf{salt},(h^{(e)}_{0})_{e\in[1,\tau]})$
$\displaystyle\@pc@lb[]$ Step 2: First Challenge $\displaystyle\@pc@lb$ 5\.
Sample
$\big{(}(\gamma^{(e)}_{j})_{j\in[1,n]},\epsilon^{(e)}\big{)}_{e\in[1,\tau]}\overset{\;\$}{\longleftarrow}PRG(h_{1})$
where
$\big{(}(\gamma^{(e)}_{j})_{j\in[1,n]},\epsilon^{(e)}\big{)}_{e\in[1,\tau]}\in(\mathbb{F}_{q^{m\cdot\eta}}^{n}\times\mathbb{F}_{q^{m\cdot\eta}})^{\tau}$
$\displaystyle\@pc@lb[]$ Step 3: First Response $\displaystyle\@pc@lb$ 6\. For
each iteration $e\in[1,\tau]$: $\displaystyle\@pc@lb$ \- For each party $i\in
S$ with $S$ a public subset of parties such that $|S|=\ell+1$:
$\displaystyle\@pc@lb$ $\diamond$ Compute
$\llbracket\bm{E}^{(e)}\rrbracket_{i}=\bm{M_{0}}+\sum_{j=1}^{k}\bm{M_{j}}\llbracket
x_{j}\rrbracket_{i}$ and set $\llbracket e_{j}\rrbracket_{i}$ as the element
in $\mathbb{F}_{q^{m}}$ associated to the j-th column of
$\llbracket\bm{E}\rrbracket$ $\displaystyle\@pc@lb$ $\diamond$ Compute
$\llbracket
z^{(e)}\rrbracket_{i}=-\sum\nolimits_{j=1}^{n}\gamma_{j}\cdot\llbracket
e_{j}^{(e)}\rrbracket_{i}^{q^{r}}$ and $\forall k\in[0,r-1],\llbracket
w_{k}^{(e)}\rrbracket_{i}=\sum\nolimits_{j=1}^{n}\gamma_{j}\cdot\llbracket
e_{j}^{(e)}\rrbracket_{i}^{q^{k}}$ $\displaystyle\@pc@lb$ $\diamond$ Compute
$\llbracket\bm{\alpha}^{(e)}\rrbracket_{i}=\epsilon^{(e)}\cdot\llbracket\bm{w}^{(e)}\rrbracket_{i}+\llbracket\bm{a}^{(e)}\rrbracket_{i}$
and $\llbracket v^{(e)}\rrbracket_{i}=\epsilon^{(e)}\cdot\llbracket
z^{(e)}\rrbracket_{i}-\langle\bm{\alpha}^{(e)},\llbracket\bm{\beta}^{(e)}\rrbracket_{i}\rangle-\llbracket
c^{(e)}\rrbracket_{i}$ $\displaystyle\@pc@lb$ 7\. Compute
$h_{2}=\mathsf{H}_{2}(m,\mathsf{\vphantom{p}pk},\mathsf{salt},h_{1},(\llbracket\bm{\alpha}^{(e)}\rrbracket_{i},\llbracket
v^{(e)}\rrbracket_{i})_{i\in S,e\in[1,\tau]})$ $\displaystyle\@pc@lb[]$ Step
4: Second Challenge $\displaystyle\@pc@lb$ 8\. Sample
$(I^{(e)})_{e\in[1,\tau]}\overset{\;\$}{\longleftarrow}PRG(h_{2})$ where
$(I^{(e)})_{e\in[1,\tau]}\in(\\{I\subset N~{}|~{}|I|=\ell\\})^{\tau}$
$\displaystyle\@pc@lb[]$ Step 5: Second Response $\displaystyle\@pc@lb$ 9\.
For each iteration $e\in[1,\tau]$: $\displaystyle\@pc@lb$ \- Choose
deterministically a party $i^{*(e)}\in S\,\backslash\,I^{(e)}$ and compute
$\llbracket\bm{\alpha}^{(e)}\rrbracket_{i^{*(e)}}$ $\displaystyle\@pc@lb$ \-
Compute the authentication path $\mathsf{auth}^{(e)}$ associated to root
$h^{(e)}_{0}$ and $(\mathsf{cmt}^{(e)}_{i})_{i\in I^{(e)}}$
$\displaystyle\@pc@lb$ \- Compute
$\mathsf{rsp}^{(e)}=\big{(}(\llbracket\bm{x}^{(e)}\rrbracket_{i},\llbracket\bm{\beta}^{(e)}\rrbracket_{i},\llbracket\bm{a}^{(e)}\rrbracket_{i},\llbracket
c^{(e)}\rrbracket_{i})_{i\in
I^{(e)}},\mathsf{auth}^{(e)},\llbracket\bm{\alpha}^{(e)}\rrbracket_{i^{*(e)}}\big{)}$
$\displaystyle\@pc@lb$

Figure 12: MIRA Signature Scheme based on Threshold MPCitH - Signature
Algorithm

Inputs $\displaystyle\@pc@lb$ \- Public data
$\bm{M}_{0},\dots,\bm{M}_{k}\in\mathbb{F}_{q}^{m\times n}$ such that there is
$\bm{x}\in\mathbb{F}_{q}^{k}$ such that
$\bm{E}=\bm{M}_{0}+\sum_{i=1}^{k}(\bm{M}_{i}x_{i})$ and
$\operatorname{W}_{R}(\bm{E})\leq r$ $\displaystyle\@pc@lb$ \- Message
$m\in\\{0,1\\}^{*}$ $\displaystyle\@pc@lb$ \- Signature
$\sigma=(\mathsf{salt},h_{1},h_{2},(\bar{\mathsf{rsp}}^{(e)})_{e\in[1,\tau]})$
$\displaystyle\@pc@lb[]$ Step 1: Parse signature $\displaystyle\@pc@lb$ 1\.
Sample
$\big{(}(\gamma^{(e)}_{j})_{j\in[1,n]},\epsilon^{(e)}\big{)}_{e\in[1,\tau]}\overset{\;\$}{\longleftarrow}PRG(h_{1})$
where
$\big{(}(\gamma^{(e)}_{j})_{j\in[1,n]},\epsilon^{(e)}\big{)}_{e\in[1,\tau]}\in(\mathbb{F}_{q^{m\cdot\eta}}^{n}\times\mathbb{F}_{q^{m\cdot\eta}})^{\tau}$
$\displaystyle\@pc@lb$ 2\. Sample
$(I^{(e)})_{e\in[1,\tau]}\overset{\;\$}{\longleftarrow}PRG(h_{2})$ where
$(I^{(e)})_{e\in[1,\tau]}\in(\\{I\subset N~{}|~{}|I|=\ell\\})^{\tau}$
$\displaystyle\@pc@lb$ 3\. For each iteration $e\in[1,\tau]$:
$\displaystyle\@pc@lb$ \- Choose deterministically $i^{*(e)}$ from $S\setminus
I^{(e)}$ $\displaystyle\@pc@lb$ \- Parse
$\bar{\mathsf{rsp}}^{(e)}:=\big{(}(\llbracket\bar{\bm{x}}^{(e)}\rrbracket_{i},\llbracket\bar{\bm{\beta}}^{(e)}\rrbracket_{i},\llbracket\bar{\bm{a}}^{(e)}\rrbracket_{i},\llbracket\bar{c}^{(e)}\rrbracket_{i})_{i\in\bar{I}^{(e)}},\bar{\mathsf{auth}}^{(e)},\llbracket\bar{\bm{\alpha}}^{(e)}\rrbracket_{i^{*(e)}}\big{)}$
$\displaystyle\@pc@lb[]$ Step 1: Recompute $\bm{h}_{1}$ $\displaystyle\@pc@lb$
4\. For each iteration $e\in[1,\tau]$: $\displaystyle\@pc@lb$ \- For each
party $i\in I^{(e)}$: $\displaystyle\@pc@lb$ $\diamond$ Compute
$\bar{{\mathsf{\vphantom{p}state}}}^{(e)}_{i}=(\llbracket\bar{\bm{x}}^{(e)}\rrbracket_{i},\llbracket\bar{\bm{\beta}}^{(e)}\rrbracket_{i},\llbracket\bar{\bm{a}}^{(e)}\rrbracket_{i},\llbracket\bar{c}^{(e)}\rrbracket_{i})$
and
$\bar{\mathsf{cmt}}^{(e)}_{i}=\mathsf{H}_{0}(\mathsf{salt},e,i,\bar{{\mathsf{\vphantom{p}state}}}^{(e)}_{i})$
$\displaystyle\@pc@lb$ \- Compute the Merkle tree root $\bar{h}^{(e)}_{0}$
from $(\bar{\mathsf{cmt}}^{(e)}_{i})_{i\in I^{(e)}}$ and
$\bar{\mathsf{auth}}^{(e)}$ $\displaystyle\@pc@lb$ 5\. Compute
$\bar{h}_{1}=\mathsf{H}_{1}(m,\mathsf{\vphantom{p}pk},\mathsf{salt},(\bar{h}^{(e)}_{0})_{e\in[1,\tau]})$
$\displaystyle\@pc@lb[]$ Step 2: Recompute $\bm{h}_{2}$ $\displaystyle\@pc@lb$
6\. For each iteration $e\in[1,\tau]$: $\displaystyle\@pc@lb$ \- For each
party $i\in I^{(e)}$: $\displaystyle\@pc@lb$ $\diamond$ Compute
$\llbracket\bm{E}^{(e)}\rrbracket_{i}=\bm{M}_{0}+\sum_{j=1}^{k}\bm{M}_{j}\llbracket
x_{j}\rrbracket_{i}$ and set $\llbracket e_{j}\rrbracket_{i}$ as the element
in $\mathbb{F}_{q^{m}}$ associated to the $j$-th column of
$\llbracket\bm{E}\rrbracket$ $\displaystyle\@pc@lb$ $\diamond$ Compute
$\llbracket
z^{(e)}\rrbracket_{i}=-\sum\nolimits_{j=1}^{n}\gamma_{j}\cdot\llbracket
e_{j}^{(e)}\rrbracket_{i}^{q^{r}}$ and $\forall k\in[0,r-1],\llbracket
w_{k}^{(e)}\rrbracket_{i}=\sum\nolimits_{j=1}^{n}\gamma_{j}\cdot\llbracket
e_{j}^{(e)}\rrbracket_{i}^{q^{k}}$ $\displaystyle\@pc@lb$ $\diamond$ Compute
$\llbracket\bm{\alpha}^{(e)}\rrbracket_{i}=\epsilon^{(e)}\cdot\llbracket\bm{w}^{(e)}\rrbracket_{i}+\llbracket\bm{a}^{(e)}\rrbracket_{i}$
$\displaystyle\@pc@lb$ \- Reconstruct $\bar{\bm{\alpha}}^{(e)}$ and
$(\llbracket\bar{\bm{\alpha}}^{(e)}\rrbracket_{i})_{i\in S}$ from
$(\llbracket\bar{\bm{\alpha}}^{(e)}\rrbracket_{i})_{i\in I^{(e)}}$ and
$\llbracket\bar{\bm{\alpha}}^{(e)}\rrbracket_{i^{*(e)}}$
$\displaystyle\@pc@lb$ 7\. For each iteration $e\in[1,\tau]$:
$\displaystyle\@pc@lb$ \- For each party $i\in I^{(e)}$:
$\displaystyle\@pc@lb$ $\diamond$ Compute
$\llbracket\bar{v}^{(e)}\rrbracket_{i}=\epsilon^{(e)}\cdot\llbracket\bar{z}^{(e)}\rrbracket_{i}-\langle\bar{\bm{\alpha}}^{(e)},\llbracket\bar{\bm{\beta}}^{(e)}\rrbracket_{i}\rangle-\llbracket\bar{c}^{(e)}\rrbracket_{i}$
$\displaystyle\@pc@lb$ \- Reconstruct
$(\llbracket\bar{v}^{(e)}\rrbracket_{i})_{i\in S}$ from
$(\llbracket\bar{v}^{(e)}\rrbracket_{i})_{i\in I^{(e)}}$ and $\bar{v}^{(e)}=0$
$\displaystyle\@pc@lb$ 8\. Compute
$\bar{h}_{2}=\mathsf{H}_{2}(m,\mathsf{\vphantom{p}pk},\mathsf{salt},\bar{h}_{1},(\llbracket\bar{\bm{\alpha}}^{(e)}\rrbracket_{i},\llbracket\bar{v}^{(e)}\rrbracket_{i})_{i\in
S,e\in[1,\tau]})$ $\displaystyle\@pc@lb[]$ Step 5: Verify signature
$\displaystyle\@pc@lb$

Figure 13: MIRA Signature Scheme based on Threshold MPCitH - Verification
Algorithm

We prove that the scheme is EUF-CMA secure in the proof of theorem 5.4 in 5.2.

##  4 Parameter Sets

###  4.1 Parameters Choice

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
$\bm{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 $\bm{E}$;

  * •

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

  * •

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

  * •

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

In the LSSS-based scheme, there is also a parameter $\ell\in\mathbb{N}$, which
is the value of the privacy threshold of the used linear secret sharing
scheme.

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 MinRank parameters;

  * •

The security of the signature scheme, i.e. the cost of the best forgery
attack;

  * •

The size of the signature.

We propose the following parameters for the MinRank instance, for the security
level which corresponds to the NIST Security Level 1:

  * •

For the additive-based scheme: $(q,m,n,k,r)=(16,16,16,120,5)$;

  * •

For the LSSS-based scheme: $(q,m,n,k,r)=(251,12,13,55,5)$.

In the first scheme, we take the value of $q=16$, since it leads to almost the
shortest signature size and has the advantage to be easily serialized (two
elements of $\mathbb{F}_{q}$ can be stored in a byte). However, in the second
scheme, we take $q=251$ since we have the constraint $N\leq q$ with Shamir’s
secret sharing (since each share is associated to a distinct field element, we
can not have more shares than the size of the field). Since the protocol is
more efficient when $N$ is large, we need to take a larger value of $q$ in the
threshold-based scheme compared to the additive-based scheme. The parameters
$(m,n,k,r)$ are then chosen such that the MinRank instances are secure against
the existing attacks, that we present shortly in section 6.2, and such that
$k+1=(m-r)(n-r)$, as it corresponds exactly to the Gilbert-Varshamov bound.

Finally, we need to choose $\tau$ and $\eta$ such that our signature scheme
resists to the forgery attack described by [KZ20]. More precisely, in the
additive-based scheme, we select them such that

$\text{cost}_{\text{forge}}=\min_{0\leq\tau^{\prime}\leq\tau}\left\\{\dfrac{1}{\sum_{i=\tau^{\prime}}^{\tau}\binom{\tau}{i}p^{i}(1-p)^{\tau-i}}+N^{\tau-\tau^{\prime}}\right\\}$
(3)

is higher than $2^{\lambda}$, with
$p=\frac{2}{q^{m\eta}}-\frac{1}{q^{2m\eta}}$. In the case of the threshold
protocol, this formula becomes:

$\text{cost}_{\text{forge}}=\min_{0\leq\tau^{\prime}\leq\tau}\left\\{\dfrac{1}{\sum_{i=\tau^{\prime}}^{\tau}\binom{\tau}{i}p^{i}(1-p)^{\tau-i}}+\binom{N}{\ell}^{\tau-\tau^{\prime}}\right\\}$
(4)

with $p=(\frac{2}{q^{m\eta}}-\frac{1}{q^{2m\eta}})\cdot\binom{N}{\ell+1}$. The
factor $\binom{N}{\ell+1}$ in the value of $p$ comes from the fact that an
attacker can commit an invalid sharing of the MPC inputs in the first step of
the scheme (see [FR22] for details), and the addition of
$\binom{N}{\ell}^{\tau-\tau^{\prime}}$ comes from the fact that there are
$\binom{N}{\ell}$ possible second challenges.

In any case, as long as the forgery cost is high enough, we can just take the
parameters which lead to the shortest signatures. To proceed, we need to
compute the theoretical size of the signature, which we will do in the
following section.

###  4.2 Key and Signature Sizes

####  4.2.1 Additive Protocol Signature Size

For the additive-sharing protocol (Fig.8), we have to send $\tau$ times the
following elements:

  * •

$com_{i^{*}}\in\\{0,1\\}^{2\lambda}$;

  * •

$(state_{i^{\prime}}^{(e)})_{i^{\prime}\neq i^{*}}$;

  * •

$[\\![\bm{\alpha}]\\!]\in\mathbb{F}_{q^{m\eta}}^{r}$;

  * •

$[\\![\bm{x}]\\!]\in\mathbb{F}_{q}^{k}$;

  * •

$[\\![\bm{\beta}]\\!]\in\mathbb{F}_{q^{m}}^{r}$;

  * •

$[\\![c]\\!]\in\mathbb{F}_{q^{m\eta}}$.

Note that for each $e\in[1,\tau]$, we do not send all the $N-1$ states
$(state_{i^{\prime}}^{(e)})_{i^{\prime}\neq i^{*}}$. To reveal the state of
all the parties except one, the prover only need to send the sibling path of
the hidden leaf party in the seed tree of TreePRG. Thus, the number of
revealed seeds in $\\{0,1\\}^{\lambda}$ is equal to the depth of the tree,
which is $D=\log_{2}N$. We also add $h_{1},h_{2},\text{ and
}\mathsf{salt}\in\\{0,1\\}^{2\lambda}$, which add up to $6\lambda$. This gives
us the following signature size (in bits):

$|\sigma|$
$\displaystyle=\underbrace{6\lambda}_{\text{$\mathsf{salt},h1,h2$}}+\tau\cdot\left(\Big{(}\underbrace{k}_{\text{$\bm{x}$}}+\underbrace{r\times
m}_{\text{$\bm{\beta}$}}+\underbrace{(r+1)\times
m\times\eta}_{\text{$\bm{\alpha}$~{}\text{and}~{}$c$}}\Big{)}\cdot\log_{2}q+\underbrace{2\lambda+D\lambda}_{\text{additive
MPCitH}}\right).$

We then obtain the following sizes:

NIST Security Level | $q$ | $m$ | $n$ | $k$ | $r$ | $N$ | $\tau$ | $\eta$ |  Public Key size (Bytes) |  Secret Key size (Bytes) |  Signature size (Bytes)
---|---|---|---|---|---|---|---|---|---|---|---
1 | 16 | 16 | 16 | 120 | 5 | 256 | 18 | 1 | 84 | 16 | 5.640
3 | 16 | 19 | 19 | 168 | 6 | 256 | 26 | 1 | 121 | 24 | 11.779
5 | 16 | 23 | 22 | 271 | 6 | 256 | 34 | 1 | 150 | 32 | 20.762

####  4.2.2 Threshold Protocol Signature Size

For the threshold sharing protocol (Fig.12), we have to send $\tau$ times the
following elements:

  * •

$\ell$ times $\llbracket\bm{x}\rrbracket\in\mathbb{F}_{q}^{k}$;

  * •

$\ell$ times $\llbracket\bm{\beta}\rrbracket\in\mathbb{F}_{q^{m}}^{r}$;

  * •

$\ell$ times $\llbracket\bm{a}\rrbracket\in\mathbb{F}_{q^{m\cdot\eta}}^{r}$;

  * •

$\ell$ times $\llbracket c\rrbracket\in\mathbb{F}_{q^{m}}$;

  * •

$\llbracket\bm{\alpha}\rrbracket\in\mathbb{F}_{q^{m\cdot\eta}}^{r}$;

  * •

the authentification path $\mathsf{auth}$.

Let us remark that we cannot use a TreePRG for the threshold scheme, since the
shares of a low-threshold sharing are correlated.

For the authentification path, we do not need to send all the states. Indeed,
to allow the verification of $\ell$ states, the prover sends their sibling
paths which at most contain $\ell\cdot\log_{2}(\frac{N}{\ell})$ labels in
total (each of $2\lambda$ bits). In the sizes we will give, we are going to
use the average cost (with low deviation) of sending the sibling paths. We
also send $h_{1},h_{2},\text{ and }\mathsf{salt}\in\\{0,1\\}^{2\lambda}$,
which add up to $6\lambda$. We find the following signature size (in bits):

$|\sigma|\leq\underbrace{6\lambda}_{\mathsf{salt},h1,h2}+\tau\cdot\Big{(}\big{(}\ell\cdot(\underbrace{k}_{\bm{x}}+\underbrace{r\times
m}_{\text{${\bm{\beta}}$}}+\underbrace{(r+1)\times m\times\eta}_{\text{$a$ and
$c$}})+\underbrace{r\times
m\times\eta}_{\text{$\bm{\alpha}$}}\big{)}\cdot\log_{2}(q)+\underbrace{2\lambda\cdot\ell\log_{2}(\frac{N}{\ell})}_{\text{Threshold
MPCitH}}\Big{)}.$

We then obtain the following sizes:

NIST Security Level | $q$ | $m$ | $n$ | $k$ | $r$ | $N$ | $\ell$ | $\tau$ | $\eta$ |  Public Key size (Bytes) |  Secret Key size (Bytes) |  Signature size (Bytes)
---|---|---|---|---|---|---|---|---|---|---|---|---
1 | 251 | 12 | 13 | 55 | 5 | 251 | 3 | 7 | 1 | 117 | 16 | 8.318
3 | 251 | 16 | 15 | 109 | 5 | 251 | 3 | 10 | 1 | 155 | 24 | 17.797
5 | 251 | 16 | 17 | 109 | 6 | 251 | 3 | 14 | 1 | 195 | 32 | 30.381

##  5 Security Analysis

###  5.1 Security Proofs for the Proofs of Knowledge

####  5.1.1 Security Proofs for the Additive Protocol

We first need to prove that the proof of knowledge is sound and zero-
knowledge:

###### Theorem 5.1

The MinRank Proof of Knowledge protocol based on additive secret sharing
described in Fig.5 has the following properties:

  * •

Completeness: A prover $\mathcal{P}$ who has the knowledge of a solution of a
MinRank instance will always be accepted by the verifier.

  * •

Soundness: Suppose that there is an efficient prover $\tilde{\mathcal{P}}$
that convinces the verifier to accept with probability

$\tilde{\epsilon}>\epsilon$

with

$\epsilon=\frac{1}{N}+p\cdot(1-\frac{1}{N})$

where $\epsilon$ is the soundness of the protocol in Fig.5, and $p$ is the
false positive rate of the MPC protocol used, i.e,
$\frac{2}{q^{m\eta}}-\frac{1}{q^{2m\eta}}$.
Then, there is an efficient probabilistic extraction algorithm, $\mathcal{E}$
that, given a rewindable black-box access to $\tilde{\mathcal{P}}$, outputs
either a solution of the MinRank instance, or a commitment collision by making
a number of calls to $\tilde{\mathcal{P}}$ which is bounded by

$\frac{4}{\tilde{\epsilon}-\epsilon}\cdot\Big{(}1+\tilde{\epsilon}\cdot\frac{2\operatorname{ln}(2)}{\tilde{\epsilon}-\epsilon}\Big{)}$

  * •

Honest-Verifier Zero-Knowledge If the pseudo-random generator algorithm PRG
and the commitment $\mathsf{Com}$ are indistinguishable from the uniform
random distribution, then the algorithm 5 is Honest-Verifier Zero Knowledge.

###### Proof

Completeness:
By construction, if the prover has knowledge of a solution of the MinRank
instance, he will always be able to execute the protocol correctly, i.e, he
will always obtain $\bm{\alpha}$ such that $v=0$ when executing the MPC
protocol $\Pi^{\eta}$, this is obvious.

Soundness:
We first need to establish that the probability for the malicious prover (who
has no knowledge of the solution of the MinRank instance used and thus uses a
bad witness) to cheat is at most $\epsilon=\frac{1}{N}+(1-\frac{1}{N})\cdot
p$.
There are two situations where a malicious prover can be accepted by the
verifier if he commits a bad witness:

  * •

He obtains the value $v=0$ when executing the MPC protocol;

  * •

The verifier believes that the value obtained $v$ is $0$.

We suppose here that the malicious prover commits a bad witness. Then, the
first case occurs with probability
$p=\frac{2}{q^{m\eta}}-\frac{1}{q^{2m\eta}}$ since it is the false positive
rate of the protocol $\Pi^{\eta}$.

In the second case, the malicious prover needs to alter the communications in
order to pass the verification. More precisely, he needs to alter the value of
some share(s) of $\bm{\alpha}$ in every MPC protocol. Among the $N$ leaf
shares, only one share, $i^{*}$, will not be revealed by the prover. This
means that, if he cheats on more than one share, the verifier will notice the
cheating, and thus rejects the proof. However, if he cheats on zero share, he
will be rejected as well since the value $v$ will not be $0$ since the
malicious prover doesn’t have a good witness $\bm{x}$. This means the
malicious prover can only cheat on one share exactly. However, cheating on one
share means cheating on one main share on all the $D$ dimensions, as the main
shares are the sum of leaves that have the same index $i_{j}$ along the
current dimension. This means that the cheating is not detected if and only if
the share the prover cheated on is $i^{*}$, since there exists a bijection
between leaves and the set of their associated main party. This happens with
probability $\frac{1}{N}$ (as the prover doesn’t know the value of $i^{*}$
before cheating).
This is the only pattern to cheat and avoid detection (as shown just now, we
cannot cheat on more than one leaf), since cheating on $1$ main party for each
dimension is exactly equivalent to cheating on $1$ leaf party.
Thus, since there is no other cheating pattern possible, the probability for
the malicious prover to be authenticated is at most
$p+(1-p)\cdot\frac{1}{N}=\frac{1}{N}+(1-\frac{1}{N})\cdot p$.
We then need to show the soundness property in the theorem:
let $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ two transcripts with the same
commitments, i.e, the same
$h_{0}=\mathsf{H}({\mathsf{cmt}_{1},\dots,\mathsf{cmt}_{N}})$ , but the second
challenges $i^{*}_{1}$ (for $\mathcal{T}_{1}$) and $i^{*}_{2}$ (for
$\mathcal{T}_{2}$) differ.

Then, we have two possibilities:

  * •

$\llbracket\bm{x}\rrbracket,\llbracket\bm{\beta}\rrbracket,\llbracket\bm{a}\rrbracket$
and $\llbracket c\rrbracket$ differ in the two transcripts, and the malicious
prover found a collision in the commitment hash;

  * •

the openings of the commitments are equal, and thus the shares
$\llbracket\bm{x}\rrbracket,\llbracket\bm{\beta}\rrbracket,\llbracket\bm{a}\rrbracket$
and $\llbracket c\rrbracket$ are equal in the transcripts.

We will only consider the second case, as we suppose that we use secure hash
functions and secure commitment schemes.

Then, since $i^{*}_{1}$ and $i^{*}_{2}$ are different challenges and the
commitments are the same, it is possible to recover the witness. We will then
show we can build an extraction algorithm $\mathcal{E}$ that obtains a good
witness.

$\bm{x}$ is called a good witness if it is a solution to the MinRank instance
defined by public data, i.e. $\bm{E}=\bm{M}_{0}+\sum_{i=1}^{k}\bm{M}_{i}x_{i}$
and $\operatorname{W}_{R}(\bm{E})\leq r$. Let $R_{h}$ the random variable
associated to the randomness in initial commitment, and $r_{h}$ is the value
it takes. For that, we will use the Splitting Lemma as is done in [FJR22] and
[AMGH+22].

To get these two transcripts, the extraction algorithm $\mathcal{E}$ does the
following:

  * •

Run the protocol with randomness $r_{h}$ with the verifier until
$\mathcal{T}_{1}$ is found, i.e, $\mathcal{T}_{1}$ is the first accepted
transcript found by $\mathcal{\tilde{P}}$. We note $i^{*}_{1}$ the leaf
challenge obtained;

  * •

Then, using the same randomness $r_{h}$ that was used, i.e, building the same
commitments, $\mathcal{E}$ repeats the process $L$ times (where the value of
$L$ is made explicit hereafter) until finding another accepted transcript,
$\mathcal{T}_{2}$, for which the leaf challenge, $i^{*}_{2}$, is different
than $i^{*}_{1}$;

  * •

If such a transcript $\mathcal{T}_{2}$ is found, then $\mathcal{E}$ recovers
the witness, otherwise, if no such transcript is found after $L$ attempts,
$\mathcal{E}$ returns to the first step and tries with another $r_{h}$.

In order to establish the soundness of the protocol, we need to estimate the
number of times a malicious prover needs to repeat the authentication protocol
in order to get the good witness $\bm{x}$.
Let $\delta\in]0,1[$, and $\tilde{\epsilon}$ such that
$(1-\delta)\cdot\tilde{\epsilon}>\epsilon$. We will define the randomness
$r_{h}$ to be a good randomness if
$\mathsf{Pr}[\operatorname{Succ}_{\mathcal{\tilde{P}}}|r_{h}]>(1-\delta)\cdot\tilde{\epsilon}$.

By the Splitting Lemma (Lemma 1), we have that
$\mathsf{Pr}[r_{h}\>good|\operatorname{Succ}_{\tilde{\mathcal{P}}}]\geq\delta$.
This means that after $\frac{1}{\delta}$ accepted transcripts, we have good
odds to have a good randomness. Furthermore, we know that if the malicious
prover uses a bad witness, his probability to cheat is bounded from above by
$\epsilon$. Since the probability of success is greater than $\epsilon$, this
means that a good witness has been used (when $r_{h}$ is good).

To continue this proof, we will look at the probability to have, given an
accepted transcript $\mathcal{T}_{1}$, a second accepted transcript,
$\mathcal{T}_{2}$, with a challenge different than the one in
$\mathcal{T}_{1}$. This means we are looking to bound from below the
probability:

$\mathsf{Pr}[\operatorname{Succ}_{\tilde{\mathcal{P}}}\cap(i^{*}_{1}\neq
i^{*}_{2})|r_{h}\>good]$

Trivially, we know that this probability is equal to the probability of
success knowing that $r_{h}$ is good, minus the probability of success with
$i^{*}_{1}=i^{*}_{2}$ knowing $r_{h}$ is good. This means:

$\displaystyle\mathsf{Pr}[\operatorname{Succ}_{\tilde{\mathcal{P}}}\cap(i^{*}_{1}\neq
i^{*}_{2})|r_{h}\text{ }good]$
$\displaystyle=\mathsf{Pr}[\operatorname{Succ}_{\tilde{\mathcal{P}}}|r_{h}\text{
}good]-\mathsf{Pr}[\operatorname{Succ}_{\tilde{\mathcal{P}}}\cap(i^{*}_{1}=i^{*}_{2})|r_{h}\text{
}good]$
$\displaystyle\geq\mathsf{Pr}[\operatorname{Succ}_{\tilde{\mathcal{P}}}|r_{h}\>good]-\frac{1}{N}$
$\displaystyle\geq(1-\delta)\tilde{\epsilon}-\frac{1}{N}$
$\displaystyle\geq(1-\delta)\tilde{\epsilon}-\epsilon\qquad\text{ (since
$\epsilon\geq\frac{1}{N}$ trivially)}$

Now that we have this lower bound, we want to estimate the number of times one
has to repeat the protocol to find $\mathcal{T}_{2}$. For that, we take the
opposite probability, i.e,
$1-\mathsf{Pr}[\operatorname{Succ}_{\tilde{\mathcal{P}}}\cap(i^{*}_{1}\neq
i^{*}_{2})|r_{h}\text{ }good]$, which is lower bounded by
$1-((1-\delta)\tilde{\epsilon}-\epsilon)$. We now want a probability of
$\frac{1}{2}$ at least of success after $L$ tries of the authentication
protocol. This means then that we want:

$\displaystyle\Big{(}1-\mathsf{Pr}[\operatorname{Succ}_{\tilde{\mathcal{P}}}\cap(i^{*}_{1}\neq
i^{*}_{2})|r_{h}\text{ }good]\Big{)}^{L}$ $\displaystyle<{\frac{1}{2}}$
$\displaystyle L\cdot\ln(1-((1-\delta)\tilde{\epsilon}-\epsilon))$
$\displaystyle<-\ln(2)$ $\displaystyle L$
$\displaystyle>-\frac{\ln(2)}{\ln(1-((1-\delta)\tilde{\epsilon}-\epsilon))}$

One obtains the following majoration for the number of calls to
$\mathcal{\tilde{P}}$:

$L>\frac{\ln(2)}{\ln(\frac{1}{1-((1-\delta)\tilde{\epsilon}-\epsilon)})}\approx\frac{\ln(2)}{(1-\delta)\tilde{\epsilon}-\epsilon}$

This means that, when repeating the protocol $L$ times, the probability to get
the second transcript is higher than $\frac{1}{2}$.

Finally, we can look at the number of protocol repetitions that has to be
done. To quickly remind the steps of the extraction:

  * •

$\tilde{\mathcal{P}}$ repeats the authentication protocol until he finds an
accepted transcript $\mathcal{T}_{1}$, where the commitments are generated by
$r_{h}$, and with second challenge $i^{*}_{1}$;

  * •

When $\mathcal{T}_{1}$ is found, repeat the protocol with the same value
$r_{h}$, $L$ times. After that, $\tilde{\mathcal{P}}$ has more than
$\frac{1}{2}$ chance of being successful. If he is not, he repeats from the
first step of the procedure.

We will note $\mathbb{E}(\tilde{\mathcal{P}})$ the number of calls the
extractor $\mathcal{E}$ has to make to $\tilde{\mathcal{P}}$. After $L$ calls
(to find $\mathcal{T}_{2}$), if $r_{h}$ is good (which happens with
probability $\delta$), we have $\frac{1}{2}$ chance of not finding
$\mathcal{T}_{2}$. However, if $r_{h}$ is not good (with probability
$1-\delta$), then we can consider that $\mathcal{T}_{2}$ is never found.

Thus, $\mathsf{Pr}[\text{no
}\mathcal{T}_{2}|\operatorname{Succ}_{\tilde{\mathcal{P}}}]=\frac{\delta}{2}+(1-\delta)=1-\frac{\delta}{2}$.
If that happens, then, $\tilde{\mathcal{P}}$ has to return to the first step,
i.e, find $\mathcal{T}_{1}$ again. This means:

$\mathbb{E}(\tilde{\mathcal{P}})\leq
1+{\Big{(}(1-\mathsf{Pr}[\operatorname{Succ}_{\tilde{\mathcal{P}}}])\mathbb{E}(\tilde{\mathcal{P}})\Big{)}}+\mathsf{Pr}[\operatorname{Succ}_{\tilde{\mathcal{P}}}]\Big{(}L+(1-\frac{\delta}{2})\mathbb{E}(\tilde{\mathcal{P}})\Big{)}$

Obviously, $\tilde{\mathcal{P}}$ needs to run at least once. Then, we need to
add to that the number of times expected before finding $\mathcal{T}_{1}$, and
then, the number of times expected before finding $\mathcal{T}_{2}$.
Since
$\mathsf{Pr}[\operatorname{Succ}_{\tilde{\mathcal{P}}}]=\tilde{\epsilon}$ (by
assumption), we can replace, and simplify the expression. We find then:

$\displaystyle\mathbb{E}(\tilde{\mathcal{P}})$ $\displaystyle\leq
1+{\Big{(}(1-\tilde{\epsilon}\cdot\mathbb{E}(\tilde{\mathcal{P}})\Big{)}}+\tilde{\epsilon}\cdot\Big{(}L+(1-\frac{\delta}{2})\cdot\mathbb{E}(\tilde{\mathcal{P}})\Big{)}$
$\displaystyle\mathbb{E}(\tilde{\mathcal{P}})$ $\displaystyle\leq
1+\mathbb{E}(\tilde{\mathcal{P}})-\tilde{\epsilon}\cdot\mathbb{E}(\tilde{\mathcal{P}})+\tilde{\epsilon}\cdot
L+\tilde{\epsilon}\cdot\mathbb{E}(\tilde{\mathcal{P}})-\tilde{\epsilon}\cdot\frac{\delta}{2}\cdot\mathbb{E}(\tilde{\mathcal{P}})$
$\displaystyle\tilde{\epsilon}\cdot\frac{\delta}{2}\cdot\mathbb{E}(\tilde{\mathcal{P}})$
$\displaystyle\leq 1+\tilde{\epsilon}\cdot L$
$\displaystyle\mathbb{E}(\tilde{\mathcal{P}})$
$\displaystyle\leq\frac{2}{\tilde{\epsilon}\cdot\delta}\Big{(}1+\tilde{\epsilon}\cdot
L\Big{)}=\frac{2}{\tilde{\epsilon}\cdot\delta}\Big{(}1+\tilde{\epsilon}\cdot\frac{\ln(2)}{(1-\delta)\tilde{\epsilon}-\epsilon}\Big{)}$

Since this equality holds for any $\delta\in]0,1[$, we can take $\delta$ such
that $(1-\delta)\tilde{\epsilon}=\frac{1}{2}(\tilde{\epsilon}+\epsilon)$, and
thus, we obtain the result:

$\displaystyle\mathbb{E}(\tilde{\mathcal{P}})\leq\frac{4}{\tilde{\epsilon}-\epsilon}\cdot\Big{(}1+2\tilde{\epsilon}\cdot\frac{\ln(2)}{\tilde{\epsilon}-\epsilon}\Big{)}$

This means we found an upper bound on the number of calls the extractor
$\mathcal{E}$ has to make to $\tilde{\mathcal{P}}$ before retrieving a good
witness, in the case where the probability to cheat was higher than
$\epsilon$.

Honest-Verifier Zero-Knowledge:
Consider a simulator, described in Fig. 14, which produces the transcript
responses ($h_{0}$, $\mathsf{ch}_{1}$, $h_{1}$, $\mathsf{ch}_{2}$,
$\mathsf{rsp}$). We demonstrate that this simulator produces indistinguishable
transcripts from the real distribution (the one that we would obtain if it
were generated by an honest prover who knows $\bm{x}$) by considering a
succession of simulators: we begin by a simulator which produces true
transcripts, and and change it gradually until arriving the following
simulator. We explains why the distribution of transcripts is always the same
at each step.

\- Public data $\bm{M}_{0},\dots,\bm{M}_{k}\in\mathbb{F}_{q}^{m\times n}$
$\displaystyle\@pc@lb[]$ Step 1: Sample challenges $\displaystyle\@pc@lb$ 1\.
Sample challenges: $\displaystyle\@pc@lb$ \- First challenge:
$\mathsf{ch}_{1}=\big{(}(\gamma_{j})_{j\in[1,n]},\epsilon\big{)}\overset{\;\$}{\longleftarrow}\mathbb{F}_{q^{m\cdot\eta}}^{n}\times\mathbb{F}_{q^{m\cdot\eta}}$
$\displaystyle\@pc@lb$ \- Second challenge:
$\mathsf{ch}_{2}=i^{*}\overset{\;\$}{\longleftarrow}[1,N]$
$\displaystyle\@pc@lb[]$ Step 2: Compute shares and their commitments
$\displaystyle\@pc@lb$ 2\. Sample a seed for pseudo-random generator:
$\mathsf{seed}\overset{\;\$}{\longleftarrow}\\{0,1\\}^{\lambda}$
$\displaystyle\@pc@lb$ 3\. Expand root seed recursively using TreePRG to
obtain $N$ leafs and seeds $(\mathsf{seed}_{i^{\prime}},\rho_{i^{\prime}})$
$\displaystyle\@pc@lb$ 4\. For each $i\in[1,N]\setminus i^{*}$:
$\displaystyle\@pc@lb$ \- Sample
$\llbracket\bm{a}\rrbracket_{i}\overset{\;\$,\mathsf{seed}_{i}}{\longleftarrow}\mathbb{F}_{q^{m\cdot\eta}}^{r}$
$\displaystyle\@pc@lb$ If $i\neq N$ $\displaystyle\@pc@lb$ $\diamond$ Sample
$(\llbracket\bm{x}\rrbracket_{i},\llbracket\bm{\beta}\rrbracket_{i},\llbracket
c\rrbracket_{i})\overset{\;\$,\mathsf{seed}_{i}}{\longleftarrow}PRG$
$\displaystyle\@pc@lb$ $\diamond$
${\mathsf{\vphantom{p}state}}_{i}=\mathsf{seed}_{i}$ $\displaystyle\@pc@lb$ If
$i=N$: $\displaystyle\@pc@lb$ $\diamond$ Sample
$\left(\llbracket\bm{x}\rrbracket_{N},\llbracket\bm{\beta}\rrbracket_{N},\llbracket\bm{a}\rrbracket_{N}\right)\overset{\;\$}{\longleftarrow}\mathbb{F}_{q}^{k}\times\mathbb{F}_{q^{m}}^{r}\times\mathbb{F}_{q^{m\cdot\eta}}^{r}$
$\displaystyle\@pc@lb$ $\diamond$
$\mathsf{aux}_{N}=\left(\llbracket\bm{x}\rrbracket_{N},\llbracket\bm{\beta}\rrbracket_{N},\llbracket\bm{a}\rrbracket_{N}\right)$
$\displaystyle\@pc@lb$ $\diamond$
${\mathsf{\vphantom{p}state}}_{N}=\Big{(}\mathsf{seed}_{N},\mathsf{aux}_{N}\Big{)}$
$\displaystyle\@pc@lb$ \- Simulate the computation of the party i to get
$\llbracket\bm{\alpha}\rrbracket_{i}$ and $\llbracket v\rrbracket_{i}$
$\displaystyle\@pc@lb$ 5\. For the party $i^{*}$: $\displaystyle\@pc@lb$ \-
$\llbracket\bm{\alpha}\rrbracket_{i^{*}}\overset{\;\$}{\longleftarrow}\mathbb{F}_{q^{m\cdot\eta}}^{r}$
$\displaystyle\@pc@lb$ \- $\llbracket v\rrbracket_{i^{*}}=-\sum_{i\neq
i^{*}}\llbracket v\rrbracket_{i}$ $\displaystyle\@pc@lb$ \-
$\mathsf{cmt}_{i^{*}}\overset{\;\$}{\longleftarrow}\\{0,1\\}^{\lambda}$
$\displaystyle\@pc@lb$ 6\. Compute the commitments:
$\mathsf{cmt}_{i}=\mathsf{Com}\big{(}{\mathsf{\vphantom{p}state}}_{i},\rho_{i}\big{)}$.
$\displaystyle\@pc@lb$ 7\. Compute the commitment:
$h_{0}=\mathsf{H}(\mathsf{cmt}_{1},\cdots,\mathsf{cmt}_{N})$.
$\displaystyle\@pc@lb[]$ 9\. For each main party $p\in[1,D]\times[1,2]$:
compute $\llbracket\bm{\alpha}^{\prime}\rrbracket_{p}$ and $\llbracket
v^{\prime}\rrbracket_{p}$ $\displaystyle\@pc@lb$ 10\. For each dimension
$k\in[1,D]$: compute
$H_{k}=\mathsf{H}\big{(}(\llbracket\bm{\alpha}^{\prime}\rrbracket_{(k,i)},\llbracket
v^{\prime}\rrbracket_{(k,i)})_{i\in[1,2]}\big{)}$ $\displaystyle\@pc@lb$ 11\.
Compute $h_{1}=\mathsf{H}(H_{1},...,H_{D})$ $\displaystyle\@pc@lb[]$ Step 3:
Output transcript $\displaystyle\@pc@lb$ 12\. The prover outputs the
transcript
$(h_{0},\mathsf{ch}_{1},\mathsf{rsp}_{1},\mathsf{ch}_{2},\mathsf{rsp}_{2})$,
where $\mathsf{rsp}_{1}=h_{1}$ and
$\mathsf{rsp}_{2}=((\mathsf{cmt}_{i^{*}}),\llbracket\bm{\alpha}^{\prime}\rrbracket_{i^{*}},({\mathsf{\vphantom{p}state}}_{j},\rho_{j})_{j\neq
i^{*}})$. If $i^{*}\neq N$, he also has to send
$\llbracket\bm{x}\rrbracket_{N},\llbracket\bm{\beta}\rrbracket_{N}$ and
$\llbracket c\rrbracket_{N}$. $\displaystyle\@pc@lb$

Figure 14: HVZK simulator of the PoK with additive sharing and hypercube
optimization

  * •

Simulator 0 (real world): it takes in input the witness $\bm{x}$ and the
challenges $\mathsf{ch}_{1}=\big{(}(\gamma_{j})_{j\in[1,n]},\epsilon\big{)}$
and $\mathsf{ch}_{2}=i^{*}$. It worrectly executes the algorithm 3, hence its
output is the correct distribution.

  * •

Simulator 1: Same as the Simulator 0, but uses true randomness instead of
seed-derived randomness for leaf $i^{*}$.
If $i^{*}=N$, the leafs
$\llbracket\bm{x}\rrbracket_{N},\llbracket\bm{\beta}\rrbracket_{N},\llbracket
c\rrbracket_{N}$ are computed as in the MPC protocol.
The pseudo-random generator is supposed to be ($t$,$\epsilon_{PRG}$)-secured,
its outputs are indistinguishable from the uniform distribution. Since the
principal parts correspond to the sum of a certain number of leaves whose
distributions are indistinguishable from that of the real worlds, their
distribution is also indistinguishable.

  * •

Simulator 2: Replace the leafs
$\llbracket\bm{x}\rrbracket_{N},\llbracket\bm{\beta}\rrbracket_{N},\llbracket
c\rrbracket_{N}$ in Simulator 1 by uniformly sampled values. Compute
$\llbracket v\rrbracket_{i^{*}}=-\sum_{i\neq i^{*}}\llbracket
v\rrbracket_{i}$. Note that this simulator becomes independent from the secret
witness $\bm{x}$.
If $i^{*}=N$, it only impacts the shares
$\llbracket\bm{\alpha}\rrbracket_{i^{*}}$ and $\llbracket
v\rrbracket_{i^{*}}$. Note that this change doesn’t alter the uniform
distribution of these values. It doesn’t alter the distribution of any other
leaf.
If $i^{*}\neq N$, it only impacts
$(\llbracket\bm{x}\rrbracket_{N},\llbracket\bm{\beta}\rrbracket_{N},\llbracket
c\rrbracket_{N})$ in the simulated response and the values computed from them
in the MPC protocol. It doesn’t alter the distribution of other leaves. We
observe that the shares in
$(\llbracket\bm{x}\rrbracket_{N},\llbracket\bm{\beta}\rrbracket_{N},\llbracket
c\rrbracket_{N})$ are calculated by adding a randomness value from each seed
of party $i\neq i^{*}$, which correspond to adding a uniform random value from
$\mathsf{seed}_{i^{*}}$. Since this distribution was uniform in Simulator 1,
the output distributions are the same. Remember that this does not change the
distributions of the main parts for the same reasons as before.

  * •

Simulator 3: Rather than computing the value of
$\llbracket\bm{\alpha}\rrbracket_{i^{*}}$ as in the MPC protocol, sample it
uniformly from $\mathbb{F}_{q^{m\cdot\eta}}^{r}$. As in the previous
simulator, it doesn’t change their output distribution.

As such, the output of the simulator is indistinguishable from the real
distribution.

####  5.1.2 Security Proofs for the Threshold Sharing Protocol

###### Theorem 5.2

The MinRank Proof of Knowledge protocol based on threshold secret sharing
described in Fig.10 has the following properties:

  * •

Completeness: A prover $\mathcal{P}$ who has the knowledge of a solution of a
MinRank instance will always be accepted by the verifier.

  * •

Soundness: Suppose that there is an efficient prover $\tilde{\mathcal{P}}$
that convinces the verifier to accept with probability

$\tilde{\epsilon}>\epsilon$

with

$\epsilon=\frac{1}{\binom{N}{\ell}}+p\cdot\frac{\ell\cdot(N-\ell)}{\ell+1}$

where $\epsilon$ is the soundness of the protocol in Fig.10, and $p$ is the
soundness of the MPC protocol used, i.e,
$\frac{2}{q^{m\eta}}-\frac{1}{q^{2m\eta}}$.
Then, there is an efficient probabilistic extraction algorithm $\mathcal{E}$
that, given a rewindable black-box access to $\tilde{\mathcal{P}}$, outputs
either a solution of the MinRank instance, or a commitment collision by making
a number of calls to $\tilde{\mathcal{P}}$ which is bounded by

$\frac{4}{\tilde{\epsilon}-\epsilon}\cdot\Big{(}1+\tilde{\epsilon}\cdot\frac{8\cdot(N-\ell)}{\tilde{\epsilon}-\epsilon}\Big{)}$

  * •

Honest-Verifier Zero-Knowledge: If the pseudo-random generator algorithm PRG
and the commitment $\mathsf{Com}$ are indistinguishable from the uniform
random distribution, then the algorithm 10 is Honest-Verifier Zero Knowledge.

###### Proof

Completeness:
By construction, if the prover has knowledge of a solution of the MinRank
instance, he will always be able to execute the protocol correctly, i.e, he
will always obtain $\bm{\alpha}$ such that $v=0$ when executing the MPC
protocol $\Pi^{\eta}$, this is obvious.

Soundness:

The proof is rather long and complex. For this proof, we refer to [FR22], who
proved this theorem for any MPC protocol and MPCitH protocol, as long as they
lie in their model. Our threshold protocol is an exact application of their
model. Hence, the proof of the above theorem is the same as the proof in
appendix D of [FR22].

Honest-Verifier Zero-Knowledge:

The proof is similar to what is done in the case of the additive sharing, and
holds by the $t$-privacy of the MPC protocol, as well as the hiding property
of the commitments. Moreover, a proof in the general case is done in [FR22,
Appendix C]. Since we are in their model of MPCitH, the proof applies here as
well.

###  5.2 Security proofs for the Signature Schemes

The proofs follow in large parts the proofs in [AMGH+22], [FJR22] and [FR22].

####  5.2.1 Security Analysis of MIRA-Additive

We need to prove that the signature scheme is EUF-CMA secure:

###### Theorem 5.3

Let the PRG used be $(t,\epsilon_{PRG})$-secure, and $\epsilon_{MR}$ the
advantage an adversary has over the MinRank problem. Consider
$\mathsf{H}_{0},\mathsf{H}_{1},\mathsf{H}_{2},\mathsf{H}_{3},\mathsf{H}_{4}$
behave as random oracles, with an output of $2\lambda$ bits. Then, if an
adversary makes $q_{i}$ queries to $\mathsf{H}_{i}$, $q_{S}$ queries to the
signing oracle, the probability for him to produce a forgery (EUF-CMA) for the
MIRA Additive Signature Scheme (Fig.8) is:

$\displaystyle\mathsf{Pr}[\mathsf{Forge}]\leq\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}}+\epsilon_{PRG}+\mathsf{Pr}[X+Y=\tau]+\epsilon_{MR}$

where $\tau$ is the number of rounds of the signature,
$p=\frac{1}{q^{m\eta}}+\left(1-\frac{1}{q^{m\eta}}\right)\frac{1}{q^{m\eta}}$,
$X=\operatorname{max}_{i\in[0,q_{2}]}\\{X_{i}\\}$ with
$X_{i}\sim\mathcal{B}(\tau,p)$, and
$Y=\operatorname{max}_{i\in[0,q_{4}]}\\{Y_{i}\\}$ with
$Y_{i}\sim\mathcal{B}(\tau-X,\frac{1}{N})$.

###### Proof

In this proof, we will adopt a game hopping strategy in order to find the
upper bound.
The first game will be the access to the standard signing oracle by the
adversary $\mathcal{A}$. We will then game hop in order to eliminate the cases
where collisions happen, and, through some other games, we will manage to find
an upper bound.
We note $\mathsf{Pr}_{i}[\mathsf{Forge}]$ the probability of forgery when
considering game $i$. The aim of the proof is to find an upper bound on
$\mathsf{Pr}_{1}[\mathsf{Forge}]$.

  * •

Game 1
This is the interaction between $\mathcal{A}$ and the real signature scheme.
$\mathsf{KeyGen}$ generates $(\bm{M}_{0},\dots,\bm{M}_{k},\bm{x})$ and
$\mathcal{A}$ receives $\bm{M}_{0},\dots,\bm{M}_{k}$. $\mathcal{A}$ can make
queries to each $\mathsf{H}_{i}$ independently, and can make signing queries.
At the end of the attack, $\mathcal{A}$ outputs a message/signature pair,
$(m,\sigma)$. The event $\mathsf{Forge}$ happens when $\sigma$ is a valid
signature of $m$ and no signature of $m$ has been queried to the signing
oracle.

  * •

Game 2
In this game, we add a condition to the success of the attacker. The condition
we add is that if there is a collision between outputs of $\mathsf{H}_{0}$, or
$\mathsf{H}_{1}$, or $\mathsf{H}_{3}$, then, the forgery isn’t valid.
The first step is to look at the number of times every $\mathsf{H}_{i}$ is
called when calling the signing oracle. For $\mathsf{H}_{0}$, we make
$\tau\cdot N$ queries. The signing oracle contains also $\tau$ calls to
$\mathsf{H}_{1}$, one to $\mathsf{H}_{2}$, $\tau\cdot D$ to $\mathsf{H}_{3}$,
and finally, a single one to $\mathsf{H}_{4}$.
The number of queries to $\mathsf{H}_{0}$ or $\mathsf{H}_{1}$ or
$\mathsf{H}_{3}$ is then bounded from above by $q+\tau\cdot N\cdot q_{S}$,
where $q_{i}$ is the number of queries made by $\mathcal{A}$ to
$\mathsf{H}_{i}$, $q=\operatorname{max}\\{q_{0},q_{1},q_{2},q_{3},q_{4}\\}$
(we take $q_{2}$ and $q_{4}$ as well for $q$ since we are giving an upper
bound), and $q_{S}$ is the number of queries to the signing oracle.
We can then have the following result (it comes simply from the probability to
have at least one collision with $q+\tau\cdot N\cdot q_{S}$ values):

$\left\lvert\mathsf{Pr}_{1}[\mathsf{Forge}]-\mathsf{Pr}_{2}[\mathsf{Forge}]\right\rvert\leq\frac{3\cdot(q+\tau\cdot
N\cdot q_{S})^{2}}{2\cdot 2^{2\lambda}}$

  * •

Game 3
The attacker now fails if the inputs to any of the $\mathsf{H}_{i}$ has
already appeared in a previous query. Wlog. the adversary does not make such a
query itself and, if it happens in a signing query, this means that (at least)
the salt randomly sampled by the signing oracle appears in a previous hash or
signing query. We can bound this event with:

$\displaystyle\left\lvert\mathsf{Pr}_{2}[\mathsf{Forge}]-\mathsf{Pr}_{3}[\mathsf{Forge}]\right\rvert$
$\displaystyle\leq\frac{q_{S}\cdot(q_{S}+q_{0}+q_{1}+q_{2}+q_{3}+q_{4})}{2^{2\lambda}}$
$\displaystyle\leq\frac{q_{S}\cdot(q_{S}+5\cdot q)}{2^{2\lambda}}$

  * •

Game 4
When beginning the signature of the message $m$, $h_{1}$ and $h_{2}$ are
sampled uniformly and expanded into
$(\gamma_{1}^{(e)},\dots,\gamma_{n}^{(e)},\epsilon^{(e)})_{e\in[1,\tau]}$, and
$({i^{*}}^{(e)})_{e\in[1,\tau]}$. The game proceeds as before, but now we
replace the queries to $\mathsf{H}_{2}$ and $\mathsf{H}_{4}$ by $h_{1}$ and
$h_{2}$. If a query to $\mathsf{H}_{2}$ or $\mathsf{H}_{4}$ was already made,
the attacker fails. However, this situation doesn’t happen as Game 3 would
fail before. Hence,

$\mathsf{Pr}_{4}[\mathsf{Forge}]=\mathsf{Pr}_{3}[\mathsf{Forge}]$

  * •

Game 5
To answer the signing queries, we now use the HVZK simulator built in the
previous proof, in order to generate the views of the open parties. By
security of the PRG, the difference with the previous game is:

$\displaystyle\left\lvert\mathsf{Pr}_{5}[\mathsf{Forge}]-\mathsf{Pr}_{4}[\mathsf{Forge}]\right\rvert$
$\displaystyle\leq\epsilon_{PRG}$

  * •

Game 6
Finally, we say that an execution $e^{*}$ of a query
$h_{2}=\mathsf{H}_{4}(m,\mathsf{salt},h_{1},\llbracket
H_{1}^{(e)}\rrbracket\dots\llbracket H_{D}^{(e)}\rrbracket_{e\in[1,\tau]})$
defines a good witness $\bm{x}$ if:
\- Each of the $H_{k}^{(e)}$ are the output of a query to $H_{3}$
\- $h_{1}$ is the output of a query to $\mathsf{H}_{2}$, i.e,

$h_{1}=\mathsf{H}_{2}(\mathsf{salt},m,h_{0}^{(1)},\dots,h_{0}^{(\tau)})$

\- Each $h_{0}^{(e)}$ is the output of a query to $\mathsf{H}_{1}$, i.e,

$h_{0}^{(e)}=\mathsf{H}_{1}(salt,e,\mathsf{cmt}_{1}^{(e)},\dots,\mathsf{cmt}_{N}^{(e)})$

-Each $\mathsf{cmt}_{i}^{(e)}$ is the output of a query to $\mathsf{H}_{0}$, i.e,

$\mathsf{cmt}_{i}^{(e)}=\mathsf{H}_{0}(\mathsf{salt},e,i,{\mathsf{\vphantom{p}state}}_{i}^{(e)})$

\- The vector $\bm{x}\in\mathbb{F}_{q}^{k}$ defined by states
$\\{{\mathsf{\vphantom{p}state}}_{i}\\}_{i\in[1,N]}$ is a correct witness,
i.e, $\bm{E}=\bm{M}_{0}+\sum_{i=1}^{k}\bm{M}_{i}x_{i}$ such that
$\operatorname{W}_{R}(\bm{E})\leq r$.
In case where such an execution happens, one can retrieve the correct witness
from the states $\\{{\mathsf{\vphantom{p}state}}_{i}\\}_{i\in[1,N]}$ and, as a
consequence, one can solve the MinRank instance. This means that
$\mathsf{Pr}_{6}[\mathsf{Solve}]\leq\epsilon_{MR}$.
Finally, we only need to look at the upper bound of
$\left\lvert\mathsf{Pr}_{6}[\mathsf{Forge}\cap\mathsf{\overline{Solve}}]\right\rvert$.
This probability is upper bounded by the value

$\mathsf{Pr}[X+Y=\tau]$

where $X=\operatorname{max}_{i\in[0,q_{2}]}\\{X_{i}\\}$ with
$X_{i}\sim\mathcal{B}(\tau,p)$,
$Y=\operatorname{max}_{i\in[0,q_{4}]}\\{Y_{i}\\}$ with
$Y_{i}\sim\mathcal{B}(\tau-X,\frac{1}{N})$.
We explain this bound below:

$\mathsf{Solve}$ doesn’t happen here, meaning that, to have a forgery after a
query to $\mathsf{H}_{4}$, $\mathcal{A}$ has no choice but to cheat either on
the first round or on the second one.

Cheating at the first round. For any query $Q_{2}$ to $\mathsf{H}_{2}$, we
call the output of this query $h_{1}$. For any query $Q_{2}$, if a false
positive appears in a round $e$ with this value of $h_{1}$, then we add this
round $e$ to the set we call $G_{2}(Q_{2},h_{1})$. This means that
$\mathsf{Pr}[e\in G_{2}(Q_{2},h_{1})\text{ }|\text{
}\mathsf{\overline{Solve}}]\leq
p=\frac{1}{q^{m\eta}}+\left(1-\frac{1}{q^{m\eta}}\right)\frac{1}{q^{m\eta}}$.
Since the response $h_{1}$ is uniformly sampled, each round $e$ has the same
probability to be in the set $G_{2}(Q_{2},h_{1})$. This means that
$\\#G_{2}(Q_{2},h_{1})$ follows the binomial distribution
$X_{Q_{2}}=\mathcal{B}(\tau,p)$. We can then define
$(Q_{2\text{best}},h_{1\text{best}})$ such that $\\#G_{2}(Q_{2},h_{1})$ is
maximized, i.e,

$\\#G_{2}(Q_{2\text{best}},h_{1\text{best}})\sim
X={\operatorname{max}\\{X_{Q_{2}}\\}}_{(Q_{2}\in\mathcal{Q}_{2})}$

Cheating at the second round. Now, we need to look at the cheating in the
second round, i.e, the queries to $\mathsf{H}_{4}$. We will note this query
$Q_{4}$, with the output of this query $h_{2}$. For the signature to be
accepted, we know that, if in a round, the prover sends a wrong value of
$h_{1}$, then he needs to cheat on exactly one leaf (it is already established
that is isn’t possible to cheat on less, or on more, than one leaf). He only
needs to cheat when the value of $h_{1}^{(e)}$ is wrong, i.e, he needs to
cheat for every round $e\notin G_{2}(Q_{2\text{best}},h_{1\text{best}})$.
Since every time he cheats, the probability to be detected is $\frac{1}{N}$,
it is easy to see the probability that the verification outputs ACCEPT is
upper bounded by
$\Big{(}\frac{1}{N}\Big{)}^{\tau-\\#G_{2}(Q_{2\text{best}},h_{1\text{best}})}$
The probability that the prover is accepted on one of the $q_{4}$ queries is
then upper bounded by
$1-\Bigg{(}1-\Big{(}\frac{1}{N}\Big{)}^{\tau-\tau_{1}}\Bigg{)}$ where
$\tau_{1}=\\#G_{2}(Q_{2\text{best}},h_{1\text{best}})$. By summing over all
values of $\tau_{1}$ possible, we have then the upper bound:

$\mathsf{Pr}_{6}[\mathsf{Forge}\cap\overline{\mathsf{Solve}}]\leq\mathsf{Pr}[X+Y=\tau]$

where $X$ is as before, and
$Y={\operatorname{max}\\{Y_{Q_{2}}\\}}_{(Q_{2}\in\mathcal{Q}_{2})}$ where the
$Y_{Q_{2}}$ are distributed following $\mathcal{B}(\tau-X,\frac{1}{N})$.

All that is left to do is then to compute the sum of all the upper bounds we
retrieved: this gives us the wanted result.

####  5.2.2 Security Analysis of MIRA-Threshold

###### Theorem 5.4

Let the PRG used be $(t,\epsilon_{PRG})$-secure, and $\epsilon_{MR}$ the
advantage an adversary has over the MinRank problem. Consider
$\mathsf{H}_{0},\mathsf{H}_{1},\mathsf{H}_{2}$ and $\mathsf{H}_{M}$ behave as
random oracles, with an output of $2\lambda$ bits ($\mathsf{H}_{M}$ is the
function used for the Merkle Tree). Then, if an adversary makes $q_{i}$
queries to $\mathsf{H}_{i}$, $q_{S}$ queries to the signing oracle, $q_{M}$
queries to $\mathsf{H}_{M}$, the probability for him to produce a forgery
(EUF-CMA) for the MIRA Threshold Signature Scheme (Fig.12) is:

$\displaystyle\mathsf{Pr}[\mathsf{Forge}]\leq\frac{(q+\tau\cdot(2\cdot
N-1)\cdot
q_{S})^{2}}{2^{2\lambda}}+\frac{q_{S}\cdot(q_{S}+3q)}{2^{2\lambda}}+\epsilon_{PRG}+\mathsf{Pr}[X+Y=\tau]+\epsilon_{MR}$

where $\tau$ is the number of rounds of the signature,
$p=\frac{1}{q^{m\eta}}+\left(1-\frac{1}{q^{m\eta}}\right)\frac{1}{q^{m\eta}}$,
$X=\operatorname{max}_{i\in[0,q_{1}]}\\{X_{i}\\}$ with
$X_{i}\sim\mathcal{B}(\tau,\binom{N}{\ell+1}\cdot p)$, and
$Y=\operatorname{max}_{i\in[0,q_{2}]}\\{Y_{i}\\}$ with
$Y_{i}\sim\mathcal{B}(\tau-X,\frac{1}{\binom{N}{\ell}})$.

###### Proof

In this proof, we will adopt a game hopping strategy in order to find the
upper bound.
The first game will be the access to the standard signing oracle by the
adversary $\mathcal{A}$. We will then game hop in order to eliminate the cases
where collisions happen, and, through some other games, we will manage to find
an upper bound.
We note $\mathsf{Pr}_{i}[\mathsf{Forge}]$ the probability of forgery when
considering game $i$. The aim of the proof is to find an upper bound on
$\mathsf{Pr}_{1}[\mathsf{Forge}]$.

  * •

Game 1
This is the interaction between $\mathcal{A}$ and the real signature scheme.
$\mathsf{KeyGen}$ generates $(\bm{M}_{0},\dots,\bm{M}_{k},\bm{x})$ and
$\mathcal{A}$ receives $\bm{M}_{0},\dots,\bm{M}_{k}$. $\mathcal{A}$ can make
queries to each $\mathsf{H}_{i}$ independently, and can make signing queries.
At the end of the attack, $\mathcal{A}$ outputs a message/signature pair,
$(m,\sigma)$. The event $\mathsf{Forge}$ happens when the message output by
$\mathcal{A}$ was not previously used in a query to the signing oracle.

  * •

Game 2
We add a condition to the success of the attacker now. If there is a collision
in the outputs of $\mathsf{H}_{0}$ or on $\mathsf{H}_{M}$, then the forgery
isn’t valid. Here, $\mathsf{H}_{0}$ is called $q_{0}$ times by $\mathcal{A}$,
$\mathsf{H}_{M}$ $q_{M}$ times. When $\mathcal{A}$ calls the signing oracle,
there are in total: $\tau\cdot N$ calls to $\mathsf{H}_{0}$, $\tau\cdot(2\cdot
N-1)$ calls to $\mathsf{H}_{M}$, and one to $\mathsf{H}_{1}$ and
$\mathsf{H}_{2}$. In this game, only $\mathsf{H}_{0}$ and $\mathsf{H}_{M}$ are
of interest, but for a simpler notation, we will take
$q=\operatorname{max}\\{q_{0},q_{1},q_{2},q_{M}\\}$ (as it is an upper bound
we are looking for, this is fine). We can then give an upper bound to the
queries made by $\mathcal{A}$ to the hash functions, which is then:
$q+\tau\cdot(2\cdot N-1)\cdot q_{S}$ where $q_{S}$ is the number of queries to
the signing oracle.
When making this many queries, we can now bound from above the probability of
having a collision, with

$\left\lvert\mathsf{Pr}_{1}[\mathsf{Forge}]-\mathsf{Pr}_{2}[\mathsf{Forge}]\right\rvert\leq\frac{(q+\tau\cdot(2\cdot
N-1)\cdot q_{S})^{2}}{2^{2\lambda}}$

  * •

Game 3
The attacker now fails if the inputs to any of the $\mathsf{H}_{i}$ has
already appeared in a previous query. Wlog. the adversary does not make such a
query itself and, if it happens in a signing query, this means that (at least)
the salt randomly sampled by the signing oracle appears in a previous hash or
signing query. Since we don’t use $\mathsf{salt}$ in the Merkle Tree, this
will only concern $\mathsf{H}_{0},\mathsf{H}_{1},\mathsf{H}_{2}$. We sample
$\mathsf{salt}$ $q_{S}$ time (once by signing oracle query), and $3\cdot q$
times as well (each time we call $\mathsf{H}_{0},\mathsf{H}_{1}$ or
$\mathsf{H}_{2}$). If there is an input which already appears for
$\mathsf{H}_{M}$, this must be because a collision has been found either on
$\mathsf{H}_{M}$ or on $\mathsf{H}_{0}$. However, we already excluded this in
Game 2. This means we can give the following bound:

$\displaystyle\left\lvert\mathsf{Pr}_{2}[\mathsf{Forge}]-\mathsf{Pr}_{3}[\mathsf{Forge}]\right\rvert$
$\displaystyle\leq\frac{q_{S}\cdot(q_{S}+q_{0}+q_{1}+q_{2})}{2^{2\lambda}}$
$\displaystyle\leq\frac{q_{S}\cdot(q_{S}+3\cdot q)}{2^{2\lambda}}$

  * •

Game 4
When beginning the signature of the message $m$, $h_{1}$ and $h_{2}$ are
sampled uniformly and expanded into
$\gamma_{1}^{(e)},\dots,\gamma_{n}^{(e)},\epsilon^{(e)}$, and ${i^{*}}^{(e)}$.
The game proceeds as before, but now we replace the queries to
$\mathsf{H}_{2}$ and $\mathsf{H}_{4}$ by $h_{1}$ and $h_{2}$. If a query to
$\mathsf{H}_{2}$ or $\mathsf{H}_{4}$ was already made, the attacker fails.
However, this situation doesn’t happen as Game 3 would fail before. Hence,

$\mathsf{Pr}_{4}[\mathsf{Forge}]=\mathsf{Pr}_{3}[\mathsf{Forge}]$

  * •

Game 5
To answer the signing queries, we now use the HVZK simulator built in the
previous proof, in order to generate the views of the open parties. By
security of the PRG, the difference with the previous game is:

$\displaystyle\left\lvert\mathsf{Pr}_{5}[\mathsf{Forge}]-\mathsf{Pr}_{4}[\mathsf{Forge}]\right\rvert$
$\displaystyle\leq\epsilon_{PRG}$

  * •

Game 6
Finally, we say that an execution $e^{*}$ of a query
$h_{2}=\mathsf{H}_{2}(m,\mathsf{pk},\mathsf{salt},h_{1},(\llbracket\bm{\alpha}^{(e)}\rrbracket_{i},\llbracket
v^{(e)}\rrbracket_{i})_{i\in S,e\in[1,\tau]})$ defines a good witness $\bm{x}$
if:
\- $h_{1}$ is the output of a query to $H_{1}$, i.e,

$h_{1}=\mathsf{H}_{1}(\mathsf{salt},m,h_{0}^{(1)},\dots,h_{0}^{(\tau)})$

\- Each $h_{0}^{(e)}$ is the output of a query to the MerkleTree oracle, i.e,

$h_{0}^{(e)}=\mathsf{Merkle}(\mathsf{cmt}_{1}^{(e)},\dots,\mathsf{cmt}_{N}^{(e)})$

-Each $\mathsf{cmt}_{i}^{(e)}$ is the output of a query to $\mathsf{H}_{0}$, i.e,

$\mathsf{cmt}_{i}^{(e)}=\mathsf{H}_{0}(\mathsf{salt},e,i,{\mathsf{\vphantom{p}state}}_{i}^{(e)})$

\- The vector $\bm{x}\in\mathbb{F}_{q}^{k}$ defined by states
$\\{{\mathsf{\vphantom{p}state}}_{i}\\}_{i\in[1,N]}$ is a correct witness,
i.e, $\bm{E}=\bm{M}_{0}+\sum_{i=1}^{k}\bm{M}_{i}x_{i}$ such that
$\operatorname{W}_{R}(\bm{E})\leq r$.
In case where such an execution happens, one can retrieve the correct witness
from the states $\\{{\mathsf{\vphantom{p}state}}_{i}\\}_{i\in[1,N]}$ and, as a
consequence, one can solve the MinRank instance. This means that
$\mathsf{Pr}_{6}[\mathsf{Solve}]\leq\epsilon_{MR}$.
Finally, we only need to look at the upper bound of
$\left\lvert\mathsf{Pr}_{6}[\mathsf{Forge}\cap\mathsf{\overline{Solve}}]\right\rvert$.
This probability is upper bounded by the value

$\mathsf{Pr}[X+Y=\tau]$

with $X=\operatorname{max}_{i\in[0,q_{1}]}\\{X_{i}\\}$ with
$X_{i}\sim\mathcal{B}(\tau,\binom{N}{\ell+1}\cdot p)$,
$Y=\operatorname{max}_{i\in[0,q_{2}]}\\{Y_{i}\\}$ with
$Y_{i}\sim\mathcal{B}(\tau-X,\frac{1}{\binom{N}{\ell}})$ and where
$p=\frac{1}{q^{m\eta}}+\left(1-\frac{1}{q^{m\eta}}\right)\frac{1}{q^{m\eta}}$.
This result comes directly from [FR22, Lemma 6 and Theorem 4, Appendix F].

All that is left to do is then to compute the sum of all the upper bounds we
retrieved: this gives us the wanted result.

##  6 Known Attacks

###  6.1 Attacks against Fiat-Shamir Signatures

There are several attacks against signatures from zero-knowledge proofs
obtained thanks to the Fiat-Shamir heuristic. [AABN02] proposes an attack more
efficient than brute force for protocols with more than one challenge, i.e.
for protocols of a minimum of 5 rounds.

Kales and Zaverucha proposed in [KZ20] a forgery attack which consists in
guessing separately the two challenges of the protocol. It results an additive
cost rather than the expected multiplicative cost. The cost to forge a valid
transcript for a 5-round proof of knowledge corresponds to the cost of the
optimal trade-off between the work needed to pass the first step and the work
needed to pass the second step. To run the attack, one can find the optimal