Dual Support Decomposition in the Head: Shorter Signatures from Rank SD and MinRank

The MPC-in-the-Head (MPCitH) paradigm is a popular framework to build post-quantum signatures. After sharing the secret key, the signer emulates “in his head” an MPC protocol and commits each party’s view independently. He then reveals the views of a pseudo-random subset of parties, where this subset is given by the hash digest of the commitments (in the setting of the Fiat-Shamir heuristic). By the privacy of the MPC protocol, nothing is revealed about the secret key, which implies the zero-knowledge property. On the other hand, a malicious signer needs to cheat for at least one party, which shall be discovered by the verifier with high probability, hence ensuring the unforgeability property.

In the new NIST call for additional post-quantum signatures [33], many submissions rely on the MPCitH paradigm applied on a large range of security assumptions. Three MPCitH candidates fall in the rank-based cryptography category:

• RYDE [4], for which the security relies on the hardness of solving the rank syndrome decoding problem;

• MIRA [5] and MiRitH [1], for which the security relies on the hardness of solving the MinRank problem (MIRA and MiRitH rely on the same security assumption, but use different modelings and MPC protocols).

Recently, new techniques of MPC-in-the-Head have been proposed:

• the VOLE-in-the-Head (VOLEitH) framework [12] released in Summer 2023;^{Footnote 1}

• the TC-in-the-Head (TCitH) framework [22] released in Autumn 2023.^{Footnote 2}

As shown in [22] a simple application of these frameworks leads to shorter and faster signature schemes compared to those submitted to the NIST call (for similar underlying security assumption).

For MPCitH-based schemes (including those based on VOLEitH and TCitH), the signatures are composed of two parts, a “symmetric part” made of seeds and hash digests and an “arithmetic part” composed of the open party views and broadcast shares of the MPC protocol. While for a given security level the symmetric part is of rather fixed size (for the considered MPCitH framework), the arithmetic part depends on the modeling of the used security assumption and the associated MPC protocol. In the traditional broadcast-based MPCitH framework (i.e. the MPCitH framework widely used before VOLEitH and TCitH), to minimize the signature size, the designers had minimize the sum of the sizes of the MPC input and of the broadcasted values while considering only linear multiparty computation. With the VOLEitH and TCitH frameworks, the game rules have changed. These frameworks enable quadratic (or higher degree) multiparty computation, which implies that minimizing the signature size is achieved only by minimizing the MPC protocol input (i.e., the witness of the modeling).

In rank-based cryptography, several modelings for the rank syndrome decoding problem and the MinRank problem have been proposed. The first one is derived from [37] and consists in working with a permuted version and an additively-masked version of the secret. The best scheme relying on it is proposed in [15]. The second modeling is based on q-polynomials and is first used in such a context in [20]. The third modeling consists in writing the low-rank object as the product of two small matrices and is first used in such a context in [2] and [20]. The last modeling relies on Kipnis-Shamir technique, initially proposed for the cryptanalysis of the MinRank problem [29] and used to build a scheme in [1]. We sum up the different techniques to handle the rank metric in Table 1.

In this work, we explore modelings for the rank syndrome decoding problem and the MinRank problems to identify the best option with the new VOLEitH and TCitH techniques. We show that the shortest signatures with RSD and MinRank are obtained thanks to the dual support decomposition modeling, which consists in finding a basis \((e_1,\ldots ,e_r)\) and coefficients \(c_{1,1},\ldots ,c_{n,r}\) such that

While this modeling is quite natural for the rank syndrome decoding problem, it requires to work with a dual matrix of a code in the MinRank problem: we need to consider the syndrome decoding problem for matrix codes. In fact, the MinRank problem being the message decoding problem for such codes, we define in this work the MinRank Syndrome problem, which is a equivalent variant of the MinRank problem which has not been previously used in cryptosystems. Working in the dual has the advantage to remove the encoded message from the witness of the code-based problem, leading to a shorter witness. With the dual support decomposition modeling, the witness size (and thus the signature size) is independent of the code dimension, thanks to the definition of the syndrome version of the MinRank problem. This enables us to optimize the parameters by taking codes of larger dimensions.

We then apply the TCitH and VOLEitH frameworks on the optimal modeling, yielding new signature schemes with smaller sizes as summarized in Table 2. We also put the signature sizes of the NIST candidates based on the same security assumptions (namely RYDE, MIRA and MiRitH) in the column “MPCitH” and their signature sizes when performing a straightforward application of VOLEitH and TCitH. We observe that the difference in signature sizes between VOLEitH and TCitH tends to disappear while increasing the parameter N, i.e., the number of leaves in GGM seed trees used for the commitment (a.k.a. the number of parties in standard MPCitH schemes). Since these two frameworks are faster than previous MPCitH schemes, it becomes natural to consider larger values of N. We obtain signature sizes down to 3.7 kB for TCitH with \(N=256\) leaves, and down to 2.9 kB for VOLEitH and TCitH with \(N=2048\) leaves (more details are given in Tables 7 and 10). The ranges of sizes reported in Table 2 correspond to a parameter N ranging between 256 and 2048. Let us note that new generic optimizations for MPCitH-based signatures have been proposed in [11] very recently. We applied these optimisations to our new signature schemes, enabling us to save an additional few hundred bytes. The obtained sizes are reported in Table 2 with the label “optimized”.

Paper Organization. The paper is organized as follows: In Sect. 2, we introduce the necessary background on the rank metric and sharing schemes. We present the existing attacks against \(\textsf{RSD}\) and \(\textsf{MinRank}\) in Sect. 3. We explore the possible modelings for rank-based cryptography in Sect. 4. We recall the TCitH and VOLEitH frameworks in Sect. 5 and we apply these frameworks to the dual support decomposition modeling to obtain new signature schemes in Sect. 6.

2.1 Notations

We denote by \(\mathbb {F}_q\) the finite field of size q. The set of vectors with n coordinates in \(\mathbb {F}_q\) is referred as \(\mathbb {F}_q^{n}\), the set of matrices with m rows and n columns in \(\mathbb {F}_q\) is referred as \(\mathbb {F}_q^{m\times n}\). We use lowercase bold letters to represent vectors and uppercase bold letters for matrices (\(\boldsymbol{E} \in \mathbb {F}_q^{m \times n}\), \(\boldsymbol{x} \in \mathbb {F}_q^k\), \(x \in \mathbb {F}_q\)). The subset of integers from 1 to n is represented with \([1, n]\). If S is a set, we write \(x\overset{\;\$}{\longleftarrow }S\) the uniform sampling of a random element x in S. We note the \(\mathbb {F}_q\)-linear subspace of \(\mathbb {F}_{q^m}\) generated by \((x_1,\dots ,x_n) \in \mathbb {F}_{q^m}^{n}\) as \(\langle x_1,\dots ,x_n\rangle \). Let us define the gaussian coefficient \({ \begin{bmatrix} \textit{m} \\ \textit{r} \end{bmatrix}_q } = \prod _{i=0}^{r-1}\frac{q^m-q^i}{q^r-q^i} \approx q^{r(m-r)}\), it corresponds to the number of different dimension-r \(\mathbb {F}_q\)-linear subspaces of \(\mathbb {F}_{q^m}\).

2.2 Secret Sharing

A threshold secret sharing scheme is a method to share a value v into a sharing \([\![ v ]\!]:=([\![ v ]\!]_1,\ldots ,[\![ v ]\!]_N)\) such that v can be reconstructed from any \(\ell \)+1 shares while no information is revealed on the secret from the knowledge of \(\ell \) shares. We note by \([\![ x ]\!]_i\) the i^th share of \([\![ x ]\!]\) (i.e. the share of the i^th party). We can also note \([\![ x ]\!]_I\) where I is a set of indices, to denote all the shares of the parties in the set I.

Let us define Shamir’s secret sharing scheme [36], since the frameworks we will consider rely on it. Let \(\ell \) and N two integers such that \(1 \le \ell \le N\). Let \(e, \omega _1, \ldots , \omega _N\) be \(N+1\) distinct elements of \(\mathbb {F}\cup \{\infty \}\). To share a value \(v\in \mathbb {F}\) using Shamir’s secret sharing scheme, one should

1. 1.

   sample \(\ell \) randoms values \(r_1,\ldots ,r_\ell \) of \(\mathbb {F}\);

2. 2.

   compute the polynomial P by interpolation such that

   $$P(e) = v ~~~\text {and}~~~ \forall i\in [1,\ell ], P(\omega _i) = r_i;$$
3. 3.

   build the N shares \([\![ v ]\!]_1,\ldots ,[\![ v ]\!]_N\) as

   $$\forall i\in [1,N],~ [\![ v ]\!]_i := P(\omega _i).$$

To recover the secret value from \(\ell +1\) shares, we re-compute the polynomial P by interpolation and we just deduce P(e). Let us stress that \(P(\infty )\) refers to the leading coefficient of the polynomial P. The most classical choice is to set e to zero but we may consider alternative choices depending on the context (and in particular \(e = \infty \)).

We define the degree of a Shamir’s secret sharing as the degree of the underlying polynomial. A sharing generated using the above process is of degree \(\ell \). The sum of a \(d_1\)-degree sharing and a \(d_2\)-degree sharing is of degree \(\max (d_1,d_2)\), while the multiplication is of degree \(d_1+d_2\).

2.3 Rank Metric and Hard Problems for Cryptography

We will first recall some background on the Rank Metric, and we will then define hard problems we will use (\(\textsf{RSD}\) and \(\textsf{MinRank}\)).

Definition 1

(Rank Metric over \(\mathbb {F}_{q^m}^n\)). Let \(\boldsymbol{x} = (x_1,\dots ,x_n) \in \mathbb {F}_{q^m}^n\), and \(\mathcal {B} = (b_1,\dots ,b_m) \in \mathbb {F}_{q^m}^m\) an \(\mathbb {F}_q\)-basis of \(\mathbb {F}_{q^m}\). Each coordinate \(x_j\) can be associated with a vector \((x_{j,1},\dots ,x_{j,m}) \in \mathbb {F}_q^m\) such that \(x_j = \sum _{i=1}^m x_{j,i}b_i\). Let us define the following notations:

• \(\boldsymbol{M}_{\boldsymbol{x}} = (x_{j,i})_{(j,i) \in [1, n]\times [1, m]} \) is the matrix associated to the vector \(\boldsymbol{x}\);

• the rank weight is defined as: \(w_R\big (\boldsymbol{x}\big ) = \textsf{rank}(\boldsymbol{M_x})\);

• the distance between two vectors \(\boldsymbol{x}\) and \(\boldsymbol{y}\) in \(\mathbb {F}_{q^m}^n\) is: \(d(x,y) = w_R\big (\boldsymbol{x}-\boldsymbol{y}\big ) \);

• the support of a vector \(\operatorname {Supp}{(\boldsymbol{x})}\) is the \(\mathbb {F}_q\)-linear subspace of \(\mathbb {F}_{q^m}\) generated by its coordinates: \(\operatorname {Supp}{(\boldsymbol{x})} = \langle x_1,\dots ,x_n \rangle \).

Definition 2

A linear code \(\mathcal {C}\) over \(\mathbb {F}_{q^m}\) of dimension k and length n is a linear subspace of \(\mathbb {F}_{q^m}^n\) of dimension k. The elements of \(\mathcal {C}\) are called codewords. The code \(\mathcal {C}\) can be represented in two ways:

• by a generator matrix \(\boldsymbol{G}\), where \(\mathcal {C}= \{\boldsymbol{mG}, \boldsymbol{m} \in \mathbb {F}_{q^m}^k\}\), or

• by a parity-check matrix \(\boldsymbol{H} \in \mathbb {F}_{q^m}^{(n - k) \times n}\) where \(\mathcal {C}= \{\boldsymbol{x} \in \mathbb {F}_{q^m}^{n}: \boldsymbol{H}\boldsymbol{x}^{\top } = \boldsymbol{0}^{\top } \}\)

We now continue by formally recalling the definition of the rank syndrome decoding (\(\textsf{RSD}\)) problem.

Definition 3

(\(\textsf{RSD}\) problem). Let q, m, n, k and r be positive integers. Let \(\boldsymbol{H} \overset{\;\$}{\longleftarrow }\mathbb {F}_{q^m}^{(n - k) \times n}\) and \(\boldsymbol{x} \overset{\;\$}{\longleftarrow }\mathbb {F}_{q^m}^n\) such that \(w_R\big (\boldsymbol{x}\big ) = r\). Let \(\boldsymbol{y}^{\top } = \boldsymbol{H} \boldsymbol{x}^{\top }\). Given \((\boldsymbol{H}, \boldsymbol{y})\), the computational \(\textsf{RSD}(q, m, n, k, r)\) problem asks to find a vector \(\tilde{\boldsymbol{x}} \in \mathbb {F}_{q^m}^n\) such that \(\boldsymbol{H}\tilde{\boldsymbol{x}}^\top = \boldsymbol{y}^{\top }\) and \(w_R\big (\tilde{\boldsymbol{x}}\big ) = r\).

We now introduce a variant of the above problem, the \(\textsf{RSD}_{\text {s}}\) problem and later argue that it is as hard as the standard \(\textsf{RSD}\) problem.

Definition 4

(\(\textsf{RSD}_{\text {s}}\) problem). Let q, m, n, k and r be positive integers. Let \(\boldsymbol{H} \overset{\;\$}{\longleftarrow }\mathbb {F}_{q^m}^{(n - k) \times n}\) and \(\boldsymbol{x} = (x_i) \overset{\;\$}{\longleftarrow }\mathbb {F}_{q^m}^n\) such that \(w_R\big (\boldsymbol{x}\big ) = r\), \(x_1 = 1\in \mathbb {F}_{q^m}\) and \(\langle x_1, \ldots , x_r \rangle _{\mathbb {F}_q} = \operatorname {Supp}{(\boldsymbol{x})}\). Let \(\boldsymbol{y}^{\top } = \boldsymbol{H} \boldsymbol{x}^{\top }\). Given \((\boldsymbol{H}, \boldsymbol{y})\), the computational \(\textsf{RSD}_{\text {s}}(q, m, n, k, r)\) problem asks to find a vector \(\tilde{\boldsymbol{x}} \in \mathbb {F}_{q^m}^n\) such that \(\boldsymbol{H}\tilde{\boldsymbol{x}}^\top = \boldsymbol{y}^{\top }\) and \(w_R\big (\tilde{\boldsymbol{x}}\big ) = r\).

The last problem we will rely on is the well-known \(\textsf{MinRank}\) problem:

Definition 5

(\(\textsf{MinRank}\) problem). Let q, m, n, k and r be positive integers. Let \(\boldsymbol{M}_1, \dots , \boldsymbol{M}_k, \boldsymbol{E} \in \mathbb {F}_{q}^{m\times n}\) and \(\boldsymbol{x} :=(x_1, \ldots , x_k) \in \mathbb {F}_q^k\) be uniformly sampled such that

Given \(\boldsymbol{M} ,\boldsymbol{M}_1\dots , \boldsymbol{M}_k\), the computational \(\textsf{MinRank}(q, m, n, k, r)\) problem asks to retrieve the vector \(\boldsymbol{x}\).

The last notion to recall is the Gilbert-Varshamov bound for the rank metric and for MinRank. This bound in rank metric has been introduced in [30]. It can be seen as the probable minimum weight of a random code.

Definition 6

(Rank Gilbert-Varshamov Bound). Let \(S_r\) be the number of elements of the sphere in \(\mathbb {F}_{q^m}^n\) of radius r centered in 0, i.e., the number of elements in \(\mathbb {F}_{q^m}^n\) of weight exactly r. We have \(S_0 = 1\), and for \(r \ge 1\),

Let \(B_r := \sum _{i=0}^{r} S_r\) be the number of elements of the ball in \(\mathbb {F}_{q^m}^n\) of radius r centered in 0. The Rank Gilbert-Varshamov (RGV) bound for an [n, k] linear code over \(\mathbb {F}_{q^m}\) is the smallest integer r such that

Using the approximation \(B_r \approx q^{(m+n-r)r}\), one can say the RGV bound is the smallest r such that \(m(n-k) \le (m-r)r+nr\). We call this value \(d_{\textsf{RGV}}\). The same bound exists for matrix codes (i.e., for \(\textsf{MinRank}\)) as they are simply \(\mathbb {F}_q\)-linear codes. Courtois described this bound in [17, Section 24.2], and it can also be derived from the one above easily (consider a \([m\times n,k]\) linear code over \(\mathbb {F}_q\) instead of [n, k] linear over \(\mathbb {F}_{q^m}\)). This bound is also mentioned in attacks on \(\textsf{MinRank}\) ([8, 9] for instance). Concretely, this states that, for an instance of \(\textsf{MinRank}\) with parameters (q, m, n, k, r), we do not expect to obtain more than one solution if r is chosen such that \(k+1 \le (m-r)(n-r)\).

Complexity of Attacks for Parameters on the GV Bound. For \(\textsf{RSD}\), the parameter r is taken as \(d_{\textsf{RGV}}-1\), i.e., the highest r such that \( (m-r)r+nr <m(n-k)\). With this parameter, if \(\boldsymbol{H}\) and \(\boldsymbol{y}\) were to be randomly sampled, one would expect to have a solution with probability \(q^{(m+n-r)r-m(n-k)}\). Since \(\boldsymbol{y}\) is set so there is a solution and since we are below RGV, it is not expected to have another solution. For \(\textsf{MinRank}\), we take parameters on the RGV bound, with \(k+1 = (m-r)(n-r)\). For \(k+1\) matrices randomly sampled (\(\boldsymbol{M}, \boldsymbol{M}_1,\dots ,\boldsymbol{M}_k\)), the probability to have a solution to the \(\textsf{MinRank}\) instance is \(q^{(m+n-r)r-(mn-k)}\). Since \(\boldsymbol{M}\) is set so that there is a solution and since we are on GV, it is not expected to have another solution for the instance. Let us now explain why in addition to having only one solution, it is important to take parameters according to these bounds. Since the combinatorial attacks from [34] for \(\textsf{RSD}\) and [26] for \(\textsf{MinRank}\), very few improvements have been made in the complexity. For \(\textsf{MinRank}\), the kernel attack is still the best combinatorial attack, and for \(\textsf{RSD}\), the exponential part of the complexities is still quadratic and has known almost no improvement for over 20 years (with the exception of [6], which slightly improved the complexity). Regarding the algebraic attacks, introduced in [7] and improved in [10] and [8], they managed to greatly reduce the complexity for the \(\textsf{RQC}\) and \(\textsf{LRPC}\) schemes. However, this came from the fact that these parameters were not on RGV. The attacked parameters were in \(\mathcal {O}\left( \sqrt{n-k}\right) \), which made them easier to attack, whereas we will consider parameters around the RGV bound, in \(\mathcal {O}\left( n \right) \). In practice, for parameters taken at the RGV bound, or just below, the algebraic attacks have roughly the same complexity as the combinatorial ones ( [8]). Overall, this means that, for parameters taken on the Rank Gilbert-Varshamov bound, the attacks have known no significant amelioration for the last 20 years.

We give here the well known reduction from \(\textsf{RSD}\) to \(\textsf{RSD}_{\text {s}}\), and then the attacks considered against \(\textsf{RSD}\) and \(\textsf{MinRank}\), which we will use in order to establish parameters for the signature schemes. We will also use these attacks in order to establish parameters to compare the different modelings in Sect. 4.

3.1 Security of the Rank Syndrome Decoding Problem

We deal here with the \(\textsf{RSD}\) problem, first by explaining the relation between \(\textsf{RSD}\) and \(\textsf{RSD}_{\text {s}}\), and then the attacks on \(\textsf{RSD}\).

Security Reduction. The \(\textsf{RSD}_{\text {s}}\) problem was most notably used in the \(\textsf{RQC}\) scheme in order to optimize it [31]. In the following, we show that the \(\textsf{RSD}_{\text {s}}\) problem is as hard as the standard \(\textsf{RSD}\) problem. More precisely, we show that any \(\textsf{RSD}\) instance can be solved by an \(\textsf{RSD}_{\text {s}}\) solver. This is the same reduction as in [6, 7, 34], and others, used to specialize some variables. We exhibit below the reduction which has not formally been described in previous works (as part of the folklore of rank-based cryptography).

Proposition 1

Let q, m, n, k, r be positive integers such that \(n > k\). Let \(\mathcal {A}_\text {s}\) be an algorithm which solves a \((q,m,n,k+1,r)\)-instance of the \(\textsf{RSD}_{\text {s}}\) problem in time t with success probability \(\varepsilon _s\). Then there exists an algorithm \(\mathcal {A}\) which solves a (q, m, n, k, r)-instance of the \(\textsf{RSD}\) problem in time t with probability \(\varepsilon \), where

under the assumption that the code \(\mathcal {C}\) associated to the parity-check matrix \(\boldsymbol{H}\) of the \(\textsf{RSD}\) instance contains no words of weight r.

Proof

See the full version [16].

Remark 1

In practice, the loss factor in Proposition 1 tends to 1 when q grows. For our considered parameters, with \(q=2\), its value is around 0.3. Moreover, one can get the average number of codewords of \(\mathcal {C}\) of weight r to justify our assumption. Let \(\mathcal {S}_r = \prod _{i=0}^{r-1}\frac{(q^n-q^i)(q^{m}-q^{i})}{q^{r}-q^{i}}\) be the number of words in \(\mathbb {F}_{q^m}^n\) of weight exactly r. Then, on average, there are \(\frac{S_r}{q^{m(n-k)}}\) words of rank r in the code. When below RGV, this makes the probability that a random code \(\mathcal {C}\) contains no codeword of weight r close to 1.

Remark 2

The best known attacks on \(\textsf{RSD}\) use the reduction to \(\textsf{RSD}_{\text {s}}\) in order to solve the instance [6, 8, 10, 34], meaning that in practice we consider the best attacks on \(\textsf{RSD}\) to evaluate the security of \(\textsf{RSD}_{\text {s}}\).

3.2 Parameters Choice for \(\textsf{RSD}_{\text {s}}\)

Because of the space constraints, we recall the best attacks on \(\textsf{RSD}\) in the full version [16]. According to these attacks, we give in Table 3 the parameters which we will use for our \(\textsf{RSD}_{\text {s}}\) instances.

3.3 Parameters Choice for \(\textsf{MinRank}\)

Because of the space constraints, we recall the attacks on \(\textsf{MinRank}\) in the full version [16]. According to these attacks, we give in Table 4 the parameters which we will use for our \(\textsf{MinRank}\) instances.

A zero-knowledge proof constructed using the MPCitH paradigm is composed of two parts, a “symmetric part” made of GGM trees (or Merkle trees) and an “arithmetic part” composed of the open party views and broadcast shares of the MPC protocol. While for a given security level the symmetric part is of rather fixed size (e.g., around 2kB for GGM trees and 4kB for Merkle trees at a 128-bit security level), the arithmetic part depends on the modeling (i.e., the way the problem instance is verified) and the associated MPC protocol. For the recent TCitH and VOLEitH techniques, the arithmetic part is actually mainly impacted by the size of the witness, which favors modelings with low-size witnesses.

In this section, we study different modelings for \(\textsf{RSD}\) and \(\textsf{MinRank}\) with respect to the witness size criterion. For the \(\textsf{RSD}\) problem, we recall the permuted secret, q-polynomial and Kipnis-Shamir modelings. We propose an other modeling, named dual support decomposition, which can be seen as an improvement of the rank decomposition from [20]. We also slightly improve all the modelings by relying on the \(\textsf{RSD}_{\text {s}}\) variant. For the \(\textsf{MinRank}\) problem, we recall the q-polynomial and Kipnis-Shamir modelings and propose an adaptation of the dual support decomposition modeling for \(\textsf{MinRank}\).

4.1 Modelings for the \(\textsf{RSD}_{\text {s}}\) Problem

Permuted Secret. We start by recalling the permuted secret technique, which was used for \(\textsf{RSD}\) in [15]. The idea of this technique consists in revealing a “permuted” and a “masked” versions of the secret: let us denote \(\sigma \) an isometry in the rank metric (such a isometry consists of multiplying the secret matrix by a invertible matrices on both sides) and \(\boldsymbol{u}\) a vector of the left kernel of \(\boldsymbol{H}\), one reveals \(\boldsymbol{v} := \sigma (\boldsymbol{x})\) and \(\boldsymbol{\tilde{x}} := \boldsymbol{x} + \boldsymbol{u}\) and the goal is to find such values \(\sigma \) and \(\boldsymbol{u}\). More precisely, the rank syndrome decoding problem consists, from two vectors \(\boldsymbol{v},\boldsymbol{\tilde{x}}\in \mathbb {F}_{q^m}^n\) satisfying \(w_R(\boldsymbol{v}) = r\) and \(\boldsymbol{H}\boldsymbol{\tilde{x}}^{\top }=\boldsymbol{y}^\top \), in finding an isometry \(\sigma \) and a vector \(\boldsymbol{u}\in \mathbb {F}_{q^m}^n\) such that

Indeed, if we get both \(\sigma \) and \(\boldsymbol{u}\), we can easily restore the initial secret as \(\boldsymbol{x} := \boldsymbol{\tilde{x}}-\boldsymbol{u}\): we have \(\boldsymbol{H}\boldsymbol{x}^{\top } = \boldsymbol{y}^\top - \boldsymbol{0}^\top \) and \(w_R(\boldsymbol{x}) = w_R(\sigma (\boldsymbol{x})) = w_R(\sigma (\boldsymbol{\tilde{x}}) - \sigma (\boldsymbol{u})) = w_R(\boldsymbol{v}) = r\).

Unfortunately, this modeling is not compatible with the recent MPCitH techniques as TCitH or VOLEitH. Such techniques requires at least additive sharings over a commutative group (or for the more recent techniques, Shamir’s secret sharing over a ring). However, the isometry \(\sigma \) lives in a non-commutative group, so it requires to rely on a special form of MPCitH named the shared-permutation framework [15, 21].

Rank Decomposition. The Rank Decomposition protocol proposed in [20] aims to verify the rank of the witness by using the rank decomposition theorem. In this modeling, the rank syndrome decoding problem consists in finding a vector \(\boldsymbol{x}\in \mathbb {F}_{q^m}^n\) and two matrices \(\boldsymbol{T} \in \mathbb {F}_q^{m\times r}\) and \(\boldsymbol{R} \in \mathbb {F}_q^{r \times n}\) such that

where \(\boldsymbol{X} \in \mathbb {F}_q^{m\times n}\) is the matrix associated to \(\boldsymbol{x}\). Concretely, the MPC protocol takes as input some shares of \(\boldsymbol{x}\), of \(\boldsymbol{T}\) and of \(\boldsymbol{R}\). The protocol then checks that \(\boldsymbol{X} = \boldsymbol{T}\boldsymbol{R}\), where the shares of \(\boldsymbol{X}\) is derived from those of \(\boldsymbol{x}\). Using the standard representation \(\boldsymbol{H} = \begin{pmatrix} \boldsymbol{I_{n-k}} \vert \vert \boldsymbol{H}'\end{pmatrix}\), one can send only the right part of \(\boldsymbol{x}\) of size k, denoted as \(\boldsymbol{x_B}\). Furthermore, it is possible to send one less column of the matrix \(\boldsymbol{T}\), since \(1 \in \operatorname {Supp}{(\boldsymbol{x})}\) (see [4] for the optimization) and as a result the size of witness is (in bits):

q-Polynomial. The q-polynomial technique proposed in [20] to check the rank metric constitutes an improvement compared to a number of previous methods. Let us first recall the definition of a q-polynomial.

Definition 7

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

The roots of a q-polynomial of q-degree r form a linear subspace of \(\mathbb {F}_{q^m}\) of dimension at most r. Moreover, for each linear subspace of \(\mathbb {F}_{q^m}\) of dimension at most r, there exists a unique monic q-polynomial of q-degree r annihilating all the elements of the subspace. Let \(\boldsymbol{x} = (x_1, \ldots , x_n) \in \mathbb {F}_{q^m}^n\) of rank \(w_R\big (\boldsymbol{x}\big ) = r\) and let \(P_{\boldsymbol{x}}(X)\) the monic q-polynomial annihilating \(\operatorname {Supp}{(\boldsymbol{x})}\). In this modeling, the rank syndrome decoding problem consists in finding a vector \(\boldsymbol{x}\in \mathbb {F}_{q^m}^n\) and a q-polynomial \(P_{\boldsymbol{x}}\in \mathbb {F}_{q^m}[X]\) of q-degree r such that

Concretely, the MPC protocol based on the q-polynomial technique takes as input some shares of \(\boldsymbol{x}\) and some shares of \(P_{\boldsymbol{x}}(X)\). The protocol then checks that \(P_{\boldsymbol{x}}(x_i) = 0\) for all \(i \in [1, n]\). As previously, one can send only the right part of \(\boldsymbol{x}\) of size k using the standard representation of \(\boldsymbol{H}\). Furthermore, it is possible to send one less coefficient of the polynomial \(P_{\boldsymbol{x}}\) when relying on \(\textsf{RSD}_{\text {s}}\). As a result the size of witness is (in bits):

This modeling based on q-polynomials currently leads to the shortest communications for \(\textsf{RSD}\) when considering linear multiparty computation, but it is not the best one when considering non-linear multiparty computation as in the new MPCitH frameworks.

Kipnis-Shamir. Historically, the Kipnis-Shamir modeling was introduced in the cryptanalysis of the \(\textsf{MinRank}\) problem [29]. We can use the same idea to have a modeling of \(\textsf{RSD}\). It consists in giving the right-kernel of the matrix of \(\boldsymbol{x}\). We denote this matrix in \(\mathbb {F}_q^{m\times n}\) by \(\boldsymbol{X}\). If \(w_R\big (\boldsymbol{x}\big ) = r\), then the right-kernel of \(\boldsymbol{X}\) is of dimension \(n-r\) and can be represented by an \(r \times (n-r)\) matrix.

In the \(\textsf{RSD}_{\text {s}}\) case, the witness is composed of \(\boldsymbol{x}\) and of the matrix \(\boldsymbol{A} \in \mathbb {F}_q^{r\times (n-r)}\). The MPC protocol takes as input \(\boldsymbol{K} = \begin{pmatrix} \boldsymbol{I_{n-r}}\\ \boldsymbol{A}\\ \end{pmatrix}\), and then checks that \(\boldsymbol{X}\boldsymbol{K} = \boldsymbol{0}\). It is possible to send only \(\boldsymbol{x_B}\), as previously with q-polynomials, and since 1 is in the support, the size of the witness is:

Note that transmitting \(\boldsymbol{A}\) costs \((r-1)\cdot (n-r)\) only since we know that 1 is in \({\boldsymbol{x}}\). This approach is slightly better than the q-polynomial technique in terms of witness size.

Dual Support Decomposition. Finally, we introduce an other modeling for \(\textsf{RSD}_{\text {s}}\), using only the support and the coordinates. This can be seen as an improvement of the rank decomposition from [20], as our new modeling does not rely on having \(\boldsymbol{x_B} \in \mathbb {F}_{q^m}^k\) as input. To that end, one has as inputs:

• The support of \(\boldsymbol{x}\), \(\operatorname {Supp}{(\boldsymbol{x})} = \langle 1, x_2,\dots ,x_r\rangle \);

• The coordinates of \(\boldsymbol{x}\) in this basis, i.e., \(\boldsymbol{C} \in \mathbb {F}_q^{r \times (n-r)}\) such that

  $$(1,x_2,\dots ,x_r) \cdot \begin{pmatrix} \boldsymbol{I_r} & \boldsymbol{C} \end{pmatrix} = (1,x_2,\dots ,x_n) =\boldsymbol{x}$$

More precisely, in this modeling, the \(\textsf{RSD}_{\text {s}}\) problem consists in finding \(x_2,\ldots ,x_r\in \mathbb {F}_{q^m}\) and \(\boldsymbol{C}\in \mathbb {F}_q^{r \times (n-r)}\) such that

Concretely, after computing \(\boldsymbol{x}= (x_1,\dots ,x_r) \cdot \begin{pmatrix} \boldsymbol{I_r} & \boldsymbol{C} \end{pmatrix} \), one verifies that \(\boldsymbol{H}\boldsymbol{x}^T\) is indeed equal to \(\boldsymbol{y}^T\). Since 1 is in the support of \(\boldsymbol{x}\), it is possible to transmit only \(r-1\) elements for \(\operatorname {Supp}{(\boldsymbol{x})}\), and we can have a gain on the matrix \(\boldsymbol{C}\) as well since the r first coordinates are linearly independent. This results in an efficient protocol, where the inputs are of size

We see here that the input size does not depend on k anymore, allowing us to take more efficient parameters.

Global Comparison. Table 5 provides a global comparison of the different modelings in terms of witness size for the \(\textsf{RSD}\) problem. For each of the described modelings, we provide the size formula as well as the obtained concrete size for optimized parameters reaching a 128-bit security according to the attacks in Sect. 3.2.

4.2 Modelings for the \(\textsf{MinRank}\) Problem

The \(\textsf{MinRank}\) problem is closely related to the \(\textsf{RSD}\) problem. The two problems indeed share a number of similarities as evidence of the algebraic attacks applying to both problems (see, e.g., [8, 10]). Quite naturally, most of the above modelings for \(\textsf{RSD}\) can be adapted for \(\textsf{MinRank}\).

Rank Decomposition. Similar to \(\textsf{RSD}_{\text {s}}\), the Rank Decomposition protocol was introduced in [20]. This protocol takes as input (shares of) \(\boldsymbol{x} \in \mathbb {F}_q^k\), \(\boldsymbol{T} \in \mathbb {F}_q^{m\times r}\), and \(\boldsymbol{R} \in \mathbb {F}_q^{r \times n}\). Then, after building \(\boldsymbol{E} = \boldsymbol{M}+\sum _{i=1}^{k} x_i\boldsymbol{M}_i\), the protocol checks that \(\boldsymbol{E} = \boldsymbol{T}\boldsymbol{R}\). This leads to a witness size (in bits) of

q-Polynomial. The q-polynomial technique of [20] can be also applied to \(\textsf{MinRank}\): the witness is composed of the shares of \(\boldsymbol{x}\in \mathbb {F}_q^k\) and the coefficients \(\boldsymbol{\beta } \in \mathbb {F}_{q^m}^r\) of the q-polynomial associated to \(\boldsymbol{E}\). The MPC protocol computes \(\boldsymbol{E}= \boldsymbol{M}+ \sum _{i=1}^{k} x_i \boldsymbol{M}_i\) and verifies that \(P_{\boldsymbol{E}}(X) := \sum _{i=0}^{r-1}\beta _iX^{q^i}+X^{q^r}\) is the annihilator polynomial of \(\boldsymbol{E}\). This verification relies on the isomorphism between \(\mathbb {F}_{q^m}\) and \(\mathbb {F}_q^m\), and associates each column of \(\boldsymbol{E}\), denoted as \(\boldsymbol{e}_i\), to an element of \(\mathbb {F}_{q^m}\), \(e_i\). The protocol hence simply checks that \(P_{\boldsymbol{E}}(e_i) = 0\) for \(i\in [1, n]\).

With this modeling, the size of the witness size is (in bits):

Kipnis-Shamir. This is the modeling used in MiRitH [1], which is an improvement of MinRank-in-the-Head [2]. The goal of this modeling is to use the right kernel of \(\boldsymbol{E}\) in order to prove its rank. Let \(\boldsymbol{K} = \begin{bmatrix} \boldsymbol{I_{n-r}}\\ \boldsymbol{A}\\ \end{bmatrix}\) a matrix of rank \(n-r\) representing the right kernel of \(\boldsymbol{E}\). The witness is composed of \(\boldsymbol{x}\) and \(\boldsymbol{A} \in \mathbb {F}_q^{r\times (n-r)}\). The protocol recomputes \(\boldsymbol{E} = \boldsymbol{M} + \sum _{i=1}^{k} x_i \boldsymbol{M}_i\) and verifies that \(\boldsymbol{E}\cdot \boldsymbol{K} = \boldsymbol{0}\). If the verification succeeds, one deduces that \(\boldsymbol{E}\) is indeed of rank r since it has a kernel of rank \(n-r\).

With this modeling, the witness is of size:

As for \(\textsf{RSD}_{\text {s}}\), the witness is smaller with this modeling than with the q-polynomials technique.

New Modeling for the \(\textsf{MinRank}\) Problem: Dual Support Decomposition. We introduce hereafter a new MPCitH modeling for the \(\textsf{MinRank}\) problem which achieves smaller witness sizes than the previous modelings. To build our modeling, we will rely on an alternative formulation of this problem, namely, its syndrome version, which has not been previously used to build cryptosystems. More precisely, this problem can be expressed in a syndrome decoding way by using the dual of the matrix code generated by \(\boldsymbol{M}_1, \dots , \boldsymbol{M}_k\). First, one can define the map

The generator matrix of the code \(\langle \boldsymbol{M}_1, \dots , \boldsymbol{M}_k \rangle \) is the matrix \(\boldsymbol{G} \in \mathbb {F}_q^{k\times mn}\) whose lines are \(\rho (\boldsymbol{M}_1),\dots ,\rho (\boldsymbol{M}_k)\), i.e.,

Solving the \(\textsf{MinRank}\) problem then consists, given \(\boldsymbol{G}\) and \(\boldsymbol{M}\), in finding \(\boldsymbol{x}\) and \(\boldsymbol{E}\) such that \(\rho (\boldsymbol{M}) = -\boldsymbol{x}\boldsymbol{G} + \rho (\boldsymbol{E})\) and \(\textsf {rank}(\boldsymbol{E}) \le r\). The dual matrix of this code is, as usual, a full-rank matrix \(\boldsymbol{H} \in \mathbb {F}_q^{(mn-k)\times mn}\) such that \(\boldsymbol{G}\boldsymbol{H}^\top = \boldsymbol{0}\). Then, the \(\mathsf {MinRank~Syndrome}\) problem can be defined by applying \(\boldsymbol{H}^\top \) in the linear constraint: given \(\boldsymbol{H}\) and \(\boldsymbol{y} := \rho (\boldsymbol{M})\boldsymbol{H}^\top \), the \(\mathsf {MinRank~Syndrome}\) problem consists in finding \(\boldsymbol{E}\) such that \(\boldsymbol{y} = \boldsymbol{0} + \rho (\boldsymbol{E}) \boldsymbol{H}^\top \) and \(\textsf {rank}(\boldsymbol{E}) \le r\).

Definition 8

(\(\mathsf {MinRank~Syndrome}\) problem). Let q, m, n, k and r be positive integers. Let \(\boldsymbol{H} := \begin{bmatrix} \boldsymbol{I_{mn-k}} & \boldsymbol{H'} \end{bmatrix} \in \mathbb {F}_q^{(mn-k) \times mn}\) where \(\boldsymbol{H'} \in \mathbb {F}_q^{(mn-k)\times k}\), and \(\boldsymbol{y} \in \mathbb {F}_q^{mn-k}\). The \(\mathsf {MinRank~Syndrome}\) problem asks to find \(\boldsymbol{E}\) such that \(\rho (\boldsymbol{E})\boldsymbol{H}^\top = \boldsymbol{y}\) and \(\textsf{rank}(\boldsymbol{E}) \le r\).

Proposition 2

The \(\textsf{MinRank}\) problem and the \(\mathsf {MinRank~Syndrome}\) problem are equivalent.

Proof

The proof is similar to the proof of equivalence between the decoding problem and the syndrome decoding problem for the Hamming metric.

• Let us explain how to solve a \(\mathsf {MinRank~Syndrome}\) instance \((\boldsymbol{H},y)\) using a \(\textsf{MinRank}\) solver. The first step consists in finding a solution \(\rho (\boldsymbol{M})\) to the linear system \(\rho (\boldsymbol{M}) \boldsymbol{H}^\top = \boldsymbol{y}\) without any constraint on the rank of \(\boldsymbol{M}\). Then, we consider a dual matrix \(\boldsymbol{G}\) of \(\boldsymbol{H}\), where we interpret each row as a flatten matrix among \(\boldsymbol{M}_1, \ldots , \boldsymbol{M}_k\). We can then find \(\boldsymbol{x}\) and \(\boldsymbol{E}\) such that \(\boldsymbol{M} + \sum _{i=1}^{k} x_i\boldsymbol{M}_i = \boldsymbol{E}\) and \(\textsf{rank}(\boldsymbol{E}) \le r\) using the \(\textsf{MinRank}\) solver. Such an \(\boldsymbol{E}\) is directly a solution of our \(\mathsf {MinRank~Syndrome}\) instance, since

  $$\rho (\boldsymbol{E})\boldsymbol{H}^\top = [-\boldsymbol{x}\boldsymbol{G} + \rho (\boldsymbol{E})]\boldsymbol{H}^\top = \rho (\boldsymbol{M})\boldsymbol{H}^\top = \boldsymbol{y}.$$

• Let us now explain how to solve a \(\textsf{MinRank}\) instance \((\boldsymbol{M},\boldsymbol{M}_1,\ldots ,\boldsymbol{M}_k)\) using a MinRank Syndrome solver. First, we can build the dual matrix \(\boldsymbol{H}\) from \(\boldsymbol{M}_1,\ldots ,\boldsymbol{M}_k\), such that \(\boldsymbol{G}\boldsymbol{H}^\top = \boldsymbol{0}\) where the rows of \(\boldsymbol{G}\) are defined as \(\rho (\boldsymbol{M}_1), \ldots , \rho (\boldsymbol{M}_k)\). We can then find \(\boldsymbol{E}\) such that \(\rho (\boldsymbol{E})\boldsymbol{H}^\top = \rho (\boldsymbol{M})\boldsymbol{H}^\top \) and \(\textsf{rank}(\boldsymbol{E}) \le r\) using the MinRank Syndrome solver (defining the syndrome as \(\boldsymbol{y} = \rho (\boldsymbol{M})\boldsymbol{H}^\top \)). Therefore, \(\rho (\boldsymbol{E}-\boldsymbol{M})\) is in the right kernel of \(\boldsymbol{H}\), for which a basis is described by the rows of \(\boldsymbol{G}\). By Gaussian elimination, we can thus find \(\boldsymbol{x}\) such that \(\rho (\boldsymbol{E}-\boldsymbol{M}) = \boldsymbol{x}\boldsymbol{G}\), i.e., such that \(\rho (\boldsymbol{E}-\boldsymbol{M}) = \sum _{i=1}^k x_i \cdot \rho (\boldsymbol{M}_i)\). Such an \(\boldsymbol{x}\), together with \(\boldsymbol{E}\), forms a solution of our \(\textsf{MinRank}\) instance.

\(\square \)

In the Dual Support Decomposition modeling, we rely on the MinRank Syndrome problem instead of the standard \(\textsf{MinRank}\) problem. In this modeling, the protocol aims at verifying that a matrix \(\boldsymbol{E}\) is solution of the constraints \(\rho (\boldsymbol{E})\boldsymbol{H}^\top = \boldsymbol{y}\) and \(\textsf{rank}(\boldsymbol{E}) \le r \) for some \(\boldsymbol{H} \in \mathbb {F}_q^{(mn-k) \times mn}\) and \(\boldsymbol{y} \in \mathbb {F}_q^{mn-k}\). As in the rank decomposition method from [20], one can view \(\boldsymbol{E}\) as a product of two matrices, \(\boldsymbol{E} = \boldsymbol{S}\boldsymbol{C}\), with \(\boldsymbol{S} \in \mathbb {F}_q^{m\times r}\) and \(\boldsymbol{C} \in \mathbb {F}_q^{r \times n}\). Furthermore, one can write without loss of generality \(\boldsymbol{S}\) as \(\begin{bmatrix} \boldsymbol{I_r}\\ \boldsymbol{S}'\\ \end{bmatrix}\) for some matrix \(\boldsymbol{S}' \in \mathbb {F}_q^{(m-r) \times r}\) (this is always possible up to a permutation of the lines). Then, one can simply set \(\boldsymbol{E} =\begin{bmatrix} \boldsymbol{I_r}\\ \boldsymbol{S}'\\ \end{bmatrix} \cdot \boldsymbol{C}\). Therefore, given \(\boldsymbol{S'}\) and \(\boldsymbol{C}\), the protocol simply checks:

The use of the dual form of the \(\textsf{MinRank}\) matrix code makes a significant difference compared to the Rank Decomposition, as the scheme now avoids relying on the vector \(\boldsymbol{x} \in \mathbb {F}_q^k\), leading to a much smaller witness. Overall, with the identity in \(\boldsymbol{S}\), the inputs are of size

As for \(\textsf{RSD}\), the size does not depend on k anymore, which allows a better selection of the parameters.

Global Comparison. Table 6 provides a global comparison of the different modelings in terms of witness size for the \(\textsf{MinRank}\) problem. For each of the described modelings, we provide the size formula as well as the obtained concrete size for optimized parameters reaching a 128-bit security for the attacks described in Sect. 3.3.

The MPCitH paradigm [27] is a versatile method introduced in 2007 to build zero-knowledge proof systems using techniques from secure multi-party computation (MPC). This paradigm has been drastically practically improved in recent years (see, e.g., [3, 19, 23, 28]) and is particularly efficient to build zero-knowledge proofs for small circuits such as those involved in (post-quantum) signature schemes. The MPCitH paradigm can be summarized as follows. The prover emulates “in his head” an \(\ell \)-private MPC protocol with N parties and commits each party’s view independently. The verifier then challenges the prover to reveal the views of a random subset of \(\ell \) parties. By the privacy of the MPC protocol, nothing is revealed about the plain input, which implies the zero-knowledge property. On the other hand, a malicious prover needs to cheat for at least one party, which shall be discovered by the verifier with high probability, hence ensuring the soundness property.

In what follows, we describe two recently introduced MPCitH-based frameworks, namely the VOLE-in-the-Head (VOLEitH) framework from [12] and the Threshold-Computation-in-the-Head (TCitH) framework from [22, 23]. We then present the recent optimisations proposed by [11].

5.1 Threshold-Computation-in-the-Head Framework

The TCitH framework has been recently introduced in [22] as an extension of a previous work [23] published at Asiacrypt 2023. While almost all the former MPCitH-based proof system relied on additive sharings, the TCitH framework shows how using Shamir’s secret sharings (instead of additives sharings) lead to faster schemes with shorter communication.

We refer the reader to [22, 23] for a detailed exposition of the TCitH framework which is only briefly abstracted here. In a nutshell, the TCitH framework relies on MPC protocols with broadcasting, randomness oracle and hint oracle (as previous MPCitH schemes) but using Shamir’s secret sharing unlocks the use of non-linear multiparty computation (whereas previous MPCitH schemes are based on linear multiparty computation). More precisely, in the considered MPC protocols, one can compute a sharing \([\![ a\cdot b ]\!]\) of a product \(a\cdot b\) from the sharings \([\![ a ]\!]\) and \([\![ b ]\!]\) of the operands by share-wise multiplication (for all i, \([\![ a \cdot b ]\!]_i \leftarrow [\![ a ]\!]_i \cdot [\![ b ]\!]_i\)).

The TCitH framework comes with two variants depending on how one commits the input shares: either relying on GGM trees [25] or on Merkle trees [32]. In the present work, we focus on the GGM-tree variant which leads to shorter signature sizes for the considered statements. Moreover, we only consider 1-private Shamir’s secret sharings, i.e. \(\ell =1\), which gives the best results in our context.

Given some degree-d polynomials \(f_1, \ldots , f_m\) from \(\mathbb {F}[X_1,\ldots ,X_{|w|}]\), we want a zero-knowledge proof of knowledge of a witness w satisfying

We shall use the proof system TCitH-\(\varPi _{\textsc {pc}}\) described in [22, Section 5.2]. We recall the underlying MPC protocol \(\varPi _{\textsc {pc}}\) in Protocol 1. The sharing \([\![ 0 ]\!]\) used in Step 4 of the MPC protocol is a publicly-known degree-1 sharing of zero (for example, \([\![ 0 ]\!]_i=\omega _i\) when \(e=0\)). This MPC protocol is \(\ell \)-private and sound with false positive probability \(\frac{1}{|\mathbb {F}|}\) (see [22, Lemma 2]). In practice, the MPC protocol is repeated \(\rho \) times in parallel to achieve a false positive probability of \(\frac{1}{|\mathbb {F}|^\rho }\). The soundness error of TCitH-\(\varPi _{\textsc {pc}}\) (when \(\ell =1\)) is

To obtain a signature scheme, we first transform the above MPC protocol into a proof of knowledge (PoK) of soundness error \(\epsilon \) by applying the TCitH transform. We then perform \(\tau \) parallel repetitions of this PoK and apply the Fiat-Shamir transform [24]. To achieve a \(\lambda \)-bit security, we take the number \(\rho \) of MPC repetitions such that \(\frac{1}{|\mathbb {F}|^\rho } \le 2^{-\lambda }\) and the number \(\tau \) of PoK repetitions such that \(\left( \frac{d}{N}\right) ^\tau \le 2^{-\lambda }\).

The proof transcript (i.e. the signature) includes:

• The opened shares \([\![ w ]\!]_I\) of the witness \(w\in \mathbb {F}^{|w|}\), for each of the \(\tau \) PoK repetitions. In practice, the sent values are the auxiliary values \(\Delta w\).

• The opened shares of \([\![ v ]\!]_I\): because v is uniformly-sampled, these shares are communication-free since we rely on the TCitH-GGM variant.

• The degree-d sharing \([\![ \alpha ]\!]\), for each of the \(\rho \) MPC repetitions of the \(\tau \) PoK repetitions. Since \([\![ \alpha ]\!]_I\) can be recomputed by the verifier and since the \(\alpha \) should be zero, the prover just needs to send \((d+1)-1-1 = (d-1)\) shares.

• The sibling paths in the GGM trees, together with the unopened seed commitments.

Moreover, the signature includes a \(2\lambda \)-bit salt and a \(2\lambda \)-bit commitment digest that correspond to the last verifier challenge (in the Fiat-Shamir heuristic). Therefore, the signature size when using the TCitH framework in the above setting is (in bits):

5.2 VOLE-in-the-Head Framework

The VOLEitH framework has been introduced at Crypto 2023 [12]. This work provides a way to compile any zero-knowledge protocol in the VOLE-hybrid model into a publicly verifiable protocol. While it has not been introduced as a MPCitH construction, it can yet be interpreted as such. Specifically, [22] shows that the VOLEitH framework can be described in the TCitH syntax. Indeed, this framework is similar to the TCitH framework with \(\ell =1\) and GGM trees, up to several details:

• The secret is stored at \(P(\infty )\) when sharing, meaning that \(e=\infty \). As a result, to share a value v, one samples a random value r and builds the Shamir’s polynomial P as \(P(X) := v X + r\). While multiplying two Shamir’s sharings when \(e=\infty \) is similar than when \(e\not =\infty \), the addition operation is slightly different: to add two Shamir’s sharings \([\![ a ]\!]\) and \([\![ b ]\!]\) of degrees respectively \(d_1\) and \(d_2\) (such that \(d_1\le d_2\)) when \(e=\infty \), the parties can compute the following \(d_2\)-degree sharing

  $$\forall i,~ [\![ a+b ]\!]_i \leftarrow [\![ a ]\!]_i\cdot \omega _i^{d_2-d_1} + [\![ b ]\!]_i,$$

  where \(\omega _i\) is the evaluation point of the i^th party.

• The VOLEitH framework relies on a large field embedding: in the commitment phase, the prover commits \(\tau \) N-sharings \([\![ w ]\!]^{(1)},\ldots ,[\![ w ]\!]^{(\tau )}\) of the witness w. In the basic TCitH framework, the prover runs \(\tau \) MPC protocols in parallel, each of them on a different sharing \([\![ w ]\!]^{(j)}\). In the VOLEitH framework, these N sharings are merged to obtain a \(N^\tau \)-sharing \([\![ w ]\!]^{(\phi )}\) living in a large field extension \(\mathbb {K}\) such that the extension degree \([\mathbb {K}:\mathbb {F}]\) is \(\rho \), then the prover runs a unique MPC protocol which takes as input this \(N^\tau \)-sharing. More precisely, the i^th share of \([\![ w ]\!]^{(\phi )}\) is computed as

  $$[\![ w ]\!]^{(\phi )}_i \leftarrow \phi \left( [\![ w ]\!]^{(1)}_{i_1},\ldots ,[\![ w ]\!]^{(\tau )}_{i_\tau }\right) $$

  where \(i_1,\ldots ,i_\tau \in [1,N]\) satisfy \((i-1)=(i_1-1)+(i_2-1)\cdot N + \ldots + (i_\tau -1)\cdot N^{\tau -1}\) and \(\phi \) is an one-to-one ring homomorphism between \(\mathbb {F}^\tau \) and \(\mathbb {K}\) (\(\rho \ge \tau \)). If the sharings \([\![ w ]\!]^{(1)},\ldots ,[\![ w ]\!]^{(\tau )}\) encode the same witness w, then we get that \([\![ w ]\!]^{(\phi )}\) is a valid Shamir’s secret sharing of w for which the evaluation point of the i^th party is \(\phi (\omega _{i_1},\ldots ,\omega _{i_\tau })\) (with \(\omega _i\) the i^th party evaluation point in the standard TCitH setting). The main advantage of this large field embedding is that the resulting soundness error of the proof system is \(\frac{d}{N^\tau }\) instead of being \(\left( \frac{d}{N}\right) ^\tau \) (up to the false positive probability).

• The above optimisation requires that the prover ensures that the \(\tau \) sharings encode the same value (without revealing this value). To ensure this property, the VOLEitH framework introduces an additional prover-verifier pair of rounds. After committing the input shares (including the hint sharings),

  • the prover commits \(\tau \) additional uniformly-random sharings \([\![ u ]\!]^{(1)}\),..., \([\![ u ]\!]^{(\tau )}\) of the same random value \(u\in \mathbb {F}^{\rho +B}\), for \(B\ge 0\) an additional parameter,

  • the verifier sends a challenge \((H_1|H_2)\in \mathbb {F}^{(\rho +B)\times (n+\rho )}\),

  • for all \(j\in [1,\tau ]\), the prover reveals the digest sharing \([\![ \alpha ' ]\!]^{(j)} := H_1[\![ w ]\!]^{(j)} + H_2 [\![ v ]\!]^{(j)} + [\![ u ]\!]^{(j)}\), where \(\alpha '\in \mathbb {F}^{\rho +B}\).

  The idea behind this process is that the prover computes the digests of all the plain values encoded in \([\![ w ]\!]^{(1)},\ldots ,[\![ w ]\!]^{(\tau )}\) (and in \([\![ v ]\!]^{(1)},\ldots ,[\![ v ]\!]^{(\tau )}\)) and compares them. If \(([\![ w ]\!]^{(i)},[\![ v ]\!]^{(i)})\) and \(([\![ w ]\!]^{(j)},[\![ v ]\!]^{(j)})\) encode different values, then their digests \([\![ \alpha ' ]\!]^{(i)}\) and \([\![ \alpha ' ]\!]^{(j)}\) will differ with high probability. In practice, the parameters \(\rho \) and B are chosen such that the probability that two different plain values lead to the same digest is negligible. We further note that taking \((H_1|H_2)\) uniformly at random gives the smallest probability but requires to perform matrix-vector multiplications. Other strategies are possible for \((H_1|H_2)\) such as relying on a polynomial-based hash: this increases a bit the collision probability (so one needs to increase B to compensate) but lightens the computation. This strategy is used in the FAEST signature scheme [13].

We use the VOLEitH framework with the same MPC protocol than with the TCitH framework, namely the MPC protocol \(\varPi _{\textsc {pc}}\) described in Protocol 1, which is equivalent to the QuickSilver VOLE-based protocol [39] in the VOLE setting. The publicly-known degree-1 sharing \([\![ 0 ]\!]\) in Protocol 1 when \(e=\infty \) can be built as \([\![ 0 ]\!]_i=1\) for all i.

To achieve a PoK with \(\lambda \)-bit security (i.e. \(2^{-\lambda }\) soundness error), we take the field extension \(\mathbb {K}\) of degree \(\rho \) such that \(\frac{1}{|\mathbb {F}|^\rho } \le 2^{-\lambda }\), the number \(\tau \) of sharings \([\![ w ]\!]^{(j)}\) such that \(\frac{d}{N^\tau } \le 2^{-\lambda }\) and the additional parameter B such^{Footnote 3} that \(B\cdot \log _2 |\mathbb {F}| \ge 16\) (the latter choice corresponds to the choice in the specification of FAEST [13]). Then we obtain a signature scheme by applying the Fiat-Shamir transform [24] as previously.

The proof transcript (i.e. the signature) includes:

• The opened shares \([\![ w ]\!]_I\) of the witness \(w\in \mathbb {F}^{|w|}\). In practice, one sends the auxiliary values of the sub-sharings \([\![ w ]\!]^{(1)},\ldots ,[\![ w ]\!]^{(\tau )}\).

• The opened shares of \([\![ v ]\!]_I\). When v is uniformly-sampled, the shares are usually communication-free. However, we need \(\tau \) sub-sharings of the same (uniformly-random) value v. While the first sharing is communication-free, the \(\tau -1\) others require an auxiliary value to ensure that all the sub-sharings encode the same value.

• The degree-d sharing \([\![ \alpha ]\!]\), for the single MPC execution. Since \([\![ \alpha ]\!]_I\) can be recomputed by the verifier and since the \(\alpha \) should be zero, the prover just needs to send \((d+1)-1-1 = d-1\) shares.

• The sibling paths in the GGM trees, together with the unopened seed commitments.

• The opened shares \([\![ u ]\!]_I\). As for \([\![ v ]\!]_I\), since all the \(\tau \) sub-sharings must encode the same random value u, only the first sharing is communication-free and the \(\tau -1\) others require an auxiliary value.

• The degree-1 sharings \([\![ \alpha ' ]\!]^{(1)},\ldots ,[\![ \alpha ' ]\!]^{(\tau )}\). Since the plaintext value \(\alpha '\) is the same for all these sharings and since \([\![ \alpha ]\!]^{(j)}_I\) can be recomputed by the verifier for all j, sending all these sharings costs only \((\rho +B)\) field elements.

Moreover, the signature includes a \(2\lambda \)-bit salt and a \(2\lambda \)-bit commitment digest that correspond to the last verifier challenge (in the Fiat-Shamir heuristic). Therefore, the signature size when using the VOLEitH framework is (in bits):

5.3 Additional MPCitH Optimisations

New generic optimizations for MPCitH-based schemes relying on GGM trees have been proposed in a recent work [11]. The improvements are threefold:

1. 1.

   Instead of considering \(\tau \) independent GGM trees of N leaves in parallel, the authors propose to rely on a unique large GGM tree of \(\tau \cdot N\) leaves where the i^th share of the e^th PoK repetition is associated to the \((e\cdot N + i)\)^th leaf of the large GGM tree. As explained in [11], “opening all but \(\tau \) leaves of the big tree is more efficient than opening all but one leaf in each of the \(\tau \) smaller trees, because with high probability some of the active paths in the tree will merge relatively close to the leaves, which reduces the number of internal nodes that need to be revealed.”

2. 2.

   The authors further propose to improve the previous approach using the principle of grinding. When the last Fiat-Shamir challenge is such that the number of revealed nodes in the revealed sibling paths exceed a threshold \(T_{\text {open}}\), the signer rejects the challenge and recompute the hash with an incremented counter. This process is done until the number of revealed nodes is \(\le T_{\text {open}}\). For example, if we consider \(N=256\) and \(\tau =16\), the number of revealed nodes is smaller than (or equal to) \(T_{\text {open}}:=110\) with probability \(\approx 0.2\). The selected value of \(T_{\text {open}}\) induces a rejection probability \(p_{\text {rej}} = 1 - 1/\theta \), for some \(\theta \in (0,\infty )\), and the signer hence needs to perform an average of \(\theta \) hash computations for the challenge (instead of 1). While this strategy decreases the challenge space by a factor \(\theta \), it does not change the average number of hashes that must be computed to succeed an attack (since the latter is multiplied by \(\theta \)). As noticed by the authors of [11], this strategy can be thought of as loosing \(\log _2 \theta \) bit of security (because of a smaller challenge space) which are regained thanks to a proof-of-work (performing an average of \(\theta \) hash computations before getting a valid challenge).

3. 3.

   Finally, [11] proposes to add another explicit proof-of-work to the Fiat-Shamir hash computation of the last challenge. The signer must get a hash digest for which the w last bits are zero, for w a parameter of the scheme. The same counter as for the previous improvement is used as a nonce in this hash and increased until the w-zeros property is satisfied. This strategy increases the cost of hashing the last challenge by a factor \(2^w\) and hence increases the security of w bits. This thus allows to take smaller parameters \((N,\tau )\) for the large tree, namely parameters achieving \(\lambda - w\) bits of security instead of \(\lambda \).

While the authors of [11] focus on VOLEitH, the same optimisations also apply to TCitH. In summary, for a given w, one picks parameters \((N,\tau )\) ensuring \(\lambda -w\) bits of security. Then fixing \(T_{\text {open}}\) for these \((N,\tau )\) yields a rejection probability \(p_{\text {rej}} = 1 - 1/\theta \). The gain in size comes from the smaller parameters \((N,\tau )\) on the one hand, and the smaller sibling paths (of size \(\le T_{\text {open}}\) instead of \(\approx \tau \log _2 N\)) on the other hand. This gain in size is traded for an increased number of Fiat-Shamir hash attempts (\(\theta \cdot 2^w\) on average instead of 1).

In this section, we propose new signature schemes based on the rank syndrome decoding problem and on the MinRank problem. To proceed, we rely on the TCitH and VOLEitH frameworks to obtain non-interactive zero-knowledge proofs of knowledge for these two problems using the new Dual Support Decomposition model described in Sect. 4 and we use the recent MPCitH optimisation presented in Sect. 5.3. Moreover, to have more granularity in the choice of the parameters, we consider that the \(\tau \) emulations of the MPC protocol might not involve the same number of parties: there will be \(\tau _1\) emulations with \(N_1\) parties and \(\tau _2 := \tau -\tau _1\) emulations with \(N_2\) parties. The schemes are then secure if \(\left( \frac{d}{N_1}\right) ^{\tau _1}\cdot \left( \frac{d}{N_2}\right) ^{\tau _2}\) for TCitH and \(\frac{d}{N_1^{\tau _1}\cdot N_2^{\tau _2}}\) for VOLEitH are negligible (instead of simply \(\left( \frac{d}{N}\right) ^{\tau }\) and \(\frac{d}{N^{\tau }}\)).

6.1 New Signatures Based on \(\textsf{RSD}_{\text {s}}\)

The TCitH and VOLEitH frameworks enable us to prove the knowledge of a witness that satisfies some polynomial constraints. In order to get a signature scheme based on the rank syndrome decoding problem, one just needs to exhibit the polynomial constraints which is satisfied by a rank syndrome decoding solution. As shown in Sect. 4.1, solving an \(\textsf{RSD}_{\text {s}}\) instance for \(\boldsymbol{y}\) and \(\boldsymbol{H}\) is equivalent to finding \(\boldsymbol{s}=(x_2,\dots ,x_r)\) where \(x_i \in \mathbb {F}_{q^m}\) for \(i \in \{2,\dots , r \}\) and \(\boldsymbol{C} \in \mathbb {F}_q^{r \times (n-r)}\) such that

Equation 1 directly gives degree-2 polynomial constraints into the coefficients of \(\boldsymbol{s}\) and \(\boldsymbol{C}\). Let us assume that the \(\boldsymbol{H}\) is in standard form, meaning it can be written as \(\boldsymbol{H}=\begin{pmatrix} \boldsymbol{I_{n-k}} & \boldsymbol{H'} \end{pmatrix}\), where \(\boldsymbol{H'}\in \mathbb {F}_{q^m}^{(n-k)\times k}\). Given the inputs \([\![ \boldsymbol{s} ]\!]\) and \([\![ \boldsymbol{C} ]\!]\), the hint \([\![ \boldsymbol{v} ]\!]\) with \(\boldsymbol{v}\in {\mathbb {F}_{q^m}^\rho }\) and the MPC randomness \(\boldsymbol{\Gamma }=(\gamma _{i,j})_{i,j}\in \mathbb {F}_{q^m}^{(n-k)\times \rho }\), the emulated MPC protocol (repeated \(\rho \) times) described in Protocol 1 thus consists of computing

where \([\![ \boldsymbol{x_A} ]\!]\) and \([\![ \boldsymbol{x_B} ]\!]\) are built such as \([\![ \begin{pmatrix} \boldsymbol{x_A} & \boldsymbol{x_B} \end{pmatrix} ]\!] = \begin{pmatrix} 1 & [\![ \boldsymbol{s} ]\!] \end{pmatrix} \cdot \begin{pmatrix} \boldsymbol{I_r} & [\![ \boldsymbol{C} ]\!] \end{pmatrix}\).

Signature Size. According to Sect. 5, the signature size using the TCitH framework is (in bits):

while the signature size using the VOLEitH framework is (in bits):

where \(|w|:=(r-1)m+r(n-r)\).

Computational Cost. The running time of the signing algorithm can be split in three main parts:

1. 1.

   The generation of the input shares using seed trees and their commitment. The computational cost scales linearly with the number of input shares. When there are \(\tau _1\) MPC emulations with \(N_1\) parties and \(\tau _2\) MPC emulations with \(N_2\) parties, the total number of input shares is \(\tau _1\cdot N_1 + \tau _2 + N_2\).

2. 2.

   The MPC emulation. This step consists in computing the degree-2 broadcast sharing \([\![ \boldsymbol{\alpha } ]\!]\), knowing that \(\boldsymbol{\alpha }=0\). Let us estimate the cost of emulating the MPC protocol. We only count multiplications which are predominant (compared to additions) for the considered extension fields. We recall that multiplying two degree-1 sharings costs 2 multiplications in the underlying field, assuming we already know the plain value.

   • With TCitH, the MPC emulation will be repeated \(\tau :=\tau _1+\tau _2\) times. Each repetition includes 2 vector-matrix multiplications with a matrix \(\mathbb {F}_{q^m}^{(r-1)\times (n-r)}\) to compute \([\![ \boldsymbol{x} ]\!]:=[\![ \begin{pmatrix} \boldsymbol{x_A} & \boldsymbol{x_B} \end{pmatrix} ]\!]\), 2 vector-matrix multiplications with a matrix of \(\mathbb {F}_{q^m}^{k\times (n-k)}\) to compute \([\![ \boldsymbol{r} ]\!]:=[\![ \boldsymbol{x_A} ]\!] + [\![ \boldsymbol{x_B} ]\!] \boldsymbol{H'}^T - \boldsymbol{y}\), and 2 vector-matrix multiplications with matrix of \(\mathbb {F}_{q^m}^{(n-k)\times \rho }\) to compute \([\![ \boldsymbol{\alpha } ]\!]\).

   • With VOLEitH, the MPC emulation is executed only once, but in a larger extension field \(\mathbb {K}\) where \([\mathbb {K}:\mathbb {F}_{q^m}]=\rho \). The emulation includes 2 vector-matrix multiplications with a matrix \(\mathbb {K}^{(r-1)\times (n-r)}\) to compute \([\![ \boldsymbol{x} ]\!]:=[\![ \begin{pmatrix} \boldsymbol{x_A} & \boldsymbol{x_B} \end{pmatrix} ]\!]\), \(2\rho \) vector-matrix multiplications with a matrix of \(\mathbb {F}_{q^m}^{k\times (n-k)}\) to compute \([\![ \boldsymbol{r} ]\!]:=[\![ \boldsymbol{x_A} ]\!] + [\![ \boldsymbol{x_B} ]\!] \boldsymbol{H'}^T - \boldsymbol{y}\), and 2 vector-matrix multiplications with matrix of \(\mathbb {K}^{(n-k)\times 1}\) to compute \([\![ \boldsymbol{\alpha } ]\!]\).

3. 3.

   The global proof-of-work, composed of the grinding process on the seed trees and the explicit proof-of-work on the Fiat-Shamir hash computation. Its average cost is \( \theta \cdot 2^w\) Fiat-Shamir hash computations.

The running time of the other parts of the signing algorithm is negligible compared to those three components. Regarding the running time of the verification algorithm, since the verifier should also expand the seed trees and emulate some parties, the verification time will be similar (a bit smaller) than the signing time.

Parameter Selection. We select some parameter sets for our signature schemes. To have a fair comparison between both frameworks (TCitH and VOLEitH), we chose the parameters such that the cost of generating the input shares and the cost of the proof-of-work are similar (namely, we chose parameters such that \(\tau _2\cdot N_1 + \tau _2\cdot \tau _2\) and \(\theta \cdot 2^w\) are roughly equal). We present in Table 7 the sizes obtained for the signature scheme.

While proposing optimized implementations of our signature scheme is left for future work, we provide some (upper bound) estimates for its running time in Table 8. The timings of the symmetric components (generation and commitment of the input shares and proof of work) are estimated based on the benchmarks from [11]. Since we rely on the same parameters for the symmetric components (same \(\tau _1\cdot N_1 + \tau _2\cdot N_2\) and same \(\log _2 \theta + w\)), we can use their timings as upper bounds. For example, their scheme MandaRain-3-128 s includes a generation and commitment of 22 528 input shares and has a total proof-of-work of 14 bits as our “short” instances. Since it runs in 2.8 ms on a 5 GHz CPU, we deduce that the symmetric components cost is at most 14 Mcycles.^{Footnote 4} Then, we derived and benchmarked a naive implementation of the MPC emulation, which gives us an upper bound for the emulation cost. Despite this pessimistic estimation, the results presented in Table 8 show that our scheme is competitive with the NIST candidate RYDE. In particular, all our variants relying on VOLEitH are faster than RYDE.

Comparison. Table 9 summarizes the state of the art of signature schemes based on \(\textsf{RSD}\). We include in the comparison only short parameters, i.e., with \(N = 256\) for MPCitH-based signatures, and \(N= 32\) for [15]. We include the schemes of Stern [37] and Véron [38] applied to the rank metric. For 128 bits of security, these two schemes have signature sizes of around 30 kB. These sizes were roughly halved in [21] and [15]. Finally, [20] reduced it below 6 kB and our work achieves sizes below 4 kB.

Resilience Property. One should note that our scheme is highly resilient to hypothetical cryptanalytic progress on \(\textsf{RSD}_{\text {s}}\). Indeed, if we were to take the set of parameters for \(\textsf{RSD}_{\text {s}}\) corresponding to NIST III, applied to the proof of knowledge for NIST I, i.e., a security of \(\lambda = 192\) for \(\textsf{RSD}_{\text {s}}\) and \(\lambda =128\) for the protocol, we would get an increase of only 0.4 kB (for \(N=512\)) or 0.3 kB (for \(N=2048\)) in the signature size. Namely, we can take a large margin of security for the parameters of \(\textsf{RSD}_{\text {s}}\) at a moderate cost.

6.2 New Signatures Based on \(\textsf{MinRank}\)

The TCitH and VOLEitH frameworks enable us to prove the knowledge of a witness that satisfies some polynomial constraints. In order to get a signature scheme based on \(\textsf{MinRank}\), one just needs to exhibit the polynomial constraints which that a \(\textsf{MinRank}\) solution should satisfy. As shown in Sect. 4.2, we can use the \(\mathsf {MinRank~Syndrome}\) problem, which asks to find \(\boldsymbol{S'}\in \mathbb {F}_q^{(m-r)\times r}\) and \(\boldsymbol{C}\in \mathbb {F}_q^{r\times n}\) such that

where \(\boldsymbol{H} \in \mathbb {F}_q^{(mn-k) \times mn}\) and \(\boldsymbol{y}\in \mathbb {F}_q^{mn-k}\). Equation (2) directly gives degree-2 polynomial constraints into the coefficients of \(\boldsymbol{S'}\) and \(\boldsymbol{C}\). Let us assume that the matrix \(\boldsymbol{H}\) is in standard form, meaning it can be written as \(\boldsymbol{H}=\begin{pmatrix} \boldsymbol{I_{n\cdot m-k}} & \boldsymbol{H'} \end{pmatrix}\), where \(\boldsymbol{H'}\in \mathbb {F}_{q}^{(n\cdot m-k)\times k}\). Given the inputs \([\![ \boldsymbol{S'} ]\!]\) and \([\![ \boldsymbol{C} ]\!]\), the hint \([\![ \boldsymbol{v} ]\!]\) with \(\boldsymbol{v}\in {\mathbb {F}_{q}^\rho }\) and the MPC randomness \(\boldsymbol{\Gamma }=(\gamma _{i,j})_{i,j}\in \mathbb {F}_{q}^{(n-k)\times \rho }\), the emulated MPC protocol (repeated \(\rho \) times) described in Protocol 1 thus consists in computing

where \([\![ \boldsymbol{x_A} ]\!]\) and \([\![ \boldsymbol{x_B} ]\!]\) are built such as \([\![ \begin{pmatrix} \boldsymbol{x_A} & \boldsymbol{x_B} \end{pmatrix} ]\!] = \rho \left( \begin{pmatrix} \boldsymbol{I_r} \\ [\![ \boldsymbol{S'} ]\!] \end{pmatrix}\cdot [\![ \boldsymbol{C} ]\!]\right) \).

Signature Size. According to Sect. 5, the signature size using the TCitH framework is (in bits):

while the signature size using the VOLEitH framework is (in bits):

where \(|w|:=r(m-r)+rn\).

Computational Cost. As in the previous section, the running time of the signing algorithm can be split in three main parts:

1. 1.

   The generation of the input share using seed trees and their commitment. The computational cost scales linearly with the number of input shares. When there are \(\tau _1\) MPC emulations with \(N_1\) parties and \(\tau _2\) MPC emulations with \(N_2\) parties, the total number of input shares is \(\tau _1\cdot N_1 + \tau _2 + N_2\).

2. 2.

   The MPC emulation. This step consists in computing the degree-2 broadcast sharing \([\![ \boldsymbol{\alpha } ]\!]\), knowing that \(\boldsymbol{\alpha }=0\). Let us estimate the cost of emulating the MPC protocol (while only counting multiplications as above).

   • With TCitH, the MPC emulation will be repeated \(\tau :=\tau _1+\tau _2\) times. Each repetition includes 2 multiplications between matrices of \(\mathbb {F}_{N}^{(m-r)\times r}\) and \(\mathbb {F}_{N}^{r\times n}\) to compute \([\![ \boldsymbol{x} ]\!]\), \(2\cdot [\mathbb {F}_N:\mathbb {F}_q]\) vector-matrix multiplications with a matrix of \(\mathbb {F}_{q}^{k\times (n\cdot m-k)}\) to compute \([\![ \boldsymbol{x_A} ]\!] + [\![ \boldsymbol{x_B} ]\!] \boldsymbol{H'}^T - \boldsymbol{y}\), and 2 vector-matrix multiplications with matrix of \(\mathbb {F}_{N}^{(n\cdot m -k)\times \rho }\) to compute \([\![ \boldsymbol{\alpha } ]\!]\).

   • With VOLEitH, the MPC emulation is executed only once, but in a larger extension field \(\mathbb {K}\) where \([\mathbb {K}:\mathbb {F}_{N}]=\rho \). The emulation includes 2 matrix multiplications of \(\mathbb {K}^{(m-r)\times r}\) and \(\mathbb {K}^{r\times n}\) to compute \([\![ \boldsymbol{x} ]\!]\), \(2\rho \cdot [\mathbb {F}_N:\mathbb {F}_q]\) vector-matrix multiplications with a matrix of \(\mathbb {F}_{q}^{k\times (n\cdot m-k)}\) to compute \([\![ \boldsymbol{x_A} ]\!] + [\![ \boldsymbol{x_B} ]\!] \boldsymbol{H'}^T - \boldsymbol{y}\), and 2 vector-matrix multiplications with matrix of \(\mathbb {K}^{(n\cdot m-k)\times 1}\) to compute \([\![ \boldsymbol{\alpha } ]\!]\).

3. 3.

   The global proof-of-work, composed of the grinding process on the seed trees and the explicit proof-of-work on the Fiat-Shamir hash computation. Its average cost is \( \theta \cdot 2^w\) Fiat-Shamir hash computations.

The running time of the other parts of the signing algorithm is negligible compared to those three components. Regarding the running time of the verification algorithm, since the verifier should also expand the seed trees and emulate some parties, the verification time will be similar (a bit smaller) than the signing time.

Parameter Selection. We select some parameter sets for our signature schemes. To have a fair comparison between both frameworks (TCitH and VOLEitH), we chose the parameters such that the cost of generating the input shares and the cost of the proof-of-work are similar (namely, we chose parameters such that \(\tau _2\cdot N_1 + \tau _2\cdot \tau _2\) and \(\theta \cdot 2^w\) are roughly equal). We present in Table 10 the sizes obtained for the signature scheme.

As previously, we leave optimized implementations for future work and provide (upper bound) estimates of the running time in Table 11 based on the benchmarks from [11] and a naive implementation of the MPC emulation of our scheme. Despite this pessimistic estimation, the results of Table 11 show that our scheme is competitive with the NIST sublmissions MIRA and MiRitH (both applying MPC-in-the-Head to \(\textsf{MinRank}\)). In particular, all our variants relying on TCitH are faster than MIRA and the short instances of MiRitH.

Comparison. Table 12 summarizes the state of the art of signature schemes based on \(\textsf{MinRank}\). We include in the comparison only short parameters, i.e., with \(N = 256\) for MPCitH-based signatures, and \(N= 32\) for [15]. For the \(\textsf{MinRank}\) parameters, we use \(q=16, m= 16, n=16,k =142, r=4\). Historically, the first schemes from [18, 35], and [14] obtained signature sizes no less than 26 kB for 128 bits of security. Then, the technique from [15] applied to \(\textsf{MinRank}\) achieved \(\sim \)10 kB, and [2] reduced it even below 7 kB. The recent work from [20] reduces it below 6 kB, and the MIRA and MiRitH submissions to the NIST have sizes below 6 kB as well. Finally, our work achieves sizes below 4 kB.

Resilience Property. As for our scheme based on \(\textsf{RSD}_{\text {s}}\), our above scheme is highly resilient to hypothetical cryptanalytic progress on \(\textsf{MinRank}\). Indeed, if we were to take the set of parameters for \(\textsf{MinRank}\) corresponding to NIST III, applied to the proof of knowledge for NIST I, i.e., a security of \(\lambda = 192\) for \(\textsf{MinRank}\) and \(\lambda =128\) for the protocol, we would get an increase of only 0.4 kB (for \(N=512\)) or 0.3 kB (for \(N=2048\)) in the signature size. Namely, we can take a large margin of security for the parameters of \(\textsf{MinRank}\) at a moderate cost.