11institutetext:  Technology Innovation Institute, UAE 22institutetext:
Sorbonne Université, CNRS, INRIA, Institut de Mathématiques
de Jussieu-Paris Rive Gauche, Ouragan, Paris, France 33institutetext:
CryptoExperts, Paris, France 44institutetext: University of Limoges, France
55institutetext: CISPA, Helmholtz Center for Information Security, Saarbrücken

# RYDE: A Digital Signature Scheme based on Rank-Syndrome-Decoding Problem
with MPCitH Paradigm

Loïc Bidoux 11 Jesús-Javier Chi-Domínguez 11 Thibauld Feneuil 2 and 32 and 3
Philippe Gaborit 44 Antoine Joux 55 Matthieu Rivain 33 Adrien Vinçotte 44

###### Abstract

We present a signature scheme based on the Syndrome-Decoding problem in rank
metric. It is a construction from multi-party computation (MPC), using a MPC
protocol which is a slight improvement of the linearized-polynomial protocol
used in [Fen22], allowing to obtain a zero-knowledge proof thanks to the
MPCitH paradigm. We design two different zero-knowledge proofs exploiting this
paradigm: the first, which reaches the lower communication costs, relies on
additive secret sharing and uses the hypercube technique [AMGH+22]; and the
second relies on low-threshold linear secret sharing as proposed in [FR22].
These proofs of knowledge are transformed into signature schemes thanks to the
Fiat-Shamir heuristic [FS86], allows us to obtain signatures above 6kB. These
performances prompted us to propose this signature to the Post-Quantum
Cryptography Standardization process organized by NIST.

##  1 Introduction

Zero-Knowledge (ZK) Proofs of Knowledge (PoK) have become significant
cryptographic primitives thanks to their various applications. Such protocols
allow a party (the prover) to convince an other one (the verifier) that he
knows a secret information without reveal anything about it. ZK proofs are
useful in many contexts: they allow to construct identification schemes, they
can be turned in signature schemes thanks to the Fiat-Shamir transform [FS86]
or the Unruh transform [Unr14]. In recent years, many signatures have been
constructed using this approach, for example from Zero-knowledge proofs of
knowledge of the solution to an instance of the Syndrome Decoding problem
[Ste93], the Multivariate Quadratic problem [SSH11], or the Permuted Kernel
Problem [Sha90].

We propose here a code based signature scheme, whose security relies on the
difficulty to solve the syndrome decoding problem: for a random matrix
$\bm{H}\in\mathbb{F}_{q^{m}}^{(n-k)\times n}$ and a vector
$\bm{y}\in\mathbb{F}_{q^{m}}^{n-k}$, this problem asks to find a vector
$\bm{x}\in\mathbb{F}_{q^{m}}^{n}$ of small weight such that
$\bm{H}\bm{x}^{T}=\bm{y}$. This problem is known to be NP-hard and accepted as
secured for reasonable parameters.
We consider here the rank weight of $\bm{x}$, which is equal to the dimension
of the $\mathbb{F}_{q}$-linear subspace generated by its coefficients in
$\mathbb{F}_{q^{m}}$. The notion of error in this metric is completely
different from that of Hamming: counting the number of non-zero coordinates
induces a local notion of error, while determining the dimension of a vector
subspace generated by a set of coordinates implies having a general vision of
it. Beyond their use in cryptography, rank metric codes are therefore
effective in practice for correcting errors in the form of blocks.
A first proposition of PoK for Syndrome Decoding problem has be done by
[Ste93] in Hamming metric, but its soundness error, which corresponds to the
probability that a malicious prover convince the verifier that he knows the
witness of the Syndrome Decoding instance, is equal to $2/3$. Although by
repeating the protocol $\tau$ times the soundness equal to $(2/3)^{\tau}$ can
be arbitrary close to 0, it results from the high amount of information to
transmit a too long signature. His approach has been generalized within the
framework of the rank metric, and has given rise to numerous protocol
proposals, for example [GSZ11, FJR21, BG22]. Among these, some of which have a
soundness equal to $1/N$ for some parameter $N$ (the quantity of information
to be transmitted increases with N, but with a better trade-off).

A possible technique for design efficient Proofs of Knowledge is to use the
MPC-in-the-Head paradigm, introduced in [IKOS07], that relies on symmetric
primitives. The idea which will be improved by [KKW18], by using MPC in their
pre-processing model. This technique relies on the multi-party computation:
the prover emulates "in his head" an additive MPC protocol where all
information are split in $N$ shares. It commits all the emulated parties and
reveals the views of $N-1$ among them. The only way for a malicious prover to
cheat would be to do so on the unopened part only, which happen with
probability $1/N$. More recently, [AMGH+22] suggests structuring the additive
shares in a hypercube to improve the performances of MPC protocols. It is also
possible to construct signatures from threshold multi-party computation
[FJR22], which allows a gain in the speed of signature verification at the
cost of bigger signatures.
This framework has the advantage of being very general and can be adapted to
prove knowledge of the witness of an instance for any type of problem. For
example, the MPC-in-the-Head paradigm has been used to construct several
signatures, relying on various problems, submitted to the NIST for their post-
quantum standardization process: SDitH [AMGG+23] relies on the Syndrome
Decoding problem in Hamming metric, MIRA [ABB+23b] and MiRitH [ARZV+23] relies
on the Min-Rank problem, MQOM [FR23] and Biscuit [BKPV23] relies on the
Multivariate Quadratic problem (or a structured variant), and PERK [ABB+23a]
relies on the Permuted Kernel problem.

Contributions. We propose two complete signature schemes which adapt protocol
for Rank-Syndrome-Decoding using linearized polynomials described in [Fen22]
to the methods of hypercube [AMGH+22] and threshold MPC [FJR22], whose
adaptation isn’t straightforward. The performance of the first of these two
signatures surpasses those of all the others relying on Rank Syndrome Decoding
problem mentioned above: the hypercube optimization allows us to obtain an
efficient quantum-resistant signature whose size is below 6kB. These results
prompted us to propose this signature to the Post-Quantum Cryptography
Standardization process organized by NIST [ABB+23c]111All proposed signatures
can be found here: https://csrc.nist.gov/projects/pqc-dig-
sig/round-1-additional-signatures. The use of the threshold-MPC in the second
signature allows a gain in the speed of the verification algorithm. We also
provide complete security proofs of these two signature schemes.

Paper organization. In Section 2, we begin by defining all cryptographic and
mathematical notions necessary for understanding. In Section 3, we give a
high-level overview of the signature scheme (and leave low-level instructions
to the specifications document). In Section 4, we describe the chosen
parameters and their associated performances. In Section 5, we detail security
proofs of the schemes. In Section 6, we detail attacks against signatures
designed with the Fiat-Shamir transform and attacks against the Rank-Syndrome-
Decoding problem.

##  2 Preliminary notions

###  2.1 Notations and conventions

Let $A$ a randomized algorithm. We write $y\leftarrow A(x)$ the output of the
algorithm for the input $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 by $\mathbb{F}_{q}$ the finite field of order $q$. We use bold
letters to denote vectors and 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
$\mathsf{negl}(\lambda)$ while a polynomial function in $\lambda$ is denoted
$\mathsf{poly}(\lambda)$. We further use the notation
$\mathsf{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,\varepsilon)$-indistinguishable (where $t$ and $\varepsilon$ are
$\mathbb{N}\to\mathbb{R}$ functions) if, for any algorithm $\mathcal{A}$
running in time at most $t(\lambda)$ we have

$\big{|}\Pr[\mathcal{A}^{D_{\lambda}}()=1]-\Pr[\mathcal{A}^{E_{\lambda}}()=1]\big{|}\leq\varepsilon(\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 $\varepsilon\in\mathsf{negl}(\lambda)$
for every $t\in\mathsf{poly}(\lambda)$;

  * •

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

  * •

perfectly indistinguishable if $\varepsilon=0$ for every (unbounded) $t$.

###  2.2 Security notions

####  2.2.1 Digital signature schemes

We begin by remembering basic definitions and notions of security about
signature schemes.

######  Definition 1 (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}$, possibly probabilistic, which takes as
inputs a message $m$ to be signed 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$. Output $1$ indicate that the signature is considered as valid.

A correct signature scheme verifies 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 that
a signature which is correctly generated is always accepted (when using the
right keys).

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

######  Definition 2 (EUF-CMA)

We can define the following game $G_{\textsc{euf-cma}}$ where
${\mathsf{Sign}(\mathsf{\vphantom{p}sk},\cdot)}$ is an oracle that sign a
message $m^{*}$:
$\textsl{($\mathsf{\vphantom{p}pk}$,$\mathsf{\vphantom{p}sk}$)}\leftarrow\mathsf{KeyGen}()$
$(m,\sigma)\leftarrow\mathcal{A}^{Sign(\mathsf{\vphantom{p}sk},\cdot)}(\textsf{pk})$

returns $1$ if $\textsf{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 if, for every polynomial adversary
$\mathcal{A}$, $\mathsf{Pr}\big{(}G_{\textsc{euf-cma}}(\mathcal{A})=1\big{)}$
is negligible.

####  2.2.2 Commitment schemes

The security of the signature relies on a commitment scheme, which allows to
commit on a value while hiding it until a possible future opening. We consider
two properties: the commitment reveals no information about what is committed
(hiding property), and there is only one (computationally tractable) way to
open the commitment (binding property).

A commitment scheme takes as input any element $x$ (the value to commit) and a
random tape $\rho\in\\{0,1\\}^{\lambda}$. When the secret value $x$ is
revealed, the commitment $\mathsf{cmt}=\mathsf{Com}(x,\rho)$ can be verified
by revealing $\rho$, which prove that $x$ has not been modified in the
meantime.

######  Definition 3 (Hiding)

A commitment scheme $\mathsf{Com}$ is computationally hiding if, for every
$m_{0},m_{1}$, the distributions of

$\big{\\{}\mathsf{Com}(m_{0},\rho),\rho\overset{\;\$}{\longleftarrow}\\{0,1\\}^{\lambda}\big{\\}}\text{
and
}\big{\\{}\mathsf{Com}(m_{1},\rho),\rho\overset{\;\$}{\longleftarrow}\\{0,1\\}^{\lambda}\big{\\}}$

are computationally indistinguishable.

######  Definition 4 (Binding)

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

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

where $\mu$ is a negligible function.

####  2.2.3 Pseudo-random generators

######  Definition 5 (Pseudo-random Generators)

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

  * •

$\ell(\lambda)>\lambda$

  * •

The distributions $\\{G(s)|\>s\leftarrow\\{0,1\\}^{\lambda}\\}$ and
$\\{r\>|\>r\overset{\;\$}{\longleftarrow}\\{0,1\\}^{\ell(\lambda)}\\}$ are
$(t,\epsilon)$-indistinguishable

In our constructions, we need _puncturable pseudo-random functions_
(puncturable PRF). Such a primitive produces $N$ pseudo-random values and
provides a way to reveal all the values but one. A standard construction of
puncturable PRFs can be derived from the tree-based construction of [GGM86],
usually denoted as the GGM construction. The idea is to use a tree PRG in
which one uses a pseudorandom generator to expand a root seed into $N$
subseeds in a structured way. This can be illustrated quite easily with the
following figure:

$(seed_{\text{root}},\mathsf{salt})$ $(seed_{int_{1}},\mathsf{salt})$ $\qquad
seed_{1}\qquad$ $\qquad seed_{2}\qquad$ ($seed_{int_{2}},\mathsf{salt})$
$\qquad seed_{3}\qquad$ $\qquad seed_{4}\qquad$

Figure 1: Example of GGM tree of depth 2

where each intermediate seed generates two new seeds, and $\mathsf{salt}$ is a
random value in $\\{0,1\\}^{\lambda}$.

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}$ ($\mathsf{salt}$ being known). 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 as, in the additive-based MPCitH transformation we 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$. More generally, for a GGM tree with
$N$ leaves 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|})$ nodes.

####  2.2.4 Merkle trees

A collision-resistant hash function (that we 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}({\mathsf{Merkle}(v_{1}\dots
v_{\frac{N}{2}})}\|{\mathsf{Merkle}(v_{\frac{N}{2}+1}\dots v_{N})})\text{ if
}N>1\\\ \mathsf{H}_{M}(v_{1})\text{ if }N=1\\\ \end{cases}$ (1)

A Merkle Tree is a special case of vector commitment scheme allowing efficient
opening of a subset of the committed values $v_{i}$. 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. To proceed, we just need
to reveal the sibling paths of the $(v_{i})_{i\in I}$. Those paths are called
the authentication paths and are denoted $\mathsf{auth}((v_{1}\dots
v_{N}),I)$.

####  2.2.5 Zero-knowledge proofs of knowledge

We define here the concept of proof of knowledge, following [AFK21] notations.
Let $R$ 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
witness for a statement $x$ is $R(x)=\\{\omega\mid(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 6 (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}$ wants to convince
$\mathcal{V}$ that he knows $\omega$ such that $(x,\omega)\in R$.
Let us denote $\langle\mathcal{P}(x,\omega),\mathcal{V}(x)\rangle$ the
transcript between $\mathcal{P}$ and $\mathcal{V}$. A proof of knowledge must
be perfectly complete, i.e.:

$\mathsf{Pr}\big{(}\mathsf{Accept}\leftarrow\langle\mathcal{P}(x,\omega),\mathcal{V}(x)\rangle\big{)}=1$

If there exists a polynomial time prover $\tilde{\mathcal{P}}$ such that:

$\tilde{\epsilon}=\mathsf{Pr}\big{(}\mathsf{Accept}\leftarrow\langle\tilde{\mathcal{P}}(x),\mathcal{V}(x)\rangle\big{)}>\epsilon$

then there exists an algorithm $\mathcal{E}$, called extractor, which given
rewindable access to $\tilde{\mathcal{P}}$, outputs a valid witness
$\omega^{\prime}\in R(x)$ in polynomial time in terms of
$(\lambda,\frac{1}{\tilde{\epsilon}-\epsilon})$ with probability at least
$\frac{1}{2}$.

We now introduce the notion of honest-verifier zero-knowledge for a proof of
knowledge (PoK):

######  Definition 7 (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)$.

####  2.2.6 Fiat-Shamir transform

The Fiat-Shamir transform is a generic process allowing to transform an HVZK
proof of knowledge into a signature scheme. The main adaptation lies in the
removal of the interaction in the protocol: one needs to pull the challenges
in a pseudo-random (and verifiable) 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 see below that there is an effective attack against such
signatures and so, $\tau$ must be chosen carefully (not too small).

Let us describe this transformation for the case of a 5-round protocol. 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 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 from $h_{2}$ by using a XOF.

The signature $\sigma$ therefore consists of sending:

  * •

$\mathsf{salt}$ which allows to compute commitments and the Fiat-Shamir
hashes,

  * •

$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.3 MPC for proofs of knowledge

####  2.3.1 Multi-Party Computation

We recall here the formalism proposed by [FR22]. The sharing of a value $x$
into $N$ parties is denoted $(\llbracket x\rrbracket_{1},...,\llbracket
x\rrbracket_{N})$, where $\llbracket x\rrbracket_{i}$ is the share of index
$i$ for $i\in[1,N]$, and $\llbracket x\rrbracket_{J}=(\llbracket
x\rrbracket_{i})_{i\in J}$ is the subset of shares for $J\subset[1,N]$.

######  Definition 8 (Threshold LSSS)

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

Formally, a $(t,N)-$threshold LSSS is a pair of algorithms:

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

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

  * •

Correctness: for every $x\in\mathbb{F}$, $r\in R$ and $J\in[1,N]$ such that
$|J|=t$: let $\llbracket x\rrbracket=\mathsf{Share}(x,r)$. We have:

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

  * •

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\Big{\\{}\llbracket s_{0}\rrbracket_{I}\text{ }|\text{
}\genfrac{}{}{0.0pt}{0}{r\overset{\;\$}{\longleftarrow}R}{\text{ }\llbracket
s_{0}\rrbracket_{[1,N]}\longleftarrow\mathsf{Share}(s_{0},r)}\Big{\\}}\text{
and }\Big{\\{}\llbracket s_{1}\rrbracket_{I}\text{ }|\text{
}\genfrac{}{}{0.0pt}{0}{r\overset{\;\$}{\longleftarrow}R}{\text{ }\llbracket
s_{1}\rrbracket_{[1,N]}\longleftarrow\mathsf{Share}(s_{1},r)}\Big{\\}}$

are perfectly indistinguishable.

  * •

Linearity: for every $v,v^{\prime}\in\mathbb{F}^{t}$, $\alpha\in\mathbb{F}$
and subset $J\subset[1,N]$ of $t$ elements:

$\mathsf{Reconstruct}_{J}(\alpha
v+v^{\prime})=\alpha\mathsf{Reconstruct}_{J}(v)+\mathsf{Reconstruct}_{J}(v^{\prime})$

Below are the two specific secret sharing which are used in RYDE:

######  Definition 9 (Additive secret sharing)

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

$\mathsf{Share}:(s,(r_{1},...,r_{N-1}))\rightarrow\llbracket
s\rrbracket=\left(r_{1},...,r_{N-1},s-\sum_{i=1}^{N-1}r_{i}\right)$

The $\mathsf{Reconstruct}_{[1,N]}$ algorithm consists in computing the sum of
all the shares.

######  Definition 10 (Shamir’s secret sharing)

The Shamir’s secret sharing over a finite field $\mathbb{F}$ is an
$(\ell+1,N)$-threshold LSSS with $R=\mathbb{F}^{\ell}$. Let $e_{1},...,e_{N}$
be public distinct elements of $\mathbb{F}^{*}$. The $\mathsf{Share}$
algorithm is defined as follows:

  * •

Build a polynomial: $P(X)=s+\sum_{i=1}^{\ell}r_{i}X^{i}$

  * •

For each $i\in[1,N]$: compute $\llbracket s\rrbracket_{i}=P(e_{i})$

The $\mathsf{Reconstruct}_{J}$ algorithm consists in recovering $P$ with
polynomial interpolation from known evaluations $\llbracket
s\rrbracket_{J}=(P(e_{i}))_{i\in J}$. The reconstructed secret is then given
by the constant term $s$ of $P$.

A multi-party computation protocol is an interactive protocol involving
several parties whose objective is to jointly compute a function $f$ on the
share $\llbracket x\rrbracket$ they received at the begin of the protocol, so
that they each get a share of $\llbracket f(x)\rrbracket$ at the end of the
execution. In the restricted MPC model described in [FR22], at each step the
parties can perform one of the following actions:

  * •

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

  * •

Computing: since the sharing is linear, the parties can perform linear
transformations on the shared values.

  * •

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

For application of the MPCitH paradigm, this MPC protocol is only required to
be secure in the semi-honest setting: we suppose that all parties rightfully
perform their computation. The view of a party is made up of all the
information available to this party when executing the protocol: its input
shares and the messages it receives from other parties.

######  Proposition 1 ([FR22])

Given a $(\ell+1,N)$-threshold LSSS, the following property holds; 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\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).$

One deduces that 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}$ builds the Lagrange polynomial from
the known evaluations and outputs the image of each party’s point.

####  2.3.2 MPC-in-the-Head paradigm

The MPC-in-the-Head paradigm, introduced by [IKOS07], is a framework allowing
to convert a generic secure multi-party computation (MPC) protocol to a zero-
knowledge proof. Let us assume we have a $\ell$-private MPC protocol in which
$N$ parties $\mathcal{P}_{1},\ldots,\mathcal{P}_{N}$ securely and correctly
evaluate a function $f$ on a secret input $x$. The verifier asks the prover to
reveal the views of $\ell$ parties (which include input shares and
communications with other parties). In this construction, the zero-knowledge
property comes from the $\ell$-privacy of the MPC protocol.

In what follows, we assume that all the manipulated MPC protocols fit the
model decribed in [FR22]: they use $(\ell+1,N)$-threshold LSSS and only uses
the operations decribed in the previous subsection.

We want to build a zero-knowledge proof of knowledge of a witness for a
statement $x$ such that $(x,\omega)\in\mathcal{R}$. Assume that we have a MPC
protocol which evaluates a function $f$ on the witness $\omega$ and has the
security properties mentioned above. The protocol works as follows:

  * •

each party receives as input a share $\llbracket\omega\rrbracket_{i}$, where
$\llbracket\omega\rrbracket$ is a threshold LSSS sharing of $\omega$,

  * •

the function $f$ outputs ACCEPT if $(x,\omega)\in\mathcal{R}$, REJECT
otherwise,

  * •

the view of $\ell$ parties gives no information about the witness $\omega$.

In our case, the parties take as input a linear sharing
$\llbracket\omega\rrbracket$ of the secret $\omega$ (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 broadcast
values. One should note that in the case of additive sharing, a single party
needs to add a constant.

To build the zero-knowledge proof, the prover begins by building a sharing
$\llbracket\omega\rrbracket$ of $\omega$. The prover then simulates all the
parties of the protocol until the computation of $\llbracket
f(\omega)\rrbracket$ (which should correspond to a sharing of ACCEPT, since
the prover is supposed to be honest), and sends a commitment of each party’s
view. The verifier then chooses $\ell$ parties and asks the prover to reveal
their views. The verifier checks the computation of their commitments. Since
only $\ell$ parties have been opened, the revealed views give no information
about $\omega$.

A naive way for the prover to execute the protocol would be to simulate all
parties, but each party computes LSSS sharing of all involved elements. It
implies that for each $a$ in these elements, a sharing $\llbracket
a\rrbracket=(\llbracket a\rrbracket_{1},...,\llbracket a\rrbracket_{N})$
contains redundancy when $\ell<N-1$. One deduces that it is necessary to
perform the calculations of the associated MPC protocol for only a subset $S$
of $\ell+1$ out of $N$ parties, and commit them is enough to ensure the
soundness of the proof. When $\ell+1$ is small, emulating the MPC protocol is
cheap and leads to good overall performances: it is the high-level idea in
Threshold-MPCitH. This technique to save computation is not possible when we
use the additive sharing (since $\ell=N-1$). However, in the additive setting,
[AMGH+22] showed that the prover only need to emulate $1+\log_{2}N$ parties,
and not $N$.

####  2.3.3 Soundness

Consider a malicious prover who want to convince the verifier that he knows a
witness $\omega$ for the instance $x$ (although it does not). Two cases can
happen:

  * •

The challenge of the verifier are such that the protocol results in a false
positive,

  * •

The malicious prover cheats for some party $i\in[1,N]$ (and hence has
inconsistent view w.r.t. the commitments).

Feneuil and Rivain describe in [FR22] a strategy allowing a malicious prover
to convince the verifier with probability:

$\dfrac{1}{\binom{N}{\ell}}+p_{\eta}\>\dfrac{\ell\>(N-\ell)}{\ell+1}$

where $p_{\eta}$ is the false positive rate of the associated MPC protocol
(i.e. is the probability that the MPC protocol output ACCEPT even if
$(x,\omega)\not\in\mathcal{R}$). In the additive case ($\ell=N-1$), it leads
to a soundness error of

$\dfrac{1}{N}+p_{\eta}\>\left(1-\dfrac{1}{N}\right).$

###  2.4 Technical lemmas

We present here technical lemmas that are useful in following proofs. The
proofs of these lemmas can be found in the original references.

######  Lemma 1 (Splitting Lemma [PS00])

Let $A\subset X\times Y$ such that $\mathsf{Pr}[(x,y)\in A]\geq\epsilon$.
For any $\alpha<\epsilon$, 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:

  * •

$\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\dfrac{\alpha}{\epsilon}$

###  2.5 Mathematical background

####  2.5.1 $q$-polynomials

We begin by recalling here the main properties of finite fields. Let $q$ a
prime number and $m\in\mathbb{N}$. Remember that $\mathbb{F}_{q^{m}}$ is a
linear space over $\mathbb{F}_{q}$. The $q$-polynomials, introduced in
[Ore33], are very useful tools in finite vector spaces: in particular, they
allow to characterize linear subspaces.

######  Definition 11 (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}X^{q^{i}}p_{i}\qquad\text{with
}p_{i}\in\mathbb{F}_{q^{m}}$

###### Proposition 2

Let $P$ a $q$-polynomial in $\mathbb{F}_{q^{m}}[X]$,
$\alpha,\beta\in\mathbb{F}_{q}$, $x,y\in\mathbb{F}_{q^{m}}$. Then:

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

###### Proof

Comes directly from the linearity over $\mathbb{F}_{q}$ of the Frobenius
endomorphism: $x\rightarrow x^{q}$.

One can then define a linear subspace in $\mathbb{F}_{q^{m}}$ with a
$q$-polynomial.

###### Proposition 3

The set of roots of a non zero $q$-polynomial of degree $r$ is 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,
which allows to obtain the majoration of the 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 all
element in $E$ is a root of $P$.
$P$ is called the annihilator polynomial of $E$.

####  2.5.2 Rank metric

While the Hamming metric – which counts the number of nonzero coordinates of a
code word – is relevant in the case of a prime field (especially
$\mathbb{F}_{2}$), the rank metric relies on an extension field
$\mathbb{F}_{q^{m}}$.

###### Definition 12

Let $\bm{x}=(x_{1},...,x_{n})\in\mathbb{F}_{q^{m}}^{n}$, and
$\mathcal{B}=(b_{1},...,b_{m})$ an $\mathbb{F}_{q}$-basis of
$\mathbb{F}_{q^{m}}$. Each coordinate $x_{i}$ can be associated with a vector
$(x_{i,1},...,x_{i,m})\in\mathbb{F}_{q}^{m}$ such that:

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

The matrix $\bm{M}(\bm{x})=(x_{i,j})_{(i,j)\in[1,n]\times[1,n]}$ is called
matrix associated to the vector $\bm{x}$.
The rank weight is defined as: $W_{R}(\bm{x})=\mathsf{Rank}(\bm{M}(\bm{x}))$.
The distance between two vectors is given by:
$d(\bm{x},\bm{y})=W_{R}(\bm{x}-\bm{y})$.
The support of $\bm{x}$ is the linear subspace of $\mathbb{F}_{q^{m}}$
generated by its coordinates: $\mathsf{Supp}(\bm{x})=\langle
x_{1},...,x_{n}\rangle$

Remark: The rank weight and the support of a vector is independent of the
choice of the basis. On the other hand, the rank weight of $\bm{x}$ is
obviously equal to the dimension of its support.

It is clear that the metric takes on its full meaning in the case of field
extensions: if we were to place ourselves on a prime field, any non zero
vector would have weight exactly 1. It also follows that the rank metric is
less discriminating since increased by the Hamming weight.

The number of possible $r$-dimensional supports in $\mathbb{F}_{q^{m}}$ is
given by the gaussian binomial coefficient:

$\begin{bmatrix}m\\\
r\end{bmatrix}_{q}=\prod_{i=0}^{r-1}\dfrac{q^{m}-q^{i}}{q^{r}-q^{i}}$

One often use the following approximation: $\begin{bmatrix}m\\\
r\end{bmatrix}_{q}\approx q^{r(m-r)}$.

###  2.6 Rank Syndrome Decoding problem

We want to build a signature based on a standard difficult problem: the
syndrome decoding. However, rather than using the Hamming metric, we use here
the rank metric, which allows to build similar constructions, but with
different properties. We begin by recalling the fundamental definitions
inherent to coding theory.

###### Definition 13

A linear code $\mathcal{C}$ on a finite field $\mathbb{F}$ of dimension $k$
and length $n$ is a linear subspace of $\mathbb{F}^{n}$ of dimension $k$. The
elements in $\mathcal{C}$ are called the code words. One says that
$\mathcal{C}$ is a $[n,k]_{\mathbb{F}}$ code.

Two types of matrices can define a code:

###### Definition 14

Let $\mathcal{C}$ a $[n,k]_{\mathbb{F}}$ code. A matrix
$\bm{G}\in\mathbb{F}^{k\times n}$ is a generator matrix of $\mathcal{C}$ if
its rows form a basis of $\mathcal{C}$, or equivalently:

$\mathcal{C}=\\{\bm{m}\bm{G},\bm{m}\in\mathbb{F}^{k}\\}$

A matrix $\bm{H}\in\mathbb{F}^{(n-k)\times n}$ is a parity check matrix of
$\mathcal{C}$ if its rows form a basis of $\mathcal{C}^{\perp}$, or
equivalently:

$\mathcal{C}=\\{\bm{c}\in\mathbb{F}^{n},\bm{H}\bm{c}^{\intercal}=\bm{0}^{\intercal}\\}$

Remark: In order to lighten the notations, we often omit the transpose symbol
for the vertical vectors

As in the case of the Hamming metric with random codes, syndrome decoding is a
hard problem in the rank metric:

###### Definition 15

Let $\mathbb{F}_{q^{m}}$ be the finite field of size $q^{m}$. Let $(n,k,r)$ be
positive integers such that $k\leq n$. Let
$I\in\mathbb{F}_{q^{m}}^{(n-k)\times(n-k)}$ the identity matrix of dimension
$n-k$ on $\mathbb{F}_{q^{m}}$. The Rank Syndrom Decoding (Rank-SD) problem
with parameters $(q,m,n,k,r)$ is the following one:
Let $\bm{H}$, $\bm{x}$ and $\bm{y}$ such that:

  * •

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

  * •

$\bm{x}$ is uniformly sampled from
$\\{\bm{x}\in\mathbb{F}_{q^{m}}^{n},W_{R}(\bm{x})\leq r\\}$

  * •

$\bm{y}=\bm{H}\bm{x}$

From $(\bm{H},\bm{y})$, find $\bm{x}$.

Remark: Choosing the parity-check matrix $\bm{H}$ in standard form does not
decrease the hardness of the problem, because obtaining this form from a
random matrix can be done in polynomial time. As we see below, constraining
this form allows us to share only the first $k$ coordinates of $\bm{x}$.

As we see later, there are two main approaches to solve the Rank-SD problem.
The first one relies on combinatorial arguments: it consists in guessing the
support of the error. The second one relies on algebraic computations, which
consist in putting the problem into polynomial equations, then solving them
using a Gröbner basis algorithm.

##  3 Description of the signature scheme

Here we explain how to build our signature scheme from a MPC protocol checking
the solution of a Rank-SD instance. The MPC-in-the-Head paradigm allows us to
convert the protocol first into a zero-knowledge proof, then into a signature
scheme using the Fiat-Shamir transform.

###  3.1 MPC rank checking protocol

From the Proposition 4 in the previous section, one can deduce a polynomial
characterization of the rank of a vector: for all
$\bm{x}\in\mathbb{F}_{q^{m}}$, $W_{R}(\bm{x})\leq r$ if and only if there
exists a $q$-polynomial $L$ of $q$-degree $r$ such that for all $i\in[1,n]$:
$L(x_{i})=0$. The following MPC protocol is an optimization of the one
proposed in [Fen22].

We now describe a MPC protocol to check the maximum rank of a vector
$\bm{x}=(x_{1},...,x_{n})\in\mathbb{F}_{q^{m}}$. Let
$U=\mathsf{Supp}(\bm{x})=\langle x_{1},...,x_{n}\rangle$ the vector space
generated by its coordinates, and $L_{U}$ the annihilator polynomial of $U$:

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

$L_{U}$ is a $q$-polynomial, so it can be written as:

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

Since the support is defined up to multiplication by a constant, one can
always assume that it contains 1 (see [AMAB+20]) without impacting the
security of the scheme. So, we get that $1$ is a root of the linearized
polynomial $L_{U}$, we can consequently deduce a relation between its
coefficients, and send one fewer value. We can suppose that
$\bm{\beta}=(\beta_{1},...,\beta_{r-1})\in\mathbb{F}_{q^{m}}^{r-1}$ and
$\beta_{0}=-\sum_{i=1}^{r-1}\beta_{i}-1$.

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

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

If one of the $x_{i}$ is not a root of $L_{U}$, the equation above is
satisfied only with probability $\frac{1}{q^{m\eta}}$. We have

$\displaystyle\sum_{j=1}^{n}\gamma_{j}L(x_{j})$
$\displaystyle=\sum_{j=1}^{n}\gamma_{j}\left(\sum_{i=0}^{r-1}\beta_{i}x_{j}^{q^{i}}+x_{j}^{q^{r}}\right)$
$\displaystyle=\sum_{j=1}^{n}\gamma_{j}x_{j}^{q^{r}}+\sum_{i=0}^{r-1}\beta_{i}\cdot\sum_{j=1}^{n}\gamma_{j}x_{j}^{q^{i}}$
$\displaystyle=\sum_{j=1}^{n}\gamma_{j}x_{j}^{q^{r}}+\beta_{0}\sum_{j=1}^{n}\gamma_{j}x_{j}+\sum_{i=1}^{r-1}\beta_{i}\cdot\sum_{j=1}^{n}\gamma_{j}x_{j}^{q^{i}}$
$\displaystyle=\sum_{j=1}^{n}\gamma_{j}x_{j}^{q^{r}}+\Big{(}-\sum_{i=1}^{r-1}\beta_{i}-1\Big{)}\sum_{j=1}^{n}\gamma_{j}x_{j}+\sum_{i=1}^{r-1}\beta_{i}\cdot\sum_{j=1}^{n}\gamma_{j}x_{j}^{q^{i}}$
$\displaystyle=\sum_{j=1}^{n}\gamma_{j}x_{j}^{q^{r}}+\Big{(}-\sum_{i=1}^{r-1}\beta_{i}\Big{)}\sum_{j=1}^{n}\gamma_{j}x_{j}+\sum_{i=1}^{r-1}\beta_{i}\cdot\sum_{j=1}^{n}\gamma_{j}x_{j}^{q^{i}}-\sum_{j=1}^{n}\gamma_{j}x_{j}$
$\displaystyle=\sum_{j=1}^{n}\gamma_{j}(x_{j}^{q^{r}}-x_{j})+\sum_{i=1}^{r-1}\beta_{i}\cdot\sum_{j=1}^{n}\gamma_{j}(x_{j}^{q^{i}}-x_{j})$

Defining $z=-\sum_{j=1}^{n}\gamma_{j}(x_{j}^{q^{r}}-x_{j})$, and
$\omega_{i}=\sum_{j=1}^{n}\gamma_{j}(x_{j}^{q^{i}}-x_{j})$, proving the
equation is equivalent to proving that:

$z=\langle\beta,\omega\rangle$

with $\beta$ the vector of coefficients of $L_{U}$. This can be checked in the
same way as in the multiplication checking protocol from [BN20]. Therefore, it
is necessary to introduce a random vector
$\bm{a}\in\mathbb{F}_{q^{m\cdot\eta}}^{r}$ and
$c=-\langle\bm{\bm{\beta}},\bm{a}\rangle\in\mathbb{F}_{q^{m\cdot\eta}}$.

Since we consider a Rank-SD instance with $\bm{H}$ in standard form
$\bm{H}=(\bm{I}\,||\,\bm{H}^{\prime})$, the secret solution
$\bm{x}\in\mathbb{F}_{q^{m}}^{n}$ can be split it in two parts
$\bm{x}=(\bm{x}_{A}\parallel\bm{x}_{B})$ with
$\bm{x}_{A}\in\mathbb{F}_{q^{m}}^{k}$ and
$\bm{x}_{B}\in\mathbb{F}_{q^{m}}^{n-k}$, such that

$\bm{y}=\bm{H}\bm{x}~{}~{}~{}\Leftrightarrow~{}~{}~{}\bm{x}_{A}=\bm{y}-\bm{H}^{\prime}\bm{x}_{B}~{}.$

For a given instance, $(\bm{H},\bm{y})$, the secret solution can then be fully
(and linearly) recovered from $\bm{x}_{B}$ by
$\bm{x}=(\bm{y}-\bm{H}^{\prime}\bm{x}_{B}\parallel\bm{x}_{B})$.

The resulting MPC protocol, denoted $\Pi^{\eta}$, is presented in Figure 2. In
a high-level point of view, the difference between this MPC protocol and the
one described in [Fen22] comes from the fact that we assume that $1$ is in the
support of $x$ to save communication. However, this difference does not impact
the security analysis (i.e. the false-positive rate) of the protocol, see
below.

Public values. instances of a Rank-SD problem :
$\bm{H}=(I~{}\bm{H}^{\prime})\in\mathbb{F}_{q^{m}}^{(n-k)\times n}$ and
$\bm{y}\in\mathbb{F}_{q^{m}}^{n-k}$ $\displaystyle\@pc@lb$ Inputs. Each party
takes a share of $\llbracket\bm{x}_{B}\rrbracket$ where
$\bm{x}\in\mathbb{F}_{q^{m}}^{n}$. Let $U$ a $\mathbb{F}_{q}$-linear subspace
of $\mathbb{F}_{q^{m}}$ of dimension $r$ which contains $x_{1},\dots,x_{n}$
and has for annihilator polynomial $L=\prod_{u\in U}(X-u)$. Each party takes a
share of the following sharing as inputs : $\llbracket
L\rrbracket=\sum_{i=1}^{r-1}\llbracket\beta_{i}\rrbracket(X^{q^{i}}-X)+(X^{q^{r}}-X)$,
$\llbracket\bm{a}\rrbracket$ where $\bm{a}$ is uniformly sampled from
$\mathbb{F}_{q^{m\cdot\eta}}^{r-1}$ and $\llbracket c\rrbracket$ such that
$c=-\langle\bm{\bm{\beta}},\bm{a}\rangle$. $\displaystyle\@pc@lb[]$ MPC
Protocol : $\displaystyle\@pc@lb[]$ 1\. The parties sample uniformly random :
$(\gamma_{1},...,\gamma_{n},\varepsilon)\overset{\;\$}{\longleftarrow}\mathbb{F}_{q^{m\cdot\eta}}^{n+1}$.
$\displaystyle\@pc@lb$ 2\. The parties locally compute
$\llbracket\bm{x}_{A}\rrbracket=\bm{y}-\bm{H}^{\prime}\llbracket\bm{x}_{B}\rrbracket$
and
$\llbracket\bm{x}\rrbracket=(\llbracket\bm{x}_{A}\rrbracket\,||\,\llbracket\bm{x}_{B}\rrbracket)$.
$\displaystyle\@pc@lb$ 3\. The parties locally compute $\llbracket
z\rrbracket=-\sum_{j=1}^{n}\gamma_{j}\left(\llbracket
x_{j}\rrbracket^{q^{r}}-\llbracket x_{j}\rrbracket\right)$.
$\displaystyle\@pc@lb$ 4\. The parties locally compute for all $k$ from 1 to
$r-1$ :
$\llbracket\omega_{k}\rrbracket=\sum_{j=1}^{n}\gamma_{j}\left(\llbracket
x_{j}\rrbracket^{q^{k}}-\llbracket x_{j}\rrbracket\right)$.
$\displaystyle\@pc@lb$ 5\. The parties locally compute
$\llbracket\bm{\alpha}\rrbracket=\varepsilon\cdot\llbracket\bm{\omega}\rrbracket+\llbracket\bm{a}\rrbracket$.
$\displaystyle\@pc@lb$ 6\. The parties open $\bm{\alpha}$.
$\displaystyle\@pc@lb$ 7\. The parties locally compute $\llbracket
v\rrbracket=\varepsilon\cdot\llbracket
z\rrbracket-\langle\bm{\alpha},\llbracket\bm{\beta}\rrbracket\rangle-\llbracket
c\rrbracket$. $\displaystyle\@pc@lb$ 8\. The parties open $v$.
$\displaystyle\@pc@lb$

Figure 2: Protocol $\Pi^{\eta}$ : checking that an input is solution of an
instance of Rank-SD problem

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

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

###### Proof

The protocol takes place in two stages: from steps 1 to 4, it computes the
values $z$ and $\omega$. From step 5, it checks that
$z=\langle\bm{\beta},\bm{\omega}\rangle$. If $W_{R}(\bm{x})>r$, there exists
$k\in[1,n]$ such that $L(x_{k})\neq 0$.
There are two possibilities for the protocol to accept in this case:

  * •

either $\sum_{j=1}^{n}\gamma_{j}L(x_{j})=0$, which occurs with probability
$\frac{1}{q^{m\eta}}$;

  * •

or $z\neq\langle\bm{\beta},\bm{\omega}\rangle$ but the protocol still accepts,
which occurs with probability $\frac{1}{q^{m\eta}}$ (according to the false-
positive rate of the [BN20] multiplication checking protocol adapted for the
matrix setting, see [Fen22] for details).

Since these two events are independent, the false positive rate is:

$p_{\eta}=\frac{1}{q^{m\eta}}+\left(1-\frac{1}{q^{m\eta}}\right)\frac{1}{q^{m\eta}}\>\leq\>\frac{2}{q^{m\eta}}.$

###  3.2 Conversion to zero-knowledge proof optimized with the hypercube
technique

We start by presenting the main idea of a proof of knowledge optimized with
the hypercube technique as proposed by [AMGH+22]: sharing a secret in
$N=2^{D}$ additive shares, and arranging them in a geometrical structure. Let
us consider an hypercube of dimension $D$, each dimension having $2$ slots.
These $2^{D}$ shares are called “leaf parties”. They can be indexed in two
ways: either by an integer in $[1,2^{D}]$, or by a vector of coordinates
$(i_{1},...,i_{D})\in[1,2]^{D}$.

Since we use an additive secret sharing, one can intertwine several executions
where each party (what we call a “main party”) can be the sum of a subset of
leaves, such that these subsets form a partition of the leaves. We build here
$D$ intertwined protocols, and each of them has $2$ main parties. For each
dimension $d\in[1,D]$, each main share is the sum of the $2^{D-1}$ leaves
which have the same value for $i_{d}$. The main parties are indexed by
$(d,k)\in[1,D]\times[1,2]$.

The leaf parties are the first to be generated. The process is the same as in
the generation of additive shares in a standard MPCitH transformation: the
prover uses a GGM tree (as a puncturable pseudo-random function) to derive $N$
seeds from a root seed $\mathsf{seed}$. From the $i$th leaf seed, each party
$i\in[1,N-1]$ pseudo-randomly generates the input shares
$\llbracket\bm{x}_{B}\rrbracket_{i},\llbracket\bm{\beta}\rrbracket_{i},\llbracket\bm{a}\rrbracket_{i}$
and $\llbracket c\rrbracket_{i}$ (see Figure 2 for the definition of these
shares) . The last share for $i=N$ is computed such that we obtain a valid
secret sharing of the values (except for $\bm{a}$ which is random and
therefore can be sample from $\mathsf{seed}_{N}$). Then the prover can derive
the shares of the “main parties” by summing the shares according to the
partitions. For example, the share of $c$ of the main party $(1,k)$ is
$\sum_{i_{2},...,i_{D}}\llbracket c\rrbracket_{(k,i_{2},...,i_{D})}$, which is
the sum of the $2^{D-1}$ leaf shares such that $i_{1}=k$.

The resulting protocols are presented in Figure 3, Figure 4 and Figure 5.

Public data: An instance of a Rank-SD problem:
$\bm{H}=(I~{}\bm{H}^{\prime})\in\mathbb{F}_{q^{m}}^{(n-k)\times n}$ and
$\bm{y}\in\mathbb{F}_{q^{m}}^{n-k}$ $\displaystyle\@pc@lb$ The prover wants to
convince the verifier that he knows the solution
$\bm{x}\in\mathbb{F}_{q^{m}}^{n}$ of the instance, i.e. such that
$\bm{y}=\bm{H}\bm{x}$. $\displaystyle\@pc@lb[]$ Step 1: Commitment
$\displaystyle\@pc@lb$ 1\. The prover computes
$\bm{\beta}=(\bm{\beta}_{k})_{k\in[1,r-1]}\in\mathbb{F}_{q^{m}}^{r}$ the
coefficients of the annihilator q-polynomial $L(X)$ associated to $\bm{x}$
such that $L(X)=\prod_{u\in
U}(X-u)=(X^{q^{r}}-X)+\sum_{k=1}^{r-1}\bm{\beta}_{k}(X^{q^{k}}-X)$ and
$\forall j\in[1,n],L(\bm{x}_{j})=0$ $\displaystyle\@pc@lb$ 2\. The prover
samples a seed
$\mathsf{seed}\overset{\;\$}{\longleftarrow}\\{0,1\\}^{\lambda}$ and a random
salt $\mathsf{salt}\overset{\;\$}{\longleftarrow}\\{0,1\\}^{\lambda}$.
$\displaystyle\@pc@lb$ 3\. The prover expand $\mathsf{seed}$ recursively using
a GGM tree with $\mathsf{salt}$ to obtain $N$ leaves and seeds
$(\mathsf{seed}_{i^{\prime}},\rho_{i^{\prime}})$. $\displaystyle\@pc@lb$ 4\.
For each $i\in[1,N-1]$: $\displaystyle\@pc@lb$ \- The prover samples
$(\llbracket\bm{x}_{B}\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$ \- The prover samples
$\llbracket\bm{a}\rrbracket_{N}\overset{\;\$,\mathsf{seed}_{N}}{\longleftarrow}PRG$
$\displaystyle\@pc@lb$ \- The prover computes
$\llbracket\bm{x}_{B}\rrbracket_{N}=\bm{x}_{B}-\sum_{i=1}^{N-1}\llbracket\bm{x}_{B}\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}_{B}\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{)}$,
where $\rho_{i}$ is a random tape sampled in $\\{0,1\\}^{\lambda}$ from
$\mathsf{seed}_{i}$ for each $i\in[1,N]$. $\displaystyle\@pc@lb$ 7\. The
prover commits all the shares:
$h_{0}=\mathsf{H}(\mathsf{cmt}_{1},\cdots,\mathsf{cmt}_{N})$
$\displaystyle\@pc@lb$ 8\. The prover computes the main parties by summing all
the leaves associated. Indexing 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=(d,k)\in\\{(1,1),...(D,2)\\}$:
$\llbracket\bm{x}_{B}\rrbracket_{(d,k)}=\sum_{i:i_{d}=k}\llbracket\bm{x}_{B}\rrbracket_{i}$,
$\llbracket\bm{\beta}\rrbracket_{(d,k)}=\sum_{i:i_{d}=k}\llbracket\bm{\beta}\rrbracket_{i}$,
$\llbracket\bm{a}\rrbracket_{(d,k)}=\sum_{i:i_{d}=k}\llbracket\bm{a}\rrbracket_{i}$
and $\llbracket c\rrbracket_{(d,k)}=\sum_{i:i_{d}=k}\llbracket
c\rrbracket_{i}$. $\displaystyle\@pc@lb[]$ Step 2: First Challenge
$\displaystyle\@pc@lb$ 9\. The verifier randomly samples
$\big{(}(\gamma_{j})_{j\in[1,n]},\epsilon\big{)}\in\mathbb{F}_{q^{m\cdot\eta}}^{n}\times\mathbb{F}_{q^{m\cdot\eta}}$
and sends it to the prover. $\displaystyle\@pc@lb[]$ Step 3: First Response
$\displaystyle\@pc@lb$ 10\. For each dimension $d\in[1,D]$, the prover
executes the algorithm in Fig. 4 on the main parties of the current dimension:
$(d,1),(d,2)$. He computes $(\llbracket\bm{\alpha}\rrbracket,\llbracket
v\rrbracket,H_{d})\longleftarrow\text{Algorithm\ref{exec_pi}}(\big{(}P_{d},(\gamma_{j})_{j\in[1,n]},\epsilon\big{)}$
$\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 randomly samples
$i^{*}\in[1,N]$ and sends it to the prover. $\displaystyle\@pc@lb[]$ Step 4:
Second Response and verification $\displaystyle\@pc@lb$ 13\. The prover sends
to the verifier $\mathsf{cmt}_{i^{*}}$ and
$\llbracket\bm{\alpha}\rrbracket_{i^{*}}$; and the sibling path of the share
$i^{*}$ to retrieve $({\mathsf{\vphantom{p}state}}_{j},\rho_{j})_{j\neq
i^{*}}$. $\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
$d\in[1,D]$, the verifier runs the algorithm in Fig. 5 to get
$\llbracket\bm{\alpha}\rrbracket$, $\llbracket v\rrbracket$ and $H_{d}$. He
checks: $\displaystyle\@pc@lb$ \- $v=0$ for all the executions.
$\displaystyle\@pc@lb$ \- $\bm{\alpha}$ is the same for all $D$ main
executions. $\displaystyle\@pc@lb$

Figure 3: Protocol optimized with the hypercube technique

Inputs : A set of shares for the dimension $k$:
$(\llbracket\bm{x}_{B}\rrbracket,\llbracket\bm{\beta}\rrbracket,\llbracket\bm{a}\rrbracket,\llbracket
c\rrbracket)$ 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[1,N]$ :
$\displaystyle\@pc@lb$ \- Compute
$\llbracket\bm{x}_{A}\rrbracket_{i}=\bm{y}-\bm{H}^{\prime}\llbracket\bm{x}_{B}\rrbracket_{i}$
and
$\llbracket\bm{x}\rrbracket_{i}=(\llbracket\bm{x}_{A}\rrbracket_{i}\,||\,\llbracket\bm{x}_{B}\rrbracket_{i})$
$\displaystyle\@pc@lb$ \- $\llbracket
z\rrbracket_{i}=-\sum_{j=1}^{n}\gamma_{j}\left(\llbracket
x_{j}\rrbracket_{i}^{q^{r}}-\llbracket x_{j}\rrbracket_{i}\right)$
$\displaystyle\@pc@lb$ \- Compute
$\llbracket\omega_{k}\rrbracket=\sum_{j=1}^{n}\gamma_{j}\left(\llbracket
x_{j}\rrbracket^{q^{k}}-\llbracket x_{j}\rrbracket\right)$ for each
$k\in[1,r-1]$ $\displaystyle\@pc@lb$ \- Compute
$\llbracket\bm{\alpha}\rrbracket_{i}=\epsilon\cdot\llbracket\bm{w}\rrbracket_{i}+\llbracket\bm{a}\rrbracket_{i}$
and reveals $\bm{\alpha}$ $\displaystyle\@pc@lb$ \- Compute $\llbracket
v\rrbracket_{i}=\epsilon\cdot\llbracket
z\rrbracket_{i}-\langle\bm{\alpha},\llbracket\bm{\beta}\rrbracket_{i}\rangle-\llbracket
c\rrbracket_{i}$ $\displaystyle\@pc@lb$

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

Inputs: A leaf $i^{*}$ that one does not reveal, the main party shares
$\llbracket\bm{\alpha}\rrbracket$ and $\llbracket v\rrbracket$ on which the
hidden leaf $i^{*}$ depends on, all the other main parties shares
$(\llbracket\bm{x}_{B}\rrbracket,\llbracket\bm{\beta}\rrbracket,\llbracket\bm{a}\rrbracket,\llbracket
c\rrbracket)$. $\displaystyle\@pc@lb$ Outputs:
$\llbracket\bm{\alpha}\rrbracket,\llbracket v\rrbracket$ and a commitment $H$
of the execution $\displaystyle\@pc@lb[]$ For all the main parties:
$\displaystyle\@pc@lb$ If the party $p=(d,k)$ contains the leaf $i^{*}$, i.e.
$i^{*}_{d}=k$: $\displaystyle\@pc@lb$ Set $\llbracket v\rrbracket_{i^{*}}$
such that $v=0$ $\displaystyle\@pc@lb$ Else: $\displaystyle\@pc@lb$ Do the
same computations as in $\Pi^{\eta}$ to obtain the correct shares
$\llbracket\bm{\alpha}\rrbracket_{p}$ and $\llbracket v\rrbracket_{p}$
$\displaystyle\@pc@lb$

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

An important remark is that one could have chosen a number of main parties per
dimension $n\neq 2$. The size of the signature depends on $N=n^{D}$, but not
independently on $n$ and $D$. For example, choosing the MPC parameters
$(n,D)=(2,8)$ or $(n,D)=(4,4)$ have no impact on the signature size, since
$n^{D}=256$ in the both cases. However, it is in our interest to choose $n$ as
small as possible: this increase the number $D$ of interleaved MPC protocols,
but reduce the number of computations (which are much more expensive).
Consequently, we always choose $n=2$ and select different dimensions $D$.

On the other hand, it is not necessary to do computations on all the main
shares. Once one has done the calculations on the main parties on a dimension
$d\in[1,D]$, one knows the value of $\bm{\alpha}$ for the protocol. Therefore,
one can do the computations for only $n-1$ parties of protocols associated to
all other dimensions, since one can deduce the value of the last share. This
makes a total of only $n+(n-1)(D-1)$ computed parties, and choosing $n=2$
makes this value the smallest as possible with $N=n^{D}$ fixed. One obtains
that it is necessary to do computations for only $D+1$ main parties.

####  3.2.1 Application of the Fiat-Shamir transform

We deduce from the Fiat-Shamir transform a way to convert a proof of knowledge
to a signature scheme, by transforming the proof in a non-interactive
protocol. The signature scheme and its verification algorithm are depicted in
Figure 6 and Figure 7. 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 of seeds collision.

Inputs $\displaystyle\@pc@lb$ \- Secret key
$\mathsf{\vphantom{p}sk}=\bm{x}_{B}$ with
$\bm{x}=(\bm{x}_{A}\,||\,\bm{x}_{B})\in\mathbb{F}_{q^{m}}^{n}$ such that
$w_{R}\big{(}\bm{x}\big{)}=r$ $\displaystyle\@pc@lb$ \- Public key
$\mathsf{\vphantom{p}pk}=(\bm{H},\bm{y})$ with
$\bm{H}=(\bm{I}~{}\bm{H}^{\prime})\in\mathbb{F}_{q^{m}}^{(n-k)\times n}$ and
$\bm{y}\in\mathbb{F}_{q^{m}}^{n-k}$ such that $\bm{y}=\bm{H}\bm{x}$
$\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}=(\bm{\beta}_{k})_{k\in[1,r-1]}\in\mathbb{F}_{q^{m}}^{r}$ the
coefficients of the annihilator q-polynomial $L(X)$ associated to $\bm{x}$
such that $L(X)=\prod_{u\in
U}(X-u)=(X^{q^{r}}-X)+\sum_{k=1}^{r-1}\bm{\beta}_{k}(X^{q^{k}}-X)$ and
$\forall j\in[1,n],L(\bm{x}_{j})=0$ $\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 $\mathsf{seed}^{(e)}$ recursively using a GGM tree with $\mathsf{salt}$
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^{\prime}\neq N$ :
$\displaystyle\@pc@lb$ \- Sample
$(\llbracket\bm{x}_{B}^{(e)}\rrbracket_{i},\llbracket\bm{\beta}^{(e)}\rrbracket_{i},\llbracket\bm{a}^{(e)}\rrbracket_{i}\llbracket
c^{(e)}\rrbracket_{i})\overset{\;\$,\mathsf{seed}_{i}^{(e)}}{\longleftarrow}PRG$
where PRG is a pseudo-random generator $\displaystyle\@pc@lb$ \-
${\mathsf{\vphantom{p}state}}_{i}^{(e)}=\mathsf{seed}_{i}^{(e)}$
$\displaystyle\@pc@lb$ Else : $\displaystyle\@pc@lb$ \- Sample
$\llbracket\bm{a^{(e)}}\rrbracket_{N}\overset{\;\$,\mathsf{seed}_{N}^{(e)}}{\longleftarrow}PRG$
$\displaystyle\@pc@lb$ \- Compute
$\llbracket\bm{x}_{B}^{(e)}\rrbracket_{N}=\bm{x}_{B}^{(e)}-\sum_{i=1}^{N-1}\llbracket\bm{x}_{B}^{(e)}\rrbracket_{i}$,
$\llbracket\bm{\beta}^{(e)}\rrbracket_{N}=\bm{\beta}^{(e)}-\sum_{i=1}^{N-1}\llbracket\bm{\beta}^{(e)}\rrbracket_{i}$
and $\llbracket
c^{(e)}\rrbracket_{N}=-\langle\bm{\alpha}^{(e)},\bm{\beta}^{(e)}\rangle-\sum_{i=1}^{N-1}\llbracket
c^{(e)}\rrbracket_{i}$ $\displaystyle\@pc@lb$ \-
${\mathsf{\vphantom{p}state}}_{N}^{(e)}=(\mathsf{seed}_{N}^{(e)},\llbracket\bm{x}_{B}^{(e)}\rrbracket_{N},\llbracket\bm{\beta}^{(e)}\rrbracket_{N},\llbracket
c^{(e)}\rrbracket_{N})$ $\displaystyle\@pc@lb$ \- Compute
$\mathsf{cmt}_{i}^{(e)}=\mathsf{H}_{0}(\mathsf{salt},e,{\mathsf{\vphantom{p}state}}_{i}^{(e)})$
$\displaystyle\@pc@lb$ 4\. For all main party index
$p=(d,k)\in\\{(1,1),...(D,2)\\}$ :
$\llbracket\bm{x}_{B}^{(e)}\rrbracket_{(d,k)}=\sum_{i:i_{d}=k}\llbracket\bm{x}_{B}^{(e)}\rrbracket_{i}$,
$\llbracket\bm{\beta}^{(e)}\rrbracket_{(d,k)}=\sum_{i:i_{d}=k}\llbracket\bm{\beta}^{(e)}\rrbracket_{i}$,
$\llbracket\bm{a}^{(e)}\rrbracket_{(d,k)}=\sum_{i:i_{d}=k}\llbracket\bm{a}^{(e)}\rrbracket_{i}$
and $\llbracket c^{(e)}\rrbracket_{(d,k)}=\sum_{i:i_{d}=k}\llbracket
c^{(e)}\rrbracket_{i}$. $\displaystyle\@pc@lb$ 5\. Commit all the shares :
$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\.
Extend hash
$\big{(}(\gamma^{(e)}_{j})_{j\in[1,n]},\epsilon^{(e)}\big{)}_{e\in[1,\tau]}\leftarrow
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. 4 to
obtain $\llbracket\bm{\alpha}^{(e)}\rrbracket$, $\llbracket v^{(e)}\rrbracket$
and $H_{k}^{(e)}$ $\displaystyle\@pc@lb$ 9\. Compute
$h_{2}=\mathsf{H}_{4}(m,\mathsf{\vphantom{p}pk},\mathsf{salt},h_{1},(H_{1}^{(e)},...,H_{D}^{(e)})_{e\in[1,\tau]})$
$\displaystyle\@pc@lb[]$ Step 4: Second Challenge $\displaystyle\@pc@lb$ 10\.
Extend hash $(i^{*(e)})_{e\in[1,\tau]}\leftarrow PRG(h_{2})$ with
$i^{*(e)}\in[1,N]$ $\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})_{j\neq
i^{*}},\mathsf{cmt}_{i^{*(e)}},\llbracket\alpha^{(e)}\rrbracket_{i*^{(e)}}\right)$
$\displaystyle\@pc@lb$

Figure 6: Rank-SD Signature Scheme based on Hypercube MPCitH - Signature
Algorithm

Inputs $\displaystyle\@pc@lb$ \- Public key
$\mathsf{\vphantom{p}pk}=(\bm{H},\bm{y})$ with
$\bm{H}=(\bm{I}~{}\bm{H}^{\prime})\in\mathbb{F}_{q^{m}}^{(n-k)\times n}$ and
$\bm{y}\in\mathbb{F}_{q^{m}}^{n-k}$ such that $\bm{y}=\bm{H}\bm{x}$
$\displaystyle\@pc@lb$ \- Message $m\in\\{0,1\\}^{*}$ $\displaystyle\@pc@lb$
\- Signature
$\sigma=(\mathsf{salt},h_{1},h_{2},(\mathsf{rsp}^{(e)})_{e\in[1,\tau]})$,
where $\mathsf{rsp}^{(e)}=\left(({\mathsf{\vphantom{p}state}}_{j})_{j\neq
i^{*}},\mathsf{cmt}_{i^{*(e)}},\llbracket\alpha^{(e)}\rrbracket_{i^{*(e)}}\right)$
$\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{\;\$,h_{1}}{\longleftarrow}(\mathbb{F}_{q^{m\cdot\eta}}^{n}\times\mathbb{F}_{q^{m\cdot\eta}})^{\tau}$
$\displaystyle\@pc@lb$ 2\. Sample
$i^{*(e)}\overset{\;\$,h_{2}}{\longleftarrow}[1,N]$ $\displaystyle\@pc@lb$ 3\.
Read $({\mathsf{\vphantom{p}state}}_{i}^{(e)})_{i\in[1,N]})$ for each
iteration $e\in[1,\tau]$. $\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$
$\mathsf{cmt}_{i^{*}}^{(e)}=\mathsf{H}_{0}(\mathsf{salt},e,{\mathsf{\vphantom{p}state}}_{i^{*}}^{(e)})$
$\displaystyle\@pc@lb$
$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(m,\mathsf{salt},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$ on main parties $\displaystyle\@pc@lb$ \- For each dimension
$k\in[1,D]$ : $\displaystyle\@pc@lb$ Run the algorithm in Fig. 5 to get
$\bar{H_{k}^{(e)}}$ $\displaystyle\@pc@lb$ 7\. Compute
$\bar{h}_{2}=\mathsf{H}_{4}\left(m,\mathsf{\vphantom{p}pk},\mathsf{salt},\bar{h}_{1},\left(\overline{H_{1}^{(e)}},...,\overline{H_{D}^{(e)}}\right)_{e\in[1,\tau]}\right)$
$\displaystyle\@pc@lb[]$ Step 4: Verify signature $\displaystyle\@pc@lb$

Figure 7: Rank-SD based signature scheme - Verification algorithm

Remark: At the step 11 of the signature scheme, sending the state of all
shares $j\neq i^{*}$ consists on:

  * •

If $i^{*}=N$, sending the sibling path associated to the share $N$;

  * •

If $i^{*}\neq N$, sending the sibling path associated to the share $i^{*}$ and
the shares $\llbracket\bm{x}_{B}^{(e)}\rrbracket_{N}$,
$\llbracket\bm{\beta}^{(e)}\rrbracket_{N}$ and $\llbracket
c^{(e)}\rrbracket_{N}$ to recover all the states $j\neq i^{*}$.

We show in Section 5.2 that this scheme guarantees good security against EUF-
CMA attacks.

###  3.3 Conversion to zero-knowledge proof using low-threshold linear secret
sharing

####  3.3.1 Application of the MPCitH paradigm

We explain below that the MPC-in-the-Head paradigm is a framework allowing to
convert an MPC protocol with threshold linear secret sharing to a zero-
knowledge proof. Like in the subsection 3.2, the explanations given below are
correct only within the framework of the restricted model [FR22]. The
principle of the process is that the prover emulates in his head the parties,
and the verifier asks to the prover to reveal the views of $\ell$ parties out
of $N$ (which includes shares and communications with other parties). It
ensures the zero-knowledge property as long as the underlying MPC protocol
relies on a $(\ell+1,N)$-threshold secret sharing.

To build such a proof, the prover begins by computing a sharing
$\llbracket\omega\rrbracket$ of the witness $\omega$, solution of the Rank
Syndrome-Decoding instance. The prover then simulates all the parties of the
protocol until the computation of $\llbracket f(\omega)\rrbracket$ (which
should correspond to a sharing of ACCEPT, since the prover is supposed to be
honest), and sends a commitment of each party’s view to show good faith. The
verifier then chooses $\ell$ parties and asks to the prover to reveal their
views. The verifier checks the computation of the their commitments. Since
only $\ell$ parties have been opened, the revealed views give no information
about $\omega$.

A naive way for the prover to execute the protocol would be to simulate all
parties, but each party computes LSSS sharing of all involved elements. It
implies that for each $x$ in these elements, a sharing $\llbracket
x\rrbracket=(\llbracket x\rrbracket_{1},...,\llbracket x\rrbracket_{N})$
contains redundancy. One deduces that it is necessary to perform the
calculations of the associated MPC protocol for only a subset $S$ of $\ell+1$
out of $N$ parties, and commit them is enough to ensure the soundness of the
proof. The threshold protocol therefore ensures better performances for the
simulation of the MPC protocol than the additive case (especially when $\ell$
is small compared to $n$), since it is not necessary to compute all the
parties.

Remark: This advantage on the full execution of the signing algorithm is
partially mitigated by the performances of the symmetric cryptography
primitives involved in the protocol. Threshold-MPCitH has better performances
on the pseudo-random generation, but the commitment is faster (for the prover)
with additive sharing. See [FR22] for more details.

The protocol resulting from these considerations can be found in Figure 8.

Public data : An instance of a Rank-SD problem :
$\bm{H}=(I~{}\bm{H}^{\prime})\in\mathbb{F}_{q^{m}}^{(n-k)\times n}$ and
$\bm{y}\in\mathbb{F}_{q^{m}}^{n-k}$ $\displaystyle\@pc@lb$ The prover wants to
convince the verifier that he knows the solution
$\bm{x}\in\mathbb{F}_{q^{m}}^{n}$ of the instance, i.e. such that
$\bm{y}=\bm{H}\bm{x}$ $\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}_{B}$. The prover also build
shares of the annihilator polynomial $L=\prod_{u\in
U}(X-u)=X^{q^{r}}+\sum_{i=0}^{r-1}\beta_{i}X^{q^{i}}$, 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$ For each $i\in[1,N]$ :
${\mathsf{\vphantom{p}state}}_{i}=(\llbracket\bm{x}_{B}\rrbracket_{i},\llbracket\bm{\beta}\rrbracket_{i},\llbracket\bm{a}\rrbracket_{i},\llbracket
c\rrbracket_{i})$ $\displaystyle\@pc@lb$ 2\. The prover computes the
commitments :
$\mathsf{cmt}_{i}=\mathsf{Com}\big{(}{\mathsf{\vphantom{p}state}}_{i},\rho_{i}\big{)}$,
where $\rho_{i}$ is a random tape sampled from $\\{0,1\\}^{\lambda}$ for each
$i\in[1,N]$. $\displaystyle\@pc@lb$ 3\. 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$ 4\.
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$ 5\. The prover chooses a public subset $S$ of parties
such that $|S|=\ell+1$: $\displaystyle\@pc@lb$ For each party $i\in S$ :
$\displaystyle\@pc@lb$ \- Compute
$\llbracket\bm{x}_{A}\rrbracket_{i}=\bm{y}-\bm{H}^{\prime}\llbracket\bm{x}_{B}\rrbracket_{i}$
and
$\llbracket\bm{x}\rrbracket_{i}=(\llbracket\bm{x}_{A}\rrbracket_{i}\,||\,\llbracket\bm{x}_{B}\rrbracket_{i})$
$\displaystyle\@pc@lb$ \- Compute $\llbracket
z\rrbracket=-\sum_{j=1}^{n}\gamma_{j}\left(\llbracket
x_{j}\rrbracket^{q^{r}}-\llbracket x_{j}\rrbracket\right)$.
$\displaystyle\@pc@lb$ \- Compute for each $k$ from 1 to $r-1$ :
$\llbracket\omega_{k}\rrbracket=\sum_{j=1}^{n}\gamma_{j}\left(\llbracket
x_{j}\rrbracket^{q^{k}}-\llbracket x_{j}\rrbracket\right)$
$\displaystyle\@pc@lb$ \- Compute
$\llbracket\bm{\alpha}\rrbracket_{i}=\epsilon\cdot\llbracket\bm{w}\rrbracket_{i}+\llbracket\bm{a}\rrbracket_{i}$
and the parties reveals $\bm{\alpha}$ $\displaystyle\@pc@lb$ \- Compute
$\llbracket v\rrbracket_{i}=\epsilon\cdot\llbracket
z\rrbracket_{i}-\langle\bm{\alpha},\llbracket\bm{\beta}\rrbracket_{i}\rangle-\llbracket
c\rrbracket_{i}$ $\displaystyle\@pc@lb$ 6\. The prover commits the values :
$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$ 7\. 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$ 8\.
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$ 9\. The prover chooses a public party $i^{*}\in
S\backslash I$, and sends $\llbracket\bm{\alpha}\rrbracket_{i^{*}}$ to allow
the verifier to recover
$\llbracket\bm{\alpha}\rrbracket=\mathsf{Reconstruct}_{I\bigcup\\{i^{*}\\}}(\llbracket\bm{\alpha}\rrbracket_{I\bigcup\\{i^{*}\\}})$
$\displaystyle\@pc@lb$ 10\. The verifier sets $\llbracket v\rrbracket_{i^{*}}$
such that $v=0$. $\displaystyle\@pc@lb$ 11\. The computes
$\tilde{h}_{1}=\mathsf{H}((\llbracket\bm{\alpha}\rrbracket_{i},\llbracket
v\rrbracket_{i})_{i\in S})$. $\displaystyle\@pc@lb$

Figure 8: Zero-knowledge protocol, deduced from the MPC protocol with
threshold

####  3.3.2 Digital signature scheme from Rank-SD problem

In this section, one applies the Fiat-Shamir transformation to the previous
interactive zero-knowledge proof in order to obtain a signature scheme. One
transforms the zero-knowledge proof into a non-interactive protocol by
deterministically sampling challenges thanks to a hash function. It must be
run several times to achieve the desired level of security.

The resulting signature scheme is depicted in the Figure 9.

Inputs $\displaystyle\@pc@lb$ \- Secret key $\mathsf{\vphantom{p}sk}=(\bm{x})$
with $\bm{x}=(\bm{x}_{A}\,||\,\bm{x}_{B})\in\mathbb{F}_{q^{m}}^{n}$ such that
$w_{R}\big{(}\bm{x}\big{)}=r$ $\displaystyle\@pc@lb$ \- Public key
$\mathsf{\vphantom{p}pk}=(\bm{H},\bm{y})$ with
$\bm{H}=(\bm{I}~{}\bm{H}^{\prime})\in\mathbb{F}_{q^{m}}^{(n-k)\times n}$ and
$\bm{y}\in\mathbb{F}_{q^{m}}^{n-k}$ such that $\bm{y}=\bm{H}\bm{x}$
$\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}=(\bm{\beta}_{k})_{k\in[1,r-1]}\in\mathbb{F}_{q^{m}}^{r}$ the
coefficients of the annihilator q-polynomial $L(X)$ associated to $\bm{x}$
such that $L(X)=\prod_{u\in
U}(X-u)=X^{q^{r}}+\sum_{k=1}^{r-1}\bm{\beta}_{k}(X^{q^{k}}-X)$ and $\forall
j\in[1,n],L(\bm{x}_{j})=0$ $\displaystyle\@pc@lb$ 3\. For each iteration
$e\in[1,\tau]$: $\displaystyle\@pc@lb$ $\diamond$ 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$
$\diamond$ For each party $i\in[1,N]$: $\displaystyle\@pc@lb$ \- Compute the
$(\ell+1,N)$-threshold LSSS
$\llbracket\bm{x}_{B}^{(e)}\rrbracket,\llbracket\bm{\beta}^{(e)}\rrbracket,\llbracket\bm{a}^{(e)}\rrbracket,\llbracket
c^{(e)}\rrbracket$ of $\bm{x}_{B},\bm{\beta},\bm{a}^{(e)}$ and $c^{(e)}$
$\displaystyle\@pc@lb$ \- Compute
${\mathsf{\vphantom{p}state}}^{(e)}_{i}=(\llbracket\bm{x}^{(e)}_{B}\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$ $\diamond$ 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\.
Extend hash
$\big{(}(\gamma^{(e)}_{j})_{j\in[1,n]},\epsilon^{(e)}\big{)}_{e\in[1,\tau]}\leftarrow
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$ $\diamond$ For each
party $i\in S$ with $S$ a public subset of parties such that $|S|=\ell+1$:
$\displaystyle\@pc@lb$ \- Compute
$\llbracket\bm{x}_{A}^{(e)}\rrbracket_{i}=\bm{y}-\bm{H}^{\prime}\llbracket\bm{x}_{B}^{(e)}\rrbracket_{i}$
and
$\llbracket\bm{x}^{(e)}\rrbracket_{i}=(\llbracket\bm{x}_{A}^{(e)}\rrbracket_{i}\,||\,\llbracket\bm{x}_{B}^{(e)}\rrbracket_{i})$
$\displaystyle\@pc@lb$ \- Compute $\llbracket
z^{(e)}\rrbracket_{i}=-\sum\nolimits_{j=1}^{n}\gamma_{j}\left(\llbracket
x_{j}^{(e)}\rrbracket_{i}^{q^{r}}-\llbracket x_{j}^{(e)}\rrbracket_{i}\right)$
and $\forall k\in[1,r-1],\llbracket
w_{k}^{(e)}\rrbracket_{i}=\sum\nolimits_{j=1}^{n}\left(\gamma_{j}\llbracket
x_{j}^{(e)}\rrbracket_{i}^{q^{k}}-\llbracket x_{j}^{(e)}\rrbracket_{i}\right)$
$\displaystyle\@pc@lb$ \- 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$ \- Compute $\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\. Extend hash
$(I^{(e)})_{e\in[1,\tau]}\leftarrow PRG(h_{2})$ where $(\\{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$ $\diamond$ Choose deterministically a party
$i^{*(e)}\in S\,\backslash\,I^{(e)}$ and compute
$\llbracket\bm{\alpha}^{(e)}\rrbracket_{i^{*(e)}}$ $\displaystyle\@pc@lb$
$\diamond$ 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$ $\diamond$ Compute
$\mathsf{rsp}^{(e)}=\big{(}(\llbracket\bm{x}^{(e)}_{B}\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 9: Rank based signature scheme with threshold - Signing algorithm

An entity that wants to verify the signature must then recompute the
challenges using the hashes $h_{1}$ and $h_{2}$ provided in the signature. For
each iteration $e\in[1,\tau]$, the prover sends $\mathsf{rsp}^{(e)}$, which
includes all the shares belonging to the parties in $I$, and
$\llbracket\bm{\alpha}^{(e)}\rrbracket_{i^{*(e)}}$ which allows to recompute
$\bm{\alpha}^{(e)}$. As a result, this information is sufficient for the
verifier to check the hashes. Since hash functions are assumed to be collision
free, checking equality between the hashes is sufficient to assume the
validity of the signature.

The verification algorithm is formally detailed in the Figure 10.

Inputs $\displaystyle\@pc@lb$ \- Public key
$\mathsf{\vphantom{p}pk}=(\bm{H},\bm{y})$ with
$\bm{H}=(\bm{I}~{}\bm{H}^{\prime})\in\mathbb{F}_{q^{m}}^{(n-k)\times n}$ and
$\bm{y}\in\mathbb{F}_{q^{m}}^{n-k}$ such that $\bm{y}=\bm{H}\bm{x}$
$\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{\;\$,h_{1}}{\longleftarrow}(\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{\;\$,h_{2}}{\longleftarrow}(\\{I\subset
N~{}|~{}|I|=\ell\\})^{\tau}$ $\displaystyle\@pc@lb$ 3\. For each iteration
$e\in[1,\tau]$: $\displaystyle\@pc@lb$ $\diamond$ Choose deterministically
$i^{*(e)}$ from $S\setminus I^{(e)}$ $\displaystyle\@pc@lb$ $\diamond$ Parse
$\bar{\mathsf{rsp}}^{(e)}:=\big{(}(\llbracket\bar{\bm{x}}^{(e)}_{B}\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$ $\diamond$ For
each party $i\in I^{(e)}$: $\displaystyle\@pc@lb$ \- Compute
$\bar{{\mathsf{\vphantom{p}state}}}^{(e)}_{i}=(\llbracket\bar{\bm{x}}^{(e)}_{B}\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$ $\diamond$ 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$ $\diamond$ For
each party $i\in I^{(e)}$: $\displaystyle\@pc@lb$ \- Compute
$\llbracket\bar{\bm{x}}_{A}^{(e)}\rrbracket_{i}=\bm{y}-\bm{H}^{\prime}\llbracket\bar{\bm{x}}_{B}^{(e)}\rrbracket_{i}$
and
$\llbracket\bar{\bm{x}}^{(e)}\rrbracket_{i}=(\llbracket\bar{\bm{x}}_{A}^{(e)}\rrbracket_{i}\,||\,\llbracket\bar{\bm{x}}_{B}^{(e)}\rrbracket_{i})$
$\displaystyle\@pc@lb$ \- Compute
$\llbracket\bar{z}^{(e)}\rrbracket_{i}=-\sum\nolimits_{j=1}^{n}\gamma_{j}\left(\llbracket\bar{x}_{j}^{(e)}\rrbracket_{i}^{q^{r}}-\llbracket\bar{x}_{j}^{(e)}\rrbracket_{i}\right)$
and $\forall
k\in[1,r-1],\llbracket\bar{w}_{k}^{(e)}\rrbracket_{i}=\sum\nolimits_{j=1}^{n}\gamma_{j}\left(\llbracket\bar{x}_{j}^{(e)}\rrbracket_{i}^{q^{k}}-\llbracket\bar{x}_{j}^{(e)}\rrbracket_{i}\right)$
$\displaystyle\@pc@lb$ \- Compute
$\llbracket\bar{\bm{\alpha}}^{(e)}\rrbracket_{i}=\epsilon^{(e)}\cdot\llbracket\bar{\bm{w}}^{(e)}\rrbracket_{i}+\llbracket\bar{\bm{a}}^{(e)}\rrbracket_{i}$
$\displaystyle\@pc@lb$ $\diamond$ 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$ $\diamond$ For each party $i\in I^{(e)}$:
$\displaystyle\@pc@lb$ \- 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$ $\diamond$ 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 10: Rank based signature scheme with threshold - Verification algorithm

As for the additive sharing case, we prove in the Section 5.2 that this scheme
guarantees good security against EUF-CMA attack.

####  3.3.3 Using Shamir secret sharing

In practice, we use the $(\ell+1)$-threshold Shamir’s secret sharing scheme as
LSSS. Thus the shares of a secret value $s\in\mathbb{F}_{q}$ are defined as
$\llbracket s\rrbracket_{i}=P(e_{i})$, where $P$ is a polynomial whose
constant term is equal to $s$, and $e_{1},...,e_{N}\in\mathbb{F}_{q}$ are
public non zero distinct points. However, since each share corresponds to the
evaluation of a polynomial into a distinct point of $\mathbb{F}_{q}$, we get
that the number $N$ of parties is upper bounded by $q$. To have interesting
performances, it means that $q$ must be large (for example, $q=256$).

It is possible to mitigate this constraint. Let us assume that we want to
share values directly from $\mathbb{F}_{q^{m}}$ (instead of $\mathbb{F}_{q}$).
In that case, $e_{1},\ldots,e_{N}$ would belong to $\mathbb{F}_{q^{m}}$ and we
would have $N\leq q^{m}$ instead of $N\leq q$. The only issue comes from the
usage of the Frobenius endormorphism which is $\mathbb{F}_{q}$-linear and not
$\mathbb{F}_{q^{m}}$-linear. We can remark that, from a sharing $\llbracket
s\rrbracket$ of $s$, each party $i$ can obtain a sharing of $s^{q}$ by simply
computing $\llbracket s\rrbracket_{i}^{q}$. However, the evaluation points of
the obtained sharing and the encoding polynomial changed: they become
$e_{1}^{q},...,e_{N}^{q}$. Indeed,

$\displaystyle P(X)^{q}$
$\displaystyle=\left(s+\sum_{i=1}^{\ell}r_{i}X^{i}\right)^{q}$
$\displaystyle=s^{q}+\sum_{i=1}^{\ell}r_{i}^{q}(X^{q})^{i}$
$\displaystyle=\tilde{P}(X^{q})\qquad\text{where}\quad\tilde{P}=s^{q}+\sum_{i=1}^{\ell}r_{i}^{q}X^{i}$

One can add two shares if and only if they have the same evaluation points.
The optimized MPC protocol described used in Figure 9 does not satisfy this
property: we can not set the input sharings such that we have the guarantee
that addition is performed only on sharings with the same evaluation points.
However, if we want to have a scheme relying on Threshold-MPCitH with a small
$q$ (for example, with $q=2$), we can use the MPC protocol proposed in
[Fen22]. The latter satisfies the desired properties, see [Fen22, Appendix A]
for details.

##  4 Parameter sets

###  4.1 Choice of parameters

The problem Rank Syndrome Decoding is parameterized by the following
parameters:

  * •

$q\in\mathbb{N}$ \- the order of the base field on which the problem is based

  * •

$m\in\mathbb{N}$ \- the degree of the considered extension of the above field

  * •

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

  * •

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

  * •

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

The other parameters of the scheme are:

  * •

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

  * •

$\tau\in\mathbb{N}$ \- the number of rounds in the signature

  * •

$\eta\in\mathbb{N}$ \- allowing to build $\mathbb{F}_{q^{m\cdot\eta}}$

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

  * •

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

  * •

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

  * •

The size of the signature

Since the protocol is more efficient as $N$ grows (up to some point), we need
to take a larger value of $q$ in the threshold variant. To have a threshold
scheme with $N=256$ shares, we must take $q=256$ since we necessarily have
$N\leq q$ (in the Shamir Secret Sharing scheme, we can’t have more shares than
the number of elements in the base field; this means we can’t have more
parties than the cardinal of $\mathbb{F}_{q}$ in our case).

In additive sharing, we take the value of $q=2$, since it is the most
efficient and we have no constraints. We propose here two versions of the
signature scheme with different values for $N$: we set $N=256$ for a short
version of the signature, and $N=32$ for a fast one.

The choice of $(q,m,n,k,r)$ was then made in order to achieve the target
security in regards to the attacks we present in Subsection 6.2.

As for the choice of $\tau$ and $\eta$, we need to choose them such that our
signature scheme resists to the forgery attack described by [KZ20], which we
explain in Subsection 6.1. Because of this, in the additive protocol optimized
with the hypercube technique, we need to set $\tau$ 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\\}$
(2)

is higher than $2^{\lambda}$, with
$p=\frac{2}{q^{m\eta}}-\frac{1}{q^{2m\eta}}$. The value depends on $\tau$ and
$\eta$, we then need to take them such that the signature is safe, and as
small as possible, given the parameters of the Rank-SD instance.

In the case of the threshold protocol, this formula changes:

$\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\\}$
(3)

with $p=(\frac{2}{q^{m\eta}}-\frac{1}{q^{2m\eta}})\cdot\binom{N}{\ell+1}$, see
[FR22] for details.
In any case, as long as the cost of the forgery is high enough, we can just
take the parameters for which the size of signature is the smallest.

We propose the following parameters for a security of $\lambda=128$ bits:

  * •

For the additive scheme: $(q,m,n,k,r)=(2,31,33,15,10)$

  * •

For the threshold scheme with $\ell=3$: $(q,m,n,k,r)=(256,11,12,5,5)$

  * •

For the threshold scheme with $\ell=3$ with small $q$:
$(q,m,n,k,r)=(2,31,29,14,10)$

###  4.2 Signature and key sizes

####  4.2.1 Additive MPC

We must send for each $e\in[1,\tau]$ the following elements:
$\mathsf{cmt}_{i^{*}}\in\\{0,1\\}^{2\lambda}$ and
$({\mathsf{\vphantom{p}state}}^{(e)}_{i})_{i\neq i^{*}}$ (which consists in
seeds in $\\{0,1\\}^{2\lambda}$ or the following elements for one of them:
$\llbracket\bm{x}_{B}\rrbracket\in\mathbb{F}_{q^{m}}^{k}$,
$\llbracket\bm{\alpha}\rrbracket\in\mathbb{F}_{q^{m\cdot\eta}}^{r-1}$,
$\llbracket\bm{\beta}\rrbracket\in\mathbb{F}_{q^{m}}^{r-1}$, $\llbracket
c\rrbracket\in\mathbb{F}_{q^{m\cdot\eta}}$); and
$(\mathsf{salt}|h_{1}|h_{2})\in\\{0,1\\}^{6\lambda}$.

Note also that for each $e\in[1,\tau]$, we do not send all the $N-1$ seeds
$({\mathsf{\vphantom{p}state}}^{(e)}_{i})$, since we use a tree-PRG (noted
TPRG in the figures) to generate them: starting from the root seed, each seed
is recursively expanded in two child seeds until we obtain $N$ seeds. We
obtain a tree of depth $\log_{2}N$, and we only reveal the $\log_{2}N$ sibling
nodes of the root-leaf path of the hidden leaf $i^{*}$ to reveal all the
leaves except $i^{*}$.

We can now compute the communication cost of the protocol (in bits):

$\text{$|\sigma|$}=\underbrace{6\lambda}_{\text{$\mathsf{salt},h1,h2$}}+\>\tau\cdot\left(\Big{(}\underbrace{(r-1)m\eta}_{\text{$\bm{\alpha}$}}+\underbrace{km}_{\text{$\bm{x}_{B}$}}+\underbrace{(r-1)m}_{\text{$\bm{\beta}$}}+\underbrace{m\eta}_{\text{$c$}}\Big{)}\cdot\log_{2}q+\underbrace{2\lambda+(\log_{2}N)\lambda}_{\text{additive
MPCitH}}\right)\\\ $

Parameters are chosen such the Rank-SD problem is secure against the existing
attacks (see Section 6.2). We recall that the security levels of the signature
I, III and V correspond respectively to the security of AES-128, AES-192 and
AES-256. Tables 1 and 2 give the theoretical signature size for different set
of secure parameters in the case of additive shares:

NIST security level | $q$ | $m$ | $n$ | $k$ | $r$ | $N$ | $\eta$ | $\tau$ | $\mathsf{\vphantom{p}pk}$ | $\sigma$
---|---|---|---|---|---|---|---|---|---|---
1 | 2 | 31 | 33 | 15 | 10 | 256 | 1 | 20 | 0.1 kB | 5.9 kB
3 | 2 | 37 | 41 | 18 | 13 | 256 | 1 | 29 | 0.1 kB | 12.9 kB
5 | 2 | 43 | 47 | 18 | 17 | 256 | 1 | 38 | 0.1 kB | 22.8 kB
Table 1: Parameters for additive MPC on hypercube, short signature NIST security level | $q$ | $m$ | $n$ | $k$ | $r$ | $N$ | $\eta$ | $\tau$ | $\mathsf{\vphantom{p}pk}$ | $\sigma$
---|---|---|---|---|---|---|---|---|---|---
1 | 2 | 31 | 33 | 15 | 10 | 32 | 1 | 30 | 0.1 kB | 7.4 kB
3 | 2 | 37 | 41 | 18 | 13 | 32 | 1 | 44 | 0.1 kB | 16.4 kB
5 | 2 | 43 | 47 | 18 | 17 | 32 | 1 | 58 | 0.1 kB | 29.1 kB
Table 2: Parameters for additive MPC on hypercube, fast signature

####  4.2.2 Threshold MPC

In the threshold case, the process is similar to the additive one above: we
must send for each $e\in[1,\tau]$ the following elements:
$h\in\\{0,1\\}^{2\lambda}$ (an hash used) and $\ell$ times all the
elements$({\mathsf{\vphantom{p}state}}^{(e)}_{i})_{i\neq i^{*}}$; and one time
$(\mathsf{salt}|h_{1}|h_{2})\in\\{0,1\\}^{6\lambda}$.

The signature size of the scheme is given by

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

Let us recall that the scheme requires that $N\leq q$. If we want to use a
small $q$, we need to replace our MPC protocol with the one described in
[Fen22] (see Section 3.3.3 for details). In that case, the signature size is
given by

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

Tables 3 and 4 give the theoretical signature size for different set of secure
parameters in the case of threshold shares for $\ell=3$ and $\ell=1$:

NIST security level | $q$ | $m$ | $n$ | $k$ | $r$ | $N$ | $\eta$ | $\tau$ | $\mathsf{\vphantom{p}pk}$ | $\sigma$
---|---|---|---|---|---|---|---|---|---|---
1 | 256 | 11 | 12 | 5 | 5 | 256 | 2 | 6 | 0.1 kB | 8.2 kB
3 | 256 | 13 | 17 | 7 | 6 | 256 | 1 | 11 | 0.1 kB | 18.3 kB
5 | 256 | 17 | 17 | 7 | 7 | 256 | 3 | 14 | 0.1 kB | 32.5 kB
Table 3: Parameters for threshold with $\ell=3$, $q=256$ NIST security level | $q$ | $m$ | $n$ | $k$ | $r$ | $N$ | $\eta$ | $\tau$ | $\mathsf{\vphantom{p}pk}$ | $\sigma$
---|---|---|---|---|---|---|---|---|---|---
1 | 2 | 31 | 33 | 15 | 10 | 256 | 2 | 18 | 0.1 kB | 9.3 kB
3 | 2 | 37 | 41 | 18 | 13 | 256 | 2 | 27 | 0.1 kB | 21.4 kB
5 | 2 | 43 | 47 | 18 | 17 | 256 | 2 | 35 | 0.1 kB | 34.8 kB
Table 4: Parameters for threshold with $\ell=1$, $q=2$

##  5 Security analysis

###  5.1 Security proof for the proof of knowledge

####  5.1.1 Additive MPC

We prove here that our protocol fulfils the three required properties:
completeness, soundness and zero-knowledge. The proofs of this section are
close to those in [AMGH+22] (which are themselves close to [FJR22]) due to the
same structure of hypercube used, as only the MPC protocol changed.

We firstly prove that an honest prover is always accepted. Conversely, a
prover who commits a bad witness in the first step of the protocol has a
probability lower than $\epsilon=\left(p+(1-p)\frac{1}{N}\right)$ of being
accepted. Consequently, a prover that has a higher probability of acceptance
knows the secret.

###### Theorem 5.1

The protocol in Figure 3 is perfectly complete. Namely, a prover that knows
$x$ and executes the protocol correctly is accepted by a verifier with
probability 1.

###### Proof

By construction, if the prover has knowledge of a solution of the Rank-SD
instance, he is always able to execute the protocol correctly.

###### Theorem 5.2

If an efficient prover $\mathcal{\tilde{P}}$ with knowledge of only public
data $(\bm{H},\bm{y})$ can convince a verifier $\mathcal{V}$ with probability:

$\tilde{\epsilon}=\mathsf{Pr}\big{(}\langle\mathcal{\tilde{P}},\mathcal{V}\rangle\rightarrow
ACCEPT\big{)}>\epsilon=p+(1-p)\dfrac{1}{N}$

then there exists an extraction function $\mathcal{E}$ that produces a
commitment collision, or a good witness $\bm{x^{\prime}}$ solution of the
Rank-SD instance, by making an average number of calls to
$\mathcal{\tilde{P}}$ upper bounded by:

$\dfrac{4}{\tilde{\epsilon}-\epsilon}\left(1+\dfrac{2\tilde{\epsilon}\ln
2}{\tilde{\epsilon}-\epsilon}\right)$

###### Proof

The proof is similar to that of [AMGH+22]. We first need to establish that the
probability for the malicious prover (who has no knowledge of the solution of
the Rank-SD instance used) 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:

  * •

He obtains the value $v=0$ when executing the MPC protocol thanks to a false
positive.

  * •

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

The first case occurs with probability
$p=\frac{2}{q^{m\eta}}-\frac{1}{q^{2m\eta}}$, as false positive rate of the
protocol $\Pi^{\eta}$.

In the second case, the malicious prover needs to alter the communications in
order to fool the verifier. Among the $N$ shares, only the share $i^{*}$ is
not be revealed by the prover. This means that, if he cheats on more than one
share, the verifier notices the cheating, and thus rejects the proof. However,
if he cheats on zero share, he is rejected as well since the value $v$ isn’t
$0$ since the malicious prover does not have a good witness.

This means the malicious prover can only cheat on one share exactly. However,
cheating on one share $s$ implies that this it appears on one main share of
all the $D$ dimensions, as the main shares are the sum of leaves that have the
same index $i_{k}$ 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 parties. This happens with probability $\frac{1}{N}$ (as the prover does
not know the value of $i^{*}$ before cheating). No other cheating is possible,
because all leaf parties except $i^{*}$ are revealed. Remark that cheating on
the main parties give the same probability of success, since the prover should
cheat for each dimension on the main party associated to the unrevealed leaf
$i^{*}$.

Thus, the probability for the malicious prover to fool the verifier is at
most: $p+(1-p)\cdot\frac{1}{N}=\frac{1}{N}+(1-\frac{1}{N})\cdot p$.
We then need to show that the soundness is exactly this value, which we do in
what follows:
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}_{B}\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}_{B}\rrbracket,\llbracket\bm{\beta}\rrbracket,\llbracket\bm{a}\rrbracket$
and $\llbracket c\rrbracket$ are equal in the transcripts.

We 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 show
further that this means we can build an extractor function in order to obtain
a good witness.

$\bm{x}$ is called a good witness if it is solution to the Rank-SD instance
defined by public data, i.e. $\bm{H}\bm{x}=\bm{y}$ and $W_{R}(\bm{x})\leq r$.
Let $R_{h}$ the random variable associated to the randomness in initial
commitment, and $r_{h}$ is the value it takes.

For a malicious prover $\mathcal{\tilde{P}}$ to be able to get these two
transcripts, he 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, $\tilde{\mathcal{P}}$ repeats the process, until he finds another
accepted transcript, $\mathcal{T}_{2}$, for which the leaf challenge,
$i^{*}_{2}$, is different than $i^{*}_{1}$.

  * •

He then recovers the witness. If it is a bad witness, he repeats from the
beginning.

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 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, 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 obtain 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 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 time one
has to repeat the protocol to find $\mathcal{T}_{2}$. For that, we take the
opposite probability, i.e,
$1-\mathsf{Pr}(\operatorname{Success}_{\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{Success}_{\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 have 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 note $\mathbb{E}(\tilde{\mathcal{P}})$ the number of repetitions
$\tilde{\mathcal{P}}$ has to make. 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 iterations
$\tilde{\mathcal{P}}$ has to do before being able to retrieve a good witness,
in the case where the probability to cheat was higher than $\epsilon$. This
proves that $\epsilon$ is exactly the value $\frac{1}{N}+(1-\frac{1}{N})\cdot
p$.

We now have to prove zero-knowledge property by building a simulator which
outputs indistinguishable transcripts with the distribution of transcripts
from honest executions of the protocol.

The main intuition is that if the prover knows the challenge before committing
the initial shares, then he knows for which party to cheat. We consequently
build an HVZK simulator which firstly generate the challenge to build valid
transcriptions of the protocol.

###### Theorem 5.3

If the algorithm PRG is a secure pseudo-random generator and the commitment
$\mathsf{Com}$ is hiding, then the algorithm 11 is Honest-Verifier Zero
Knowledge.

###### Proof

Consider a simulator, described in Figure 11, 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 : An instance of a Rank-SD problem :
$\bm{H}=(I~{}\bm{H}^{\prime})\in\mathbb{F}_{q^{m}}^{(n-k)\times n}$ and
$\bm{y}\in\mathbb{F}_{q^{m}}^{n-k}$ $\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},\rho_{i})$.
$\displaystyle\@pc@lb$ 4\. For each $i\in[1,N]\backslash\\{i^{*}\\}$ :
$\displaystyle\@pc@lb$ \- Sample
$\llbracket\bm{a}\rrbracket_{i}\overset{\;\$,\mathsf{seed}_{i}}{\longleftarrow}\mathbb{F}_{q^{m\cdot\eta}}^{r-1}$
$\displaystyle\@pc@lb$ If $i\neq N$ $\displaystyle\@pc@lb$ \- Sample
$(\llbracket\bm{x}_{B}\rrbracket_{i},\llbracket\bm{\beta}\rrbracket_{i},\llbracket
c\rrbracket_{i})\overset{\;\$,\mathsf{seed}_{i}}{\longleftarrow}TPRG$
$\displaystyle\@pc@lb$ \- ${\mathsf{\vphantom{p}state}}_{i}=\mathsf{seed}_{i}$
$\displaystyle\@pc@lb$ \- Else: $\displaystyle\@pc@lb$ \- Sample
$\left(\llbracket\bm{x}_{B}\rrbracket_{N},\llbracket\bm{\beta}\rrbracket_{N},\llbracket
c\rrbracket_{N}\right)\overset{\;\$}{\longleftarrow}\mathbb{F}_{q^{m}}^{k}\times\mathbb{F}_{q^{m}}^{r}\times\mathbb{F}_{q^{m\cdot\eta}}$
$\displaystyle\@pc@lb$ \-
$\mathsf{aux}_{N}=\left(\llbracket\bm{x}_{B}\rrbracket_{N},\llbracket\bm{\beta}\rrbracket_{N},\llbracket
c\rrbracket_{N}\right)$ $\displaystyle\@pc@lb$ \-
${\mathsf{\vphantom{p}state}}_{N}=\mathsf{seed}_{N}\,||\,\mathsf{aux}_{N}$
$\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-1}$
$\displaystyle\@pc@lb$ \- $\llbracket v\rrbracket_{i^{*}}=-\sum_{i\neq
i^{*}}\llbracket v\rrbracket_{i}$ $\displaystyle\@pc@lb$ 6\. Compute the
commitment:
$\mathsf{cmt}_{i^{*}}=\mathsf{Com}\big{(}{\mathsf{\vphantom{p}state}}_{i^{*}},\rho_{i^{*}}\big{)}$.
$\displaystyle\@pc@lb$ 7\. Commit the full hypercube:
$h_{0}=\mathsf{Com}\big{(}cmt_{1},...,cmt_{N}\big{)}$.
$\displaystyle\@pc@lb[]$ 8\. For each main party $p\in[1,2]$ : compute
$\llbracket\bm{\alpha}\rrbracket_{p}$ and $\llbracket v\rrbracket_{p}$
$\displaystyle\@pc@lb$ 9\. For each dimension $k\in[1,D]$ : compute
$H_{k}=\mathsf{H}(\llbracket\bm{\alpha}\rrbracket,\llbracket v\rrbracket)$
$\displaystyle\@pc@lb$ 10\. Compute $h_{1}=\mathsf{H}(H_{1},...,H_{D})$
$\displaystyle\@pc@lb[]$ Step 3 : Output transcript $\displaystyle\@pc@lb$

Figure 11: HVZK simulator for zero-knowledge proof optimized with the
hypercube technique

  * •

Simulator 0 (real world): It correctly executes the algorithm 3, hence its
output is the correct distribution.

  * •

Simulator 1: Same as the Simulator 0, but starts by sampling the random
challenges, and then uses true randomness instead of seed-derived randomness
for leaf $i^{*}$. If $i^{*}=N$, the leafs
$\llbracket\bm{x}_{B}\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})$-secure, 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 world, their
distribution is also indistinguishable.

  * •

Simulator 2: Replace the leafs
$\llbracket\bm{x}_{B}\rrbracket_{N},\llbracket\bm{\beta}\rrbracket_{N},\llbracket
c\rrbracket_{N}$ in Simulator 1 by uniform sampled values. Compute $\llbracket
v\rrbracket_{i^{*}}=-\sum_{i\neq i^{*}}\llbracket v\rrbracket_{i}$. Note that
this simulator becomes independent of the secret witness $\bm{x}_{B}$.

If $i^{*}=N$, it only impacts the shares
$\llbracket\bm{\alpha}\rrbracket_{i^{*}}$ and $\llbracket
v\rrbracket_{i^{*}}$. Note that this change does not alter the uniform
distribution of these values. It does not alter the distribution of any other
leaf.

If $i^{*}\neq N$, it only impacts
$\mathsf{aux}_{N}=\left(\llbracket\bm{x}_{B}\rrbracket_{N},\llbracket\bm{\beta}\rrbracket_{N},\llbracket
c\rrbracket_{N}\right)$ in the simulated response and the values computed from
them in the MPC protocol. It does not alters the distribution of other leaves.
We observe that the shares in $\mathsf{aux}_{N}$ are calculated by adding a
randomness value from each seed of party $i\neq i^{*}$, which amounts to
adding a uniform random value from $\mathsf{seed}_{i^{*}}$. Since this
distribution was uniform too 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, Simulator 3
samples it uniformly at random from $\mathbb{F}_{q^{m\cdot\eta}}^{r-1}$. As in
the previous simulator, it does not change their output distribution.

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

####  5.1.2 MPC with threshold

We discuss here the security properties of the threshold protocol. The
following proofs are only sketched, as they are very similar to those of the
hypercube protocol.

###### Theorem 5.4

The protocol in Figure 8 is perfectly complete. Namely, a prover who knows $x$
and performs the protocol correctly is accepted by a verifier with probability
1.

###### Proof

Same trivial justification as in the previous case of the hypercube.

###### Theorem 5.5

Suppose that there is an efficient prover $\mathcal{\tilde{P}}$ that on input
$(\bm{H},\bm{y})$ convinces an honest verifier $\mathcal{V}$ to accept with
probability

$\tilde{\epsilon}=\mathsf{Pr}\big{(}\langle\mathcal{\tilde{P}},\mathcal{V}\rangle\rightarrow
ACCEPT\big{)}>\epsilon=\dfrac{1}{\binom{\ell}{N}}+p\cdot\dfrac{\ell\cdot(N-\ell)}{\ell+1}$

then there exists an extraction algorithm $\mathcal{E}$ that produces a
commitment collision, or a good witness $\bm{x^{\prime}}$ solution of the
Rank-SD instance, by making an average number of calls to
$\mathcal{\tilde{P}}$ bounded from above:

$\dfrac{4}{\tilde{\epsilon}-\varepsilon}\left(1+\dfrac{8\cdot(N-\ell)}{\tilde{\epsilon}-\epsilon}\right)$

###### Proof

For this proof, we refer to [FR22], which proves this theorem for any MPC
protocol fitting this model. Our threshold protocol is an exact application of
this model. Hence, the proof of the above theorem is the same as the proof in
appendix D of [FR22].

###### Theorem 5.6

If the algorithm PRG is pseudo-random generator and the commitment
$\mathsf{Com}$ is hiding, then there exists an honest-Verifier Zero Knowledge
algorithm.

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 provided in
[FR22, Appendix C]. Since we are in their model of MPCitH, the proof applies
here as well.

###  5.2 Security proof for signature schemes

As in the previous subsection, the proofs are largely inspired by the work of
[AMGH+22], which is largely inspired by [FJR22]. The two proofs are very
similar, and proceed in two main steps: we begin by explaining how efficiently
simulate a signature oracle to a CMA adversary using public key and the honest
verifier zero-knowledge simulator. We then show how such a RUF-CMA adversary
can be used to extract a solution to the Rank-SD instance.

####  5.2.1 Additive-RYDE

We begin by computing the probability of an attack on the signature based in
the hypercube MPC.

###### Theorem 5.7

Let the signature be $(t,\epsilon_{PRG})$-secure and with adversary of
advantage at most $\epsilon_{RSD}$ against the underlying Rank-SD problem. Let
$\mathsf{H}_{0}$, $\mathsf{H}_{1}$, $\mathsf{H}_{2}$, $\mathsf{H}_{3}$, and
$\mathsf{H}_{4}$ be random oracles with output length $2\lambda$ bits. If an
adversary makes $q_{i}$ queries to $\mathsf{H}_{i}$ and $q_{S}$ queries to the
signature oracle, the probability of such an adversary producing an
existential forgery under chosen message attack (EUF-CMA) is bounded from
above by:

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

where $q=\operatorname{max}\\{q_{0},q_{1},q_{2},q_{3},q_{4}\\}$, $\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}}$
is the false positive rate of the underlying MPC protocol,
$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 adopt a game hopping strategy in order to find the upper
bound. We note $\mathsf{Pr}_{i}[\mathsf{Forge}]$ the probability of forgery
when considering game $i$.

The first game is the access to the standard signing oracle by the adversary
$\mathcal{A}$. Then, we game hop in order to eliminate the cases where
collisions happen, and, through some other games, we manage to find an upper
bound. The aim of the proof is to find this 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{H},\bm{y})$ and $\bm{x}$, and $\mathcal{A}$
receives $(\bm{H},\bm{y})$. $\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:
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}$.
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^{\lambda}}$

  * •

Game 3:
The attacker now fails if the inputs to any of the $\mathsf{H}_{i}$ has
already appeared in a previous query. If that happens, this means that at
least the salt used was the same (we emphasize on at least). We have one
$\mathsf{salt}$ sampled every time a query is made to the signing oracle, and
it can collide each time with: a previous $\mathsf{salt}$, or any of the
queries to the $\mathsf{H}_{i}$. This means, we can bound this with:

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

  * •

Game 4:
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:

$\left\lvert\mathsf{Pr}_{7}[\mathsf{Forge}]-\mathsf{Pr}_{6}[\mathsf{Forge}]\right\rvert\leq\epsilon_{PRG}$

  * •

Game 5:
Finally, we say that an execution $e^{*}$ of a query
$h_{2}=\mathsf{H}_{4}(m,\mathsf{salt},h_{1},{H_{1}^{(e)}\dots
H_{D}^{(e)}}_{e\in[1,\tau]})$ defines a good witness $\bm{x}$ if:

    * –

Each of the $H_{k}^{(e)}$ are the output of a query to $\mathsf{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}(\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{H}\bm{x}=\bm{y}$ such that $\operatorname{W}_{R}(\bm{E})\leq r$. In
the case where an execution like this happens, we are able to retrieve the
correct witness from the states
$\\{{\mathsf{\vphantom{p}state}}_{i}\\}_{i\in[1,N]}$, and as a consequence, we
are able to solve the Rank-SD instance. This means that
$\mathsf{Pr}_{8}[\mathsf{Solve}]\leq\epsilon_{RSD}$.

Finally, we only need to look at the upper bound of
$\left\lvert\mathsf{Pr}_{8}[\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}$ does not 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})\>|\>\mathsf{\overline{Solve}})\leq p$.
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 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 party (it is already
established that is isn’t possible to cheat on less, or on more, than one
party). 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}_{8}(\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 Threshold-RYDE

We compute now the probability to forge the signature based on the MPC
threshold.

###### Theorem 5.8

Let the signature be $(t,\epsilon_{PRG})$-secure and with adversary of
advantage at most $\epsilon_{RSD}$ against the underlying Rank-SD problem. Let
$\mathsf{H}_{0}$, $\mathsf{H}_{1}$, $\mathsf{H}_{2}$ and $\mathsf{H}_{M}$ be
random oracles with output length $2\lambda$ bits. The probability of such an
adversary producing an existential forgery under chosen message attack (EUF-
CMA) is bounded from above by:

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

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}}$
the false positive rate of the MPC protocol,
$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}\left(\tau-X,\frac{1}{\binom{N}{\ell}}\right)$.

###### Proof

The proof is based on the same operation as the previous one, adopting a game
hopping strategy. The first game is the access to the standard signing oracle
by the adversary $\mathcal{A}$. The aim of the proof is to find this 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{H},\bm{y})$ and $\bm{x}$, and $\mathcal{A}$
receives $(\bm{H},\bm{y})$. $\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(2N-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. We
can then give an upper bound to the queries made by $\mathcal{A}$ to the hash
functions, which is then: $q+\tau\cdot(2N-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(2N-1)\cdot
q_{S})^{2}}{2^{\lambda}}$

  * •

Game 3:
The attacker now fails if the inputs to any of the hash functions has already
appeared in a previous query. If that happens, this means that at least the
$\mathsf{salt}$ used was the same. Since we don’t use $\mathsf{salt}$ in the
Merkle Tree, this only concerns
$\mathsf{H}_{0},\mathsf{H}_{1},\mathsf{H}_{2}$. We sample $\mathsf{salt}$
$q_{S}$ time (once by signing oracle query), and $3q$ 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:

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

  * •

Game 4: