domain: info math

text:
Nicolas Aragon

Magali Bardet

Loïc Bidoux

Jesús-Javier Chi-Domínguez

Victor Dyseryn

Thibauld Feneuil

Philippe Gaborit

Romaric Neveu

Matthieu Rivain

Jean-Pierre Tillich

MIRA Specifications

Table of Contents 1 Introduction

MIRA is a digital signature protocol based on the MinRank problem and the MPC-inthe-Head paradigm. This document specifies the scheme described in our Design Document, [ABCD + 23]. The scheme is quantum-resistant, and is based on zero-knowledge proofs and symmetric functions, such as hash functions. We present an high-level description of the scheme and the MPC-in-the-Head paradigm, on which the protocol is built. The security of the signature is conditioned by the difficulty of solving the MinRank problem. We apply the Fiat- Shamir transform [FS87] in order to have a signature. MIRA is based on additive secret sharing, and uses the idea of the hypercube structure from [AMGH + 22], as well as an MPC protocol using linearized polynomials which is introduced in [Fen22].

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

The name MIRA comes from the MInRAnk problem.

Mathematical Background and Notations

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

We denote by [1, N ] the set of integer between 1 and N . This set can be shortened by writing [N ]. Let E ∈ F m×n q = e i,j , e i,j ∈ F q , i ∈ [1, m], j ∈ [1, n], and B = b 1 . . . b m an F q -basis of F q m . It is then possible to associate each column of E to an element of F q m by setting

e j = m i=1 b i e i,j
for each j ∈ [1, n] By setting e = (e 1 . . . e n ), we can say that e is the vector associated to the matrix E. The Rank Weight is defined as W R (e) = Rank(E). The distance between two vectors x and y is d(x, y) = W R (x -y). The support of e = (e 1 . . . e n ) is the linear subspace of F q m generated by its coordinates: Supp(e) = e 1 . . . e n .

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

MinRank: Let F q be the finite field of size q, and m, n, k, r ∈ N * . The computational MinRank Problem with parameters (q, m, n, k, r) is Let M 0 , . . . , M k , E ∈ F m×n q and x ∈ F k q sampled uniformly at random such that: M 0 = Ek i=1 M i x i and Rank(E) ≤ r. Knowing M 0 , . . . , M k , retrieve x.

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

The interactive proof relies on a prover simulating a MultiParty Computation (MPC) protocol, where each party has a share of the witness x. The sharing of a secret s among N parties is denoted (s[1], . . . , s[N ]) where s[i] is the share possessed by the party i. s [J] where J ⊂ [1, N ] is the subset of shares (s[j]) j∈J . When we do not specify which party receives the share (as is the case in Fig. 1), we note the share as s [•] Below is the secret sharing scheme we are going to use.

Additive Secret Sharing. Let F a field and s ∈ F a secret. An additive secret sharing with N parties satisfies:

s[i] = r i for i ∈ [1, N -1], where r i $ ←-F s[N ] = s -N -1
i=1 s[i] The Reconstruct [1,N ] algorithm takes as inputs all the shares, and outputs the sum of all the shares.

3 High-level description of the signature scheme As mentioned earlier, the scheme relies on a MinRank instance. Hence, the public key pk is a list of matrices M 0 , . . . , M k , and the private key sk is the vector x, of size k. In order to sign a message one has to:

-Build the proof of knowledge; -Apply the Fiat-Shamir transform.

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

Description of the MPC protocol

A multi-party computation protocol is an interactive protocol involving several parties whose objective is to jointly compute a function f on the shares of x they received at the begin of the protocol, and each get a share of f (x). At each step, the parties can perform one of the following actions:

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

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

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

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

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

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

-Each party computes their share of E;

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

-The view of N -1 parties gives no information whatsoever about x.

Concretely, if v = 0, this means that E is of rank at most r if the computations and the inputs are from an honest party. This comes from the properties of a linearized polynomial (see [ABCD + 23] or [Fen22]). Formally, we can describe the MPC protocol with the following figure:

-

Public data M 0 , . . . , M k ∈ F m×n q -Each party receives x[•] ∈ F k q , L[•] = r-1 i=0 β i [•]X q i + X q r where each β i ∈ F q m , a[•]
where a is uniformly sampled from F r q mη and c[•] ∈ F q mη such that c = -a, β

1. The parties sample (γ 1 , ..., γn,

) $ ←-F n+1 q mη 2. The parties compute E[•] = M 0 + k i=1 x i [•]M i 3. The parties set e i [•] as the element in F q m associated to the i-th column of E[•] 4. They compute z[•] = -n j=1 γ j (e j [•] q r ) 5. For i from 0 to r -1 : They compute w i [•] = n j=1 γ j (e j [•] q i ) 6. α[•] = • w[•] + a[•]
and the parties open the shares to get α

7. v[•] = • z[•] -α, β[•] -c[•]
and the parties open the shares to get v 8. They output ACCEPT if v = 0, and REJECT otherwise Fig. 1: Protocol Π η to check that an input is solution of an instance of MinRank

Steps 2 and 3 are the computation of E and its support, and steps 4 to 7 are the computation of v. The parties open an element, α, during the process, in order to make sure the computation is done honestly. Note that in step 3, the computation is done in regards to the columns of E. Depending on the parameters m and n, it might be better to do it with the rows instead. We refer to [ABCD + 23] or [Fen22] for the proof of false positive of this MPC protocol and its correctness.

Application of the MPCitH paradigm

General view of MPCitH

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

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

-The prover commits the shares of the parties; -He receives a challenge in order to execute the MPC protocol; -He sends the hash of the results of the MPC protocol for each party;

-He receives a challenge to know what to reveal;

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

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

We will now describe the proof of knowledge.

Overview of MIRA

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

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

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

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

-Thanks to this challenge, he simulates the D -1 MPC computations on main shares (one per dimension), and 1 MPC computation on plain values, and sends the hash of the results of the computations;

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

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

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

Detailed algorithmic description

This section is dedicated to a low-level algorithmic description of the three algorithms of our scheme: MIRA_Keygen, MIRA_Sign and MIRA_Verify. Before that, we introduce low-level notation in Section 4.1, and detail subroutines of our main algorithmis in Sections 4.2-4.8.

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

Algorithmic notation

For an integer x ∈ [0, 2 D -1] and δ ∈ [D], we denote bit(x, δ) the δ-th least significant bit of the binary repesentation of x. For example, let x = 35 = 100011 2 , then bit(x, 2) = 1 and bit(x, 3) = 0. Fqm -vector associated to the Fq-matrix E x F k q Secret coefficients of the secret linear combination

Indexes: i [1, N ] Index of
β F r q m
Annulator polynomial of the support of e. a F r q m

Vector used in the MPC rank checking protocol.

w F r q m
Vector used in the MPC rank checking protocol.

γ F n q m
Vector from the first challenge. c Fqm Element used in the MPC rank checking protocol. z Fqm Element used in the MPC rank checking protocol.

Fqm

Element from the first challenge.

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

The main shares of the above vectors and elements are noted with an hat and an array index δ (for example â[δ]).

Table 1: Description of low level notation used in our scheme

Operations on finite field elements

Representation of finite field elements

In this document we always have F q = F 16 . We define F q as F 2 [X]/ P where P = X 4 + X + 1. Elements of F q are represented in the polynomial basis.

Converting a byte stream into elements of F q

When sampling randomness, we want to convert a byte stream b 0 , b 1 , . . . into elements of F q . Sampling n elements in F q is done using the FqArrayFromBytes(n) function 1.

Algorithm 1 FqArrayFromBytes

Input: Size n, l = n 2 bytes b0, . . . , b l-1 Output: An array x of n elements of Fq 1: for i from 0 to n 2 -1 do 2: x2i = bi & 0xf 3: x2i+1 = (bi >> 4) 4: if n%2 == 1 then 5: xn-1 = b l-1 & 0xf
We also define the FqArrayToBytes(A) 2 to go from an array of n elements of F q to a byte array.

Algorithm 2 FqArrayToBytes

Input: An array x of n elements of Fq Output: A byte array b0, . . . , b l-1 where l = n 2 1:

for i from 0 to n 2 -1 do 2: bi = (x2i & 0xf) + (x2i+1 << 4) 3: if n%2 == 1 then 4: b l-1 = xn-1 & 0xf
Using these core functions we can define how matrices over F q and arrays of elements in F q m are parsed:

-We process arrays of r elements of F q m as arrays of rm elements of F q , -We process m × n matrices over F q as arrays of mn elements of F q .

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

Defining extensions of F q

In order to perform operations in F q m we define how F q m is defined as an extension of F q .

-For m = 16:

We define F q 2 , F q 4 , F q 8 and F q 16 as follows:

F q 2 = F q [Z]/ Z 2 + Z + X 3 F q 4 = F q 2 [A]/ A 2 + A + (ZX 3 ) F q 8 = F q 4 [B]/ B 2 + B + (ZAX 3 ) F q 16 = F q 8 [Y ]/ Y 2 + Y + (ZABX 3 ) -For m prime:
When m is prime we define F q 16 as F q [Y ]/ P where P is an irreducible polynomial of degree m over F 2 . Table 2 describes the chosen polynomials.

m P 19 Y 19 + Y 5 + Y 2 + Y + 1 23 Y 23 + Y 5 + 1
Table 2: Polynomials used to define the field F q m . Conversion from F q -arrays to F q m -elements is done using a F q -basis of F q m (g 1 , ..., g m ) that is defined as follows:

-For m = 16, the basis consists of elements

Z b 0 A b 1 B b 2 Y b 3 for every possible 4-bitstring b 0 b 1 b 2 b 3 in increasing order.
-For m prime, the basis is the standard polynomial basis (1, Y, . . . , Y m-1 ).

This basis (g 1 , ..., g m ) allows converting between an F q -matrix of size m × n and an F q mvector of size n:

Algorithm 3 FqMatrixToFqmVector

Input: A matrix M ∈ F m×n q Output: A vector x ∈ F n q m of length n 1: for j ∈ [n] do 2: xj = m i=1 Mi,jgi 3: return x Algorithm 4 FqmVectorToFqMatrix Input: A vector x ∈ F n q m of length n Output: A matrix M ∈ F m×n q 1: for j ∈ [n] do 2:
Fill the j-th column of M with the coefficients of xj in the basis (g1, . . . , gm).

xj = m i=1
Mi,jgi 3: return M

Computing an annihilator polynomial

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

Algorithm 5 ComputeAnnihilatorPolynomial

Input: Support supp ∈ F r q m of rank r Output:

Annihilator polynomial P ∈ Fqm [X] such that for all u ∈ supp , P (u) = 0 P1 = X q -supp[0] q-1 for i from 1 to r do T = P q i eval = Pi(supp[i]) Pi+1 = eval q-1 Pi + T return Pr+1

Randomness generators and hash functions

-RandomBytes( ) is instanciated using the NIST provided randombytes function, it returns bytes from system entropy;

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

• PRG.Init(seed) initializes the internal state of the generator with a seed,

• PRG.GetBytes( ) outputs bytes from the generator and updates its internal state.

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

Sampling routines

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

Algorithm 6 SampleSecretInstance

Input: Size (m, n), dimension k, rank weight r, a seed seed Output: E ∈ Fqm × n a matrix of rank r and its support supp ∈ F r q m , x ∈ F k q . 1: PRG.Init(seed) 2: r_bytes = rm 2 3: repeat 4:

supp[1, r] = FqmArrayFromBytes(r, PRG.GetBytes(r_bytes)) Sampling the support 5: until Rank(FqmVectorToFqMatrix(supp)) = r 6: e = (0, . . . , 0)

Initialize e with zeros 7: repeat 8:

coordinates =FqArrayFromBytes(nr, PRG.GetBytes( nr 2 )) 9: Algorithm 8 SampleShares

for i ∈ [n] do 10: for j ∈ [r] do 11: ei = ei + coordinates[(i -1)r + j] • supp[j] 12: E = FqmVectorToFqMatrix(e) 13: until Rank(E) = r 14: k_bytes = k
Input: A seed seed Output: A set of shares (x, β, a, c) ∈ F k q × F r q m × F r q m × Fqm PRG.Init(seed) xbytes = PRG.GetBytes( k 2 ) x = FqArrayFromBytes(k, xbytes) bbytes = PRG.GetBytes( rm 2 ) β = FqmArrayFromBytes(r, bbytes) abytes = PRG.GetBytes( rm 2 ) a = FqmArrayFromBytes(r, abytes) cbytes = PRG.GetBytes( m 2 ) c = FqmArrayFromBytes(1, cbytes)[0] return (x, β, a, c) Algorithm 9 SampleFirstChallenge Input: A seed seed Output: A set of first challenges (γ (e) , (e) ) e∈[τ ] ∈ (F n q m × Fqm ) τ PRG.Init(seed) for e ∈ [τ ] do xbytes = PRG.GetBytes( (n+1)m 2 ) γ (e) = FqmArrayFromBytes(n, xbytes[..n]) (e) = FqmArrayFromBytes(1, xbytes[n+1])[0] return (γ (e) , (e) ) e∈[τ ]
Algorithm 10 SampleSecondChallenge

Input: A seed seed Output: A set of second challenges (i * (e) ) e∈[τ ] ∈ [N ] τ PRG.Init(seed) for e ∈ [τ ] do i * (e) = PRG.GetBytes(1) mod N return (i * (e) ) e∈[τ ] 4.5 MPC routines Algorithm 11 MPC-MinRank.ComputeAlpha Input: -A set of shares (e, a) -A protocol challenge (γj) j∈[1,n] , Output: α 1: for k ∈ [1, r] do 2: w k = n j=1 γj(e q k-1 j ) 3: α = • w + a 4: return α Algorithm 12 MPC-MinRank.Exec Input: -A set of main shares ( xB[δ], β[δ], â[δ], ĉ[δ]) δ∈[D] -A protocol challenge (γj) j∈[1,n] , -A full value α -The public matrices M0, . . . , M k Output: ( α[δ], v[δ]) δ∈[D] 1: for δ ∈ [D] do 2: Ê[δ] = M0 + k i=1 xi[δ]Mi 3: ê[δ] = FqMatrixToFqmVector( Ê[δ]) 4: α[δ] = MPC-RSD.ComputeAlpha(ê[δ], â[δ], (γj) j∈[1,n] , ) 5: ẑ[δ] = -n j=1 γj(êj[δ] q r ) 6: v[δ] = • ẑ[δ] -α, β[δ] -ĉ[δ] 7: return ( α[δ], v[δ]) δ∈[D]

Hypercube routines

The N = 2 D leaf shares are arranged on a D-dimensional hypercube of side length 2. An index i ∈ [N ] is positioned according to the binary representation of i -1

∈ [0, 2 D -1].
The δ-th coordinate of i in the hypercube is the δ-th least significant bit of the binary repesentation of i -1, i.e. bit(i -1, δ).

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

Algorithm 13 Hypercube.MainShares-Compute

Input: A set of leaf shares (x[i], β[i], a[i], c[i]) i∈[N ] where N = 2 D Output: A set of main shares ( x[δ], β[δ], â[δ], ĉ[δ]) δ∈[D] 1: for δ ∈ [D] do 2: x[δ] = i∈[N ] bit(i-1,δ)=0 x[i] 3: β[δ] = i∈[N ] bit(i-1,δ)=0 β[i] 4: â[δ] = i∈[N ] bit(i-1,δ)=0 a[i] 5: ĉ[δ] = i∈[N ] bit(i-1,δ)=0 c[i]
Algorithm 14 Hypercube.MainAlphaAndV-Compute

Input: A set of leaf shares (α[i], v[i]) i∈[N ] where N = 2 D Output: A set of main shares ( α[δ], v[δ]) δ∈[D] 1: for δ ∈ [D] do 2: α[δ] = i∈[N ] bit(i-1,δ)=0 α[i] 3: v[δ] = i∈[N ] bit(i-1,δ)=0 v[i]

Key parsing routines

Algorithm 15 ParseSecretKey

Input: Secret key sk Output: M0, . . . , M k , x, the annihilator polynomial β and e 1: (sk_seed, pk_seed) = sk 2: pk_PRG.Init(pk_seed)

3: L_bytes = k(mn-k) 2 4: L = FqMatrixFromBytes(k, mn-k, pk_PRG.GetBytes(L_bytes)) 5: L = (I k |L ) 6: for i ∈ [k] do 7: for j ∈ [m] do 8:
for ∈ [n] do 9:

(Mi) j, = L i,(j-1)n+ 10: (E, supp, y) = SampleSecretInstance(sk_seed) 11: 1: if D = 0 then 2: return seed 3: else 4:

F = E -k i=1 yiMi 12: for i ∈ [k] do 13: fi = F 1+ i-1 n ,1+((i-1) mod n) 14: M0 = F -k i=1 fiMi
(seed_left, seed_right) = Hash(DS_T, salt, e, seed) 5:

(seedi)

Algorithm 19 PRGPartialTreeExpand

Input: A partial tree, i.e. a family of seeds (seedi) i∈[D] , a salt and an iteration index e, a hidden index i * Output: All seeds but one (seedi (seed e) , N, salt, e) 8: a (e) [N ] = FqmArrayFromBytes(r, abytes) Compute final leaf shares 14:

) i∈[N ],i =i * 1: Let N = 2 D 2: if i * ≤ N/2 then 3: (seedi) i∈[N/2],i =i * = PRGPartialTreeExpand((seedi) i∈[D-1] ) 4: (seedi) i∈[N/2+1,N ] = PRGTreeExpand(
(e) i ) i∈[N ] = PRGTreeExpand(seed (
for i ∈ [N -1] do Compute leaf shares 9: (x (e) [i], β (e) [i], a (e) [i], c (e) [i]) = SampleShares(seed (
a (e) = i∈[N ] a (e) [i] 15: x (e) [N ] = x -N -1 i=1 x (e) [i] 16: β (e) [N ] = β -N -1 i=1 β (e) [i] 17: c (e) [N ] = -a (e) , β -N -1 i=1 c (e) [i] 18:
cmt

1 , . . . , cmt

N , cmt (1)
1 , . . . , cmt

(τ ) 1 , • • • , cmt (τ )
N )

Commit hypercube

Step 2: First challenge 21: (γ (e) , (e) ) e∈[τ ] = SampleFirstChallenge(h1)

Step 3: First response 22: for e ∈ [τ ] do 23:

α (e) = MPC-MinRank.ComputeAlpha(e, a (e) , γ (e) , (e) ) 24:

( α(e) Step 4: Second challenge 26: (i * (e) ) e∈[τ ] = SampleSecondChallenge(h2)

Step 5: Second response 27: for e ∈ [τ ] do 28:

ptree (e) =PRGPartialTreeReveal(seed (e) , i * (e) )

29: e) ]Mj otherwise 30: e (e) [i * (e) ] = FqMatrixToFqmVector(E (e) [i * (e) ]) 31:

E (e) [i * (e) ] = M0 + k j=1 x (e) [i * (e) ]Mj if i * (e) = 1 k j=1 x (e) [i * (
MPC-MinRank.ComputeAlpha(e (e) [i * (e) ], a (e) [i * (e) ], γ (e) , (e) ) 32:

if i * (e) = N then 33:

rsp (e) = (ptree (e) , cmt

i * (e) , α (e) [i * (e) ], 0, 0, 0) 34: else 35:

rsp (e) = (ptree (e) , cmt

i * (e) , α (e) [i * (e) ],

x (e) [N ], β (e) [N ], c (e) [N ])

Step 6: Signature 36: return σ = (salt, h1, h2, (rsp (e) ) e∈[τ ] )

Algorithm 22 MIRA_Verify

Input: Public key pk, message m ∈ {0, 1} * , signature σ ∈ {0, 1} * Output: Accept or Reject

Step 0: Parse keys 1:

(M0, • • • , M k ) = ParsePublicKey(pk)
Step 1: Parse challenges 2: (γ (e) , (e) ) e∈[τ ] = SampleFirstChallenge(h1) 3: (i * (e) ) e∈[τ ] = SampleSecondChallenge(h2) 4: for e ∈ [τ ] do 5:

if i * (e) = N then 6:

Check that (x (e) [N ], β (e) [N ], c (e) [N ]) = (0, 0, 0). If not, return Reject.

Step 2: Recompute h1 7: md = Hash(DS_M, m) 8: for e ∈ [τ ] do 9:

(seed e) , N, salt, e) 10:

(e) i ) i∈[N ],i =i * (e) = PRGPartialTreeExpand(ptree (
for i ∈ [N ], i = i * (e) do 11: if i = N then 12: (x (e) [i], β (e) [i], a (e) [i], c (e) [i]) = SampleShares(seed (e)
i ) 13: cmt

N , cmt (2) 1 , . . . , cmt (τ ) 1 , • • • , cmt (τ ) N )
Step 3: Recompute h2 20: for e ∈ [τ ] do 21:

for i ∈ [N ], i = i * (e) do
22:

E (e) [i] = M0 + k j=1 x (e) [i]Mj if i = 1 k j=1 x (e) [i]Mj otherwise 23: e (e) [i] = FqMatrixToFqmVector(E (e) [i]) 24: z (e) [i] = -n j=1 γ (e) j e (e)
j [i] q r 25:

α (e) [i] = MPC-MinRank.ComputeAlpha(e (e) [i], a (e) [i], γ (e) , (e) ) 26:

α (e) = i α (e) [i] 27: for i ∈ [N ], i = i * (e) do 28: v (e) [i] = (e) • z (e) [i] -α (e) , β (e) [i] -c (e) [i] 29: v (e) [i * (e) ] = -i =i * (e) v (e) [i] 30: ( α(e) [δ], v(e) [δ]) δ∈[D] = Hypercube.MainAlphaAndV-Compute((α (e) [i], v (e) [i]) i∈[N ] )
31: h2 = Hash(DS_2, md, pk, salt, h1, (α (e) , ( α(e

) [δ], v(e) [δ]) δ∈[D] ) e∈[τ ] )
Step 4: Verify commitments 32: return h1 the power of a prime number, q ∈ N, to build F q ; a positive integer, m ∈ N, the number of rows of our matrices; a positive integer, n ∈ N, the number of columns of our matrices; a positive integer, k ∈ N, the length of the secret vector x, and k + 1 is the number of matrices in the public key;

a positive integer, r ∈ N, the rank of the matrix E;

a positive integer, N ∈ N, the number of parties simulated in the MPC protocol;

a positive integer, η ∈ N, the extension degree to build F q m•η ;

a positive integer, τ ∈ N, the number of rounds in the signature.

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

-The security of the MinRank instance, i.e, the complexity of the attacks on the chosen parameters;

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

-The size of the signature.

MIRA-Additive

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

Once the MinRank instance parameters are chosen, we set N = 256 for a short version of the signature, and N = 32 for a fast one. Then, τ and η need to be such that the security level of the signature is high enough (Section 9.1). We remind that the security levels of the signature 1,3, and 5, correspond respectively to the security of AES-128, AES-192, and AES-256. Finally, we settled on the following parameters: We also give some theoretical signature sizes for other parameters, such as the following one, used in [ARZV22] achieving the security level 1. With (q, m, n, k, r) = (16,16,16,142,4), it is possible to obtain 5.550 Bytes (with short MIRA).

For the security level 3, it would also be possible to use the parameter (16,19,19,195,5), which gives a size of 11.636 Bytes, however, the security of the instance is lower than the parameter we chose. Overall, although it is possible to obtain slightly smaller signature sizes with other parameters, we choose to get slightly bigger signature (less than 100 bytes of difference) with a more conservative security (around 10 bits higher). We refer to the section 9.2, Table6 for the security of our parameter sets.

MIRA-Threshold

Note that in [ABCD + 23], two different variant of MIRA are described, using either an additive sharing scheme, or a threshold sharing scheme. The present specification contains only the additive sharing scheme, since so far, "threshold MPCitH" does not bring a significant advantage compared to "hypercube MPCitH" for the considered protocol for the MinRank problem: with the threshold technique, we obtain faster verification but with a degraded signature size, for similar signing time. This might however change in the future, in the case where threshold techniques were to improve.

Performance Analysis

This section provides performance measures of our implementations of MIRA.

Benchmark platform. Benchmark platform. The benchmarks have been performed on an Intel 13th Gen Intel (R) Core(TM) i9-13900K machine with 64GB of RAM. All the experiments were performed with Hyper-Threading, Turbo Boost, and SpeedStep features disabled. The scheme has been compiled with GCC compiler (version 11.3.0) and uses the XKCP and OpenSSL (version 3.0.2) libraries.

For each parameter set, the results have been obtained by computing the mean from 10 random instances. To minimize biases from background tasks running on the benchmark platform, each instance has been repeated 10 times and averaged.

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

Reference Implementation

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

-Concerning the C code: -O3 -flto.

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

Optimized Implementation

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

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

-Concerning the ASM code (required in the XKCP library): -x assembler-with-cpp -Wa,-defsym,old_gas_syntax=1 -Wa,-defsym,no_plt=1. Notice that one can generate the test files as mentioned above using the kat and verbose modes of the implementation, respectively. The procedure is detailed in the technical documentation (README file of the provided code).

Expected security strength

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

For the hardness of forging the signature, we refer to the following section and the design document, which gives the complexity of the attack on the Fiat-Shamir transform described in [KZ20]. This is the best attack on the Fiat-Shamir signature, and as such, this allows us to choose the parameters τ and η accordingly. Moreover, our signature scheme originates from a zero-knowledge proof of knowledge. The proofs of soundness and zero-knowledge of the proof of knowledge can be found in [ABCD + 23].

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

Theorem 1. Let the PRG used be (t, P RG )-secure, and assume an adversary running in time t has advantage at most M R against the underlying MinRank problem. Let further assume that H 0 , H 1 , H 2 , H 3 , H 4 behave as random oracles, with an output of 2λ bits. Then, if an adversary makes q i queries to H i , q S queries to the signing oracle, and runs in time at most t, their probability to produce a forgery (EUF-CMA) for the MIRA Additive Signature Scheme is upper bounded as:

Pr[Forge] ≤ 3 • (q + τ • N • q S ) 2 2 • 2 2λ + q S • (q S + 5q) 2 2λ + q S • τ • P RG + Pr[X + Y = τ ] + M R
with τ the number of rounds of the signature, X = max i∈[0,q 2 ] {X i } with X i ∼ B(τ, p), and

Y = max i∈[0,q 4 ] {Y i } with Y i ∼ B(τ -X, 1 N ).
We refer to the design document ( [ABCD + 23]) for a proof of this theorem.

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

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

-Forging a valid signature without knowing the secret key (with high probability) requires 2 λ hash computations under the best known forgery attack;

-Access to a signing oracle does not help an attacker to forge a signature.

Our signature scheme relies on the security of hash functions and commitments functions as well. In the unforgeability security proof, they are modelled as random oracles. In practice, we use SHAKE and SHA3 functions, which are collision resistant and preimage resistant. With Grover's algorithm, the complexity to find a preimage is of O(2 n 2 ) (for an hash function with an n bits output), while collisions can be found in O(2 n 3 ) with Brassard's algorithm [BHT98]. However, this last algorithm is unlikely to perform better than O(2 n 2 ) in practice (see [Ber09]). Hence, as many other cryptosystems, we consider here that a hash function with an output of 2 • λ bits provides a quantum security of λ bits.

Resistance to quantum attacks

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

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

Kales and Zaverucha attack on the Fiat-Shamir transform

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

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

τ = arg min 0≤τ ≤τ 1 P 1 + 1 P 2 τ -τ
where P 1 and P 2 are the probabilities to pass respectively the first challenge τ times among the τ repetitions and the second challenge one time.

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

cost forge = min 0≤τ 1 ≤τ 1 τ i=τ 1 τ i p i (1 -p) τ -i + (N ) τ -τ 1
where p is the false positive rate of the protocol Π η , i.e, p = 2 q mη -1 q 2mη

Attacks on MinRank

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

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

M P = 0 m×a M .
As M has rank r, it can be written M = SC with S ∈ F m×r q of rank r and C ∈ F r×n q , and cancelling the first a columns of M P corresponds to the cancellation of the first a columns of CP , which has a probability Ω(q -ar ) to happen. This leads to a smaller MinRank problem, obtained by eliminating am variables x i (using the am linear equations coming from the cancellation of the a columns of M P ) in the matrix M , that has still rank r. This new problem has parameters (q, m, n -a, K -am, r).

If a solution to the small instance is found, then the solution of the original problem can be recovered by mutiplying it on the right by P -1 . The cost of this approach is min a (q ar C A (q, m, n -a, K -am, r))

(1)

where C A (q, m, n, K, r) is the cost of an algorithm A to solve a MinRank problem.

The cost of the transformation is 2mn ω-1 + 3n ω (for the multiplication by P , computation and multiplication by P -1 ) +3(am) ω-1 K (for the linearization of the am linear equations) +am 2 (n -a)(K -am) (for the elimination of am variables x), which is negligeable.

The kernel attack

The kernel attack was described by Goubin and Courtois in [GC00]. The idea of the attack is to take random vectors, and hoping that they are in the kernel of E. Since E is of size m × n, and is of rank at most r, Ker(E) will be a matrix of dimensions n × (n -r) at least. Thus, if v $ ←-F n q , Pr[v ∈ Ker(E)] = q n-r q n = 1 q r . Then, if we get l independant vectors in Ker(E), and set the matrix X whose columns are the l vectors, we can compute (M 0 + k i=1 x i M i )X, which gives us a linear system in x 1 . . . x k , and m • l equations (since we have (M 0 + k i=1 x i M i )X = 0). Thus with l = k m , we have a unique solution to the system, which we can find with linear algebra. As to the complexity of the attack, it is quite obvious that it is in O(q r k m ) to find the vectors in the kernel, and in O(k ω ) to solve the linear system. Hence, the total complexity is O(q r k m k ω )

Algebraic attacks

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

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

HS(t) def = (1 -t) (m-r)(n-r)-(k+1) det(A(t)) t ( r 2 ) , with A(t) = max(m-i,n-j) =0 m-i n-j t 1≤i≤r,1≤j≤r
where for a series S ∈ Z[[t]], [S] denotes the series obtained by truncating S at the first non-positive coefficient.

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

Support Minors Modeling

The Support Minors modeling was introduced in [BBC + 20].

The idea is to consider the vector space generated by the rows of M , that has rank r, to introduce a formal matrix C ∈ F q [c i,j ] r×n representing a generator matrix of this vector space. As C is a basis for the rows of M , each row m i of M is a linear combination of the rows of C. This leads to the algebraic system SupportMinors = MaximalMinors m i C : m i row of M .

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

N b = b i=1 (-1) i+1 n r + i k + b -1 -i b -i m + i -1 i .
(2)

M b = k + b -1 b n r . (3)
The degree b is computed as the smallest degree such that N b ≥ M b -1. In this case, the final cost in F q operations is given by

O N b M b ω-1 ,
where ω is the linear algebra constant. Table 6: Complexity of the MinRank attacks for the proposed parameters. a is the hybrid parameter used for each attack, b the degree for the Support Minors modeling, D the degree for the Minors modeling. The complexities are given in log 2 bit operations. We use ω = 2.

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

10 Advantages and limitations

Advantages

The MIRA scheme enjoys the following advantages:

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

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

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

Resilience against MinRank attacks: Because of the way the size of the signature is obtained: one part is related to the MPC and only dependent on the security level and one part is related to the parameters of the problem in themselves, increasing the size of the problem parameters has a mitigated impact on the total size of the signature. For example, the short signature size's is 5.6 kB for the set of parameters (q, m, n, k, r) = (16,16,16,120,5) for the level 1 of security. If we choose the parameters (q, m, n, k, r) = (16,19,19,168,6), which reaches more than 192 bits of security for the underlying cryptographic problem, the

  2 15: x = FqArrayFromBytes(k, PRG.GetBytes(k_bytes)) 16: return E, supp, x Algorithm 7 SampleSeeds Input: Length , Number of seeds τ , a seed seed Output: (seed (e) ) e∈[τ ] ∈ ({0, 1} ) τ PRG.Init(seed) for i ∈ [τ ] do seed (e) = PRG.GetBytes( ) return (seed (e) ) e∈[τ ]

  15: x = y + f 16: e = FqMatrixToFqmVector(E) 17: β = ComputeAnnihilatorPolynomial(supp) 18: return (M0, . . . , M k , x, β, e) Algorithm 16 ParsePublicKey Input: Public key pk Output: M0, . . . , M k 1: (pk_seed, m_bytes) = pk 2: PRG.Init(pk_seed) 3: L_bytes = k(mn-k) 2 4: L = FqMatrixFromBytes(k, mn-k, PRG.GetBytes(L_bytes)) 5: L = (I k |L ) 6: for i ∈ [k] do 7: for j ∈ [m] do 8: for ∈ [n] do 9: (Mi) j, = L i,(j-1)n+ 10: M0 = FqMatrixFromBytes(m, n, m_bytes) 11: return (M0, . . . , M k ) 4.8 PRG tree routines Algorithm 17 PRGTreeExpand Input: A root seed seed, a number of parties N = 2 D , a salt and an iteration index e Output: A family of seeds (seedi) i∈[N ]

  seedD, N/2, salt, e) 5: else 6:(seedi) i∈[N/2] = PRGTreeExpand(seed1, N/2, salt, e) 7:(seedi) i∈[N/2+1,N ],i =i * = PRGPartialTreeExpand((seedi) i∈[2,D] ) 8: return (seedi) i∈[N ],i =i *4.9 Protocol specificationAlgorithm 20 MIRA_keygenInput: Security level λ Output: Secret key sk, public key pk1: sk_seed = RandomBytes(λ) 2: pk_seed = RandomBytes(λ) 3: pk_PRG.Init(pk_seed) 4: L_bytes = k(mn-k) 2 5: L = FqMatrixFromBytes(k, mn-k, pk_PRG.GetBytes(L_bytes)) 6: L = (I k |L ) 7: for i ∈ [k] do 8: for j ∈ [m] do 9:for ∈ [n] do 10:(Mi) j, = L i,(j-1)n+11: (E, _, y) = SampleSecretInstance(sk_seed) 12: F = Ek i=1 yiMi 13: for i ∈ [k] do 14: fi = F 1+ i-1 n ,1+((i-1) mod n) 15: M0 = Fk i=1fiMi16: pk = pk_seed || FqMatrixToBytes(M0) 17: sk = sk_seed || pk_seed 18: return sk, pk Algorithm 21 MIRA_Sign Input: Secret key sk, public key pk, message m ∈ {0, 1} * Output: Signature σ ∈ {0, 1} * Step 0: Parse keys 1: (M0, . . . , M k , x, β, e) = ParseSecretKey(sk) Step 1: Commitment 2: salt = RandomBytes(2λ) 3: mseed = RandomBytes(λ) 4: md = Hash(DS_M, m) 5: (seed (e) ) e∈[τ ] = SampleSeeds(λ, τ , mseed) 6: for e ∈ [τ ] do 7:

N

  = Hash(DS_C, salt, e, N, seed(e) i , x (e) [N ], β (e) [N ], c (e) [N ]) 19: ( x(e) [δ], β(e) [δ], â(e) [δ], ĉ(e) [δ]) δ∈[D] = Hypercube.MainShares-Compute((x (e) [i], β (e) [i], a (e) [i], c (e) [i]) i∈[N ] )20: h1 = Hash(md, pk, salt, DS_1, cmt

  [δ], v(e) [δ]) δ∈[D] = MPC-MinRank.Exec ( x(e) [δ], β(e) [δ], â(e) [δ], ĉ(e) [δ]) δ∈[D] , γ (e) , (e) , α (e) , M0, . . . , M k 25: h2 = Hash(md, pk, salt, h1, DS_2, (α (e) , ( α(e) [δ], v(e) [δ]) δ∈[D] ) e∈[τ ] )

N

  = Hash(DS_C, salt, e, N, seed (e) i , x (e) [N ], β (e) [N ], c (e) [N ]) 19: h1 = Hash(DS_1, md, pk, salt, cmt

?

  Our signature scheme uses the following parameters:

  : A root seed seed, a number of parties N = 2 D , a salt and an iteration index e, a hidden index i * Output: A partial tree, i.e. a family of seeds (seedi) i∈[D]

	1: (seed_left, seed_right) = Hash(DS_T, salt, e, seed)
	2: if D = 1 then
	3:	if i * = 1 then
	4:	return seed_right
	5:	else
	6:	return seed_left
	7: else
	8:	if i * ≤ N/2 then
	9:	(seedi) i∈[1,D-1] = PRGPartialTreeReveal(seed_left, N/2, salt, e, i * )
	10:	seedD = seed_right
	11:	else
	12:	seed1 = seed_left
	13:	(seedi)

i∈[1,N/2] = PRGTreeExpand(seed_left, N/2, salt, e) 6: (seedi) i∈[N/2+1,N ] = PRGTreeExpand(seed_right, N/2, salt, e) 7: return (seedi) i∈[N ] Algorithm 18 PRGPartialTreeReveal Inputi∈[2,D] = PRGPartialTreeReveal(seed_right, N/2, salt, e, i * -N/2) 14: return (seedi) i∈[D]

Table 3 :

 3 Parameters for MIRA with additive sharing, fast and short signatures One should note that we obtain slightly larger signature size, due to rounding of bytes when m is odd. For MIRA-192F, we have 15.560 B, MIRA-192S gives 11.792 B, MIRA-256F, 27.732 B and MIRA-256S 20.796 B.

Table 4 :

 4 Thousand (K) and Million (M) of CPU cycles of MIRA reference implementation.

Table 5 :

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

signature size will only be 6.3 kB to reach the level 1 of security. Thus, if one later discovers effective attacks against the MinRank problem that force us to increase the parameters, the size of the signatures will only be impacted that much.

Limitations

MIRA also suffers the following limitations:

Growth rate of the signature size. The size of the signature grows with a quadratic rate when increasing the security level. This comes from the fact that both the MinRank instance and the number of repetitions need to increase linearly, since both the Fiat-Shamir transform and the MinRank instance need to be secure (we see that going from level 1 to 3, the number of repetitions is increased by almost half, while the MinRank instance grows as well).

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

Implementation. This scheme is relatively complex to implement. It might be particularly heavy for low-cost devices such as smart cards or embedded systems, although it has potential to perform well on hardware as being highly parallelizable.