Luk Bettale

Delaram Kahrobaei

Ludovic Perret

Javier Verbel

Biscuit: New MPCitH Signature Scheme from Structured Multivariate Polynomials

Keywords: Post-Quantum, Digital Signature, MPC-in-the-Head, Multivariate Polynomials

This paper describes Biscuit, a new multivariate-based signature scheme derived using the MPCitH approach. The security of Biscuit is related to the problem of solving a set of quadratic structured systems of algebraic equations. These equations are highly compact and can be evaluated using very few multiplications. The core of Biscuit is a rather simple MPC protocol which consists of the parallel execution of a few secure multiplications using standard optimized multiplicative triples. This paper also includes several improvements with respect to Biscuit submission to the last NIST PQC standardization process for additional signature schemes. Notably, we introduce a new hypercube variant of Biscuit, refine the security analysis with recent third-party attacks, and present a new avx2 implementation of Biscuit.

Introduction

Biscuit is a new multivariate-based digital signature scheme submitted to the recent NIST standardization process for additional post-quantum signature schemes [START_REF]Call for Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process[END_REF]. The security of Biscuit is proven assuming the hardness of the so-called PowAff2 problem (Definition 1), which is a structured version of the well-known Multivariate Quadratic (MQ) problem [START_REF] Bellini | An estimator for the hardness of the MQ problem[END_REF]. Biscuit is in the lineage of the Picnic signature scheme [START_REF] Chase | Post-quantum zero-knowledge and signatures from symmetric-key primitives[END_REF][START_REF] Zaverucha | Picnic : Algorithm specification and design document[END_REF], which was selected as an alternate candidate in the first NIST post-quantum cryptography standardization process [START_REF] Alagic | Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process[END_REF]. The security of Picnic relays in the hardness of finding that secret key sk used to produce plaintext-ciphertext pair using a particular block-cipher. The design of Picnic builds over a Multi-Party Computation (MPC) protocol to check that shared a triple of elements in a finite field (z, x, y) is multiplicative, i.e., the MPC protocol checks whether or not z = xy. Then it follows the MPC-in-the-Head (MPCitH) paradigm (introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai in 2007 [START_REF] Ishai | Zero-knowledge from secure multiparty computation[END_REF]) to obtain Zero-Knowledge Proof-of-Knowledge (ZKPoK) of the key sk. Finally, the signature scheme is obtained by applying the Fiat-Shamir transformation [START_REF] Fiat | How to Prove Yourself: Practical Solutions to Identification and Signature Problems[END_REF] to the ZKPoK protocol. As in Picnic, the design of Biscuit follows the MPCitH paradigm, and it uses the same MPC protocol to check multiplicative triples. Contrary to Picnic, in Biscuit the main goal is to build a ZKPoK of a pre-image s of a quadratic system of multivariate polynomial equations f over a finite field. The private and public keys in Biscuit are respectively s and (f , t), where t = f (s). The performance of Picnic is proportional to the number of multiplications required to evaluate the circuit defining the underlying encryption function with the secret key sk. This fact motivates the use of a set f of polynomial equations that require a small of multiplication to be evaluated. Biscuit considers polynomials of the form f i = A 0 + A 1 • A 2 , where each A i is linear polynomial. These polynomials can be evaluated computing only one multiplication, while a random quadratic polynomial would require as many multiplications as the number of variables.

Other Submitted MPCitH Signature Schemes

Since Picnic, the use of MPCitH for designing post-quantum signature schemes has become extremely popular. These is evidenced in the new NIST standardization process for post-quantum signature schemes 8 , where eight among forty of the submitted schemes are MPCitH-based. These schemes follow the same design methodology but differ on the hard problems considered.

AIMer is based on the hardness of key-recovery of a MPC-friendly block-cipher [START_REF] Kim | AIMER specification[END_REF], MIRA and MiRitH are based on the MinRank problem [START_REF] Aragon | MIRA specification[END_REF][START_REF] Adj | MiRitH specification[END_REF], MQOM is based on the problem of solving random quadratic equations [START_REF] Feneuil | MQOM specification[END_REF], PERK is based on the Permuted Kernel Problem [START_REF] Aaraj | PERK specification[END_REF], RYDE is based on the rank syndrome decoding problem [START_REF] Aragon | RYDE specification[END_REF], and SDith relies on the syndrome decoding problem [START_REF] Aguilar Melchor | SDITH specification[END_REF]. All these schemes proposed several parameter sets parameter in order to optimize either the signature size (short variant) or the signing and verification times (fast variant). Table 1: Performance of level I short variants of MPCitH-based candidates in the first round of the NIST new call for post-quantum signature schemes.

In Table 1, we overview a performance of the MPCitH NIST candidates with version of Biscuit described in this paper. In the table we also includes FAEST whose security is based on AES, and uses a new zero-knowledge technique, named VOLE-in-the head, that improves the MPCitH approach [START_REF] Baum | FAEST specification[END_REF]. For each scheme, we report one short variant of achieving level I of security (i.e. equivalent to the security of AES128). The key-generation (keygen), signature generation (sign) and verification (verify) times are shown in number of clock-cycles (cycles). Table 1 also includes secret-key (sk), public-key (pk) and signature (σ) sizes in bytes.

Remark 1. Few days before finalizing this manuscript a new preprint appeared [START_REF] Feneuil | Threshold computation in the head: Improved framework for post-quantum signatures and zero-knowledge arguments[END_REF] that seems to significantly improve MQOM as well as many MPCitH-based signature schemes (including Biscuit).

Organization of the Paper and Main Results

After this introduction, the paper is organized as follows. Section 2 introduces basic notations, the new hard problem considered in Biscuit (PowAff2 problem, Section 2.2), as well as the basic cryptography building blocks underlying its design: Multi-Party Computation (MPC), MPC-in-the-Head approach (MPCitH), Zero-Knowledge Proof of Knowledge (ZKPoK), BN-like proof systems and the hypercube technique for MPCitH-based signature schemes. Section 3 describes the core sub-protocols underlying Biscuit. Due to the structure of the algebraic systems considered in Biscuit, the evaluation of a PowAff2 solution requires only one multiplication per equation. This leads to a rather simple MPC protocol (Section 3.1) for PowAff2 that is based on the parallel execution of secure multiplication using Beaver multiplicative triples [START_REF] Beaver | Efficient multiparty protocols using circuit randomization[END_REF] with some optimizations from [START_REF] Baum | Concretely-efficient zero-knowledge arguments for arithmetic circuits and their application to lattice-based cryptography[END_REF][START_REF] Kales | Efficient lifting for shorter zero-knowledge proofs and post-quantum signatures[END_REF]. Then, we derive a new ZKPoK for PowAff2 (Section 3.2) using the MPCitH approach. Note that the protocol presented here (Figure 3) differs from the one described in the initial Biscuit submission [START_REF] Luk Bettale | Biscuit: Shorter MPC-based Signature from PoSSo[END_REF]. In particular, we use the hypercube technique [START_REF] Aguilar Melchor | The return of the sdith[END_REF] and also include a security proof (Theorem 1) of the new ZKPoK.

Section 4 presents the Biscuit signature scheme and details the key generation (Figure 7), signature generation (Figure 8) and verification (Figure 9) algorithms. Biscuit is constructed using the traditional Fiat-Shamir transform from the ZKPoK described in Figure 3. We conclude this part with Table 2 that summarizes the secret-key, public-key, and signature sizes for the three security levels of NIST. In particular, Biscuit achieves a signature of 5.7KB for the first security level. This is comparable to other recent MPCitH-based signature schemes (Section 1.1).

Section 5 analyzes the security of the parameters proposed in Table 2. This section revisits the security analysis performed in the initial submission of Biscuit by taking into account new thirdparty analysis. In Section 5.1, we first explain the connection between the hardness of PowAff2 and the difficulty of solving the Learning With (bounded) Errors (LWE) problem [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. In Section 5.2, we consider the key-recovery problem where the best attack against is a dedicated hybrid approach (i.e. that combines exhaustive search and Gröbner bases [START_REF] Bettale | Solving polynomial systems over finite fields: improved analysis of the hybrid approach[END_REF][START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF][START_REF] Bardet | On the Complexity of Solving Quadratic Boolean Systems[END_REF]) for solving PowAff2 equations described by Charles Bouillaguet on the NIST PQC9 mailing-list. In Section 5.3, we consider forgery attacks. In particular, we refine the analysis of Kales and Zaverucha [START_REF] Kales | An attack on some signature schemes constructed from five-pass identification schemes[END_REF] for forgery attacks against 5-pass Fiat-Shamir based signature schemes. This leads us to introduce a variant of the PowAff2 problem where the attacker has to solve a sub-system with fewer equations; leading to the introduction of the PowAff2 u problem (Definition 1).

Finally, Section 6 presents an optimized implementation of Biscuit which outperforms the previous implementation. First, we use a new canonical representation of the PowAff2 equations (Lemma 1) which allows us to further simplify their evaluation. Then, we integrate the hypercube framework for even further improvement.

Preliminaries

This section presents the preliminary concepts and notations used throughout the paper.

Notations

All over this paper, we use λ for the security parameter, [n] refers to the set {1, . . . , n} for an integer n ∈ N, F q is the finite field of q elements (where q is prime or a prime power), F m q denotes the vector space of dimension m over F q and F q [x 1 , . . . , x n ] the ring of polynomials in the variables x 1 , . . . , x n over the field F q .

Bold lower-case letters denote vectors, x + y denotes the element-wise addition, x ⊙ y denotes the element-wise product and ∥ the concatenation of two vectors or two-byte strings. a ← A(x) indicates that a is the output of an algorithm A on input x, a $ ← S means that a is sampled uniformly at random from a set S.

Let R be a ring and a ∈ R. additive sharing of a, denotes a is a tuple a := ( a 1 , . . . , a N ) ∈ R N such that a = N i=1 a i . Each component a i of a is called a share of a. Throughout this paper, we only consider additive sharing and use the word sharing to refer to additive sharing.

A Multi-Party Computation (MPC) protocol is an interactive protocol executed by a set of N parties knowing a public function f . Its goal is to compute the image z = f (x 1 , . . . , x N ), where the value x i is only known by the i-th party. An MPC protocol is considered secure and correct if, at the end of the protocol, every party i knows z, and no information about its secret input value x i is revealed to the other parties.

The PowAff2 u Problem

The core problem considered in Biscuit is the one of solving a system of multivariate equations defined as the product of two affine forms. This problem, denoted as PowAff2 u , is parameterized by a tuple of positive integers (n, m, u, q), where n is the number of variables, m the number of equations, u is a parameter related to forgery (Section 5.3), and q is the finite field size.

Definition 1 (The PowAff2 u problem).

Let A 1,0 , A 1,1 , A 1,2 , . . . , A m,0 , A m,1 , A m,2 ∈ F q [x 1 , . . . , x n ] be affine forms, i.e.:

A k,j (x 1 , . . . , x n ) = a (k,j) 0 + n i=1 a (k,j) i x i , with a (k,j) 0 , . . . , a (k,j) n ∈ F q .
(1)

Input. A vector t = (t 1 , . . . , t m ) ∈ F m q and multivariate polynomials f = (f 1 , . . . , f m ) ∈ F q [x 1 , . . . , x n ] m defined as:

f k (x 1 , . . . , x n ) = A k,0 (x 1 , . . . , x n ) + 2 j=1 A k,j (x 1 , . . . , x n ), ∀k ∈ [m]. (2)
Question. Find -if any -a vector (s 1 , . . . , s n ) ∈ F n q and set J ⊆ [m] of size m -u such that:

f j (s 1 , . . . , s n ) = t j , ∀j ∈ J.
Definition 2 (The PowAff2 problem). We use PowAff2 to denote the PowAff2 0 problem. Also, we shall call PowAff2 algebraic system the set of non-linear equations f 1 , . . . , f m ∈ F q [x 1 , . . . , x n ] defined as in (2).

PowAff2 is the problem corresponding to key-recovery whilst PowAff2 u , with u > 0, is a relaxation that corresponds to signature forgery.

A detailed hardness analysis of PowAff2 u is provided in Section 5. The current best attack against Biscuit has been sketched by Charles Bouillaguet on the NIST PQC mailing-list 10 . In particular, it was mentioned that the multivariate equations defined as in Definition 1 can be reduced to a simple, but equivalent, structure.

Lemma 1. Let f = (f 1 , . . . , f m ) ∈ F q [x 1 , . . . ,
x n ] m be a PowAff2 algebraic system. Then, with high probability, there exists an invertible matrix L ∈ GL n (F q ) such that :

f x • L = u 1 (x) • (x 1 + c 1 ) + w 1 (x), . . . , u n (x) • (x n + c n ) + w n (x), A ′ n+1,0 (x) + 2 j=1 A ′ n+1,j (x), . . . , A ′ m,0 (x 1 , . . . , x n ) + 2 j=1 A ′ m,j (x)
where x = (x 1 , . . . , x n ), A n+1,0 , A n+1,1 , A n+1,2 , . . . , A m,0 , A m,1 , A m,2 , u 1 , . . . , u n , v 1 , . . . , v n ∈ F q [x 1 , . . . ,
x n ] are affine polynomials and c 1 , . . . , c n ∈ F q .

Proof. By construction, we have :

f k (x 1 , . . . , x n ) = A k,0 + 2 j=1 A k,j , ∀k ∈ [m],
with A 1,0 , A 1,1 , A 1,2 , . . . , A m,0 , A m,1 , A m,2 ∈ F q [x 1 , . . . , x n ] affine forms as defined in [START_REF]Call for Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process[END_REF].

Thus, we can write

A k,2 (x 1 , . . . , x n ) = (x 1 , . . . , x n ) • b k + c k , where b k = (a (k,2) 1 , . . . , a (k,2) n ) ∈ F n q and c k = a (k,2) 0 ∈ F q . Let C ∈ F n×n q
be the matrix whose rows are b 1 , . . . , b n . We want to find a non-singular matrix L ∈ GL n (F q ) such that I n = C • L, where I n is the identity matrix of size n. This reduces to compute, if any, the inverse of C.

Digital Signature Scheme

Definition 3. A Digital Signature Scheme (DSS) is a tuple of three probabilistic polynomial-time algorithms (KeyGen, Sign, Verify) verifying:

1. (pk, sk) ← KeyGen(1 λ ). The key-generation algorithm KeyGen takes as input a security parameter 1 λ and outputs a pair of public/private keys (pk, sk). 2. σ ← Sign(sk, msg). The signing algorithm Sign takes a private key sk and a message msg ∈ {0, 1} * and outputs a signature σ. 3. b ← Sign(pk, σ, msg). The verification algorithm Verify is deterministic. It takes as input a message msg ∈ {0, 1} * , a signature σ, and a public key pk. It outputs a bit b ∈ {0, 1} : 1 means that it acceptsσ as a valid signature for msg, otherwise it rejects outputting 0.

A signature scheme is correct if for every security parameter λ ∈ N, every (pk, sk) ← KeyGen(1 λ ), and every message msg ∈ {0, 1} * , it holds that 1 ← Verify pk, msg, Sign(sk, msg) .

The standard security notion for a DSS is Existential Unforgeability under Adaptive Chosen-Message Attacks (EU-CMA). We say that a signature scheme is EU-CMA-secure if for all probabilistic polynomial-time adversaries A, the probability

Pr 1 ← Verify(pk, msg * , σ * ) (pk, sk) ← KeyGen(1 λ ) (msg * , σ * ) ← A O Sign(sk,•) (pk)
is a negligible function in λ, where A is given access to a signing oracle O Sign(sk,•) , and msg * has not been queried to O Sign(sk,•) .

Auxiliary Functions. Biscuit also relies on further basic cryptographic building blocks that we do not explicitly introduce such as commitments, collision-resistant hash functions, keyderivation functions, and pseudo-random number generators. As explained in [START_REF] Luk Bettale | Biscuit: Shorter MPC-based Signature from PoSSo[END_REF], we can use the SHAKE256 [START_REF]SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions[END_REF] extendable-output function (XOF) to instantiate these functions. During signature, the signer must generate a set of N seeds and reveal N -1 of them to the verifier for each iteration (TreePRG). The verifier then uses these seeds to check that the MPC protocol was correctly simulated. A binary tree structure allows generating the seeds using one root seed from a binary tree. Instead of sending N -1 seeds in the signature, this allows sending only ⌈log 2 N ⌉ seeds that will be used to reconstruct all N -1 seeds required. We refer to [START_REF] Luk Bettale | Biscuit: Shorter MPC-based Signature from PoSSo[END_REF] for the description of TreePRG.

5-Pass Identification Schemes

An IDentification Scheme (IDS) is an interactive protocol between a prover P and a verifier V, where P wants to prove its knowledge of a secret value sk to V, with (pk, sk) satisfying a given relation, for a public value pk. Definition 4 (5-pass identification scheme). A 5-pass IDS is a tuple of three probabilistic polynomial-time algorithms (KeyGen, P, V) such that 1. (pk, sk) ← KeyGen(1 λ ). The key-generation algorithm KeyGen takes as input a security parameter 1 λ and outputs a pair of public/private keys (pk, sk). 2. P and V follow the protocol in Figure 1, and at the end of this, V outputs 1, if it accepts that P knows sk, otherwise it rejects outputting 0.

A transcript of a 5-pass IDS is a tuple (com, ch 1 , rsp 1 , ch 2 , rsp 2 ), as in Figure 1, referring to all the messages exchanged between P and V in one execution of the IDS. We require an IDS to fulfill the following security properties.

Correctness: if for any security parameter λ ∈ N and (pk, sk)

← KeyGen(1 λ ) it holds, Pr [1 ← V(pk, com, ch 1 , rsp 1 , ch 2 , rsp 2 )] = 1, where (com, ch 1 , rsp 1 , ch 2 , rsp 2 )
is the transcript of an execution of the protocol between P(pk, sk) and V(pk).

Soundness (with soundness error ε): if, given a key pair (pk, sk), for every polynomial-time adversary A such that

Honest-verifier zero-knowledge: if there exists a probabilistic polynomial-time simulator S(pk) that outputs a transcript (com, ch1, rsp 1 , ch2, rsp 2 ) from a distribution that is computationally indistinguishable from the distribution of transcripts of an honest execution of the protocol between P(pk, sk) and V(pk).

P(pk, sk) V(pk)

com ← P 0 (pk, sk) com ch 1 $ ← ChallengeSet 1 ch 1 rsp 1 ← P 1 (pk, sk, com, ch 1 ) rsp 1 ch 2 $ ← ChallengeSet 2 ch 2 rsp 2 ← P 2 (pk, sk, com, ch 1 , rsp 1 , ch 2 ) rsp 2 V (pk, com, ch 1 , rsp 1 , ch 2 , , rsp 2 )
Fig. 1: Canonical 5-pass IDS.

2.5 MPC-in-the-Head : From MPC to Zero-Knowledge MPC-in-the-Head (MPCitH) is a generic technique, introduced as "IKOS" [START_REF] Ishai | Zero-knowledge from secure multiparty computation[END_REF]), that allows to build a Zero-Knowledge Proof of Knowledge (ZKPoK) from a secure MPC protocol.

Consider a MPC protocol where N parties P1 . . . , PN collaborate to securely evaluate a public function f on a secret input x. Assuming that the protocol is perfectly correct and that the views of t < N parties leak no information on x, then one can construct a ZKPoK from the MPC protocol as follows:

1. Simulation.

-Prover P generates a random sharing x := ( x 1 , . . . , x N ) of x such that x = N i=1 x i and assign a share x i to each party Pi.

-P emulates "in his/her mind" execution of the MPC protocol with N parties P1 . . . , PN .

-P commits on the views of each Pi, meaning the messages they send/receive during the protocol execution and their internal states. These commitments are sent to the verifier V. 2. Challenges.

-P possibly receives random challenges from V on the MPC, executes local computations accordingly and send the results to V. This step can be repeated several times. -V challenges P to open a random subset of t parties.

-P returns the requested views. 3. Verification.

-P then checks that the views11 are consistent, and the output of the circuit corresponds to the result expected.

Since its introduction, the initial approach for MPCitH from [START_REF] Ishai | Zero-knowledge from secure multiparty computation[END_REF] has been improved in different ways. In particular, Katz, Kolesnikov and Wang (KKW) extended the MPCitH paradigm to support what is known in MPC as the preprocessing model, where MPC protocols are split into an offline phase that is independent of the sensitive inputs, and an online phase, with the former being typically the bottleneck in terms of efficiency. The benefit is that the prover does not need to include the preprocessing as part of the views of the parties, and instead, the preprocessing can be checked. As an application, KKW allowed to significantly decrease the signature size of the Picnic initial version.

Also, [START_REF] Aguilar Melchor | The return of the sdith[END_REF] described a so-called hypercube variant of MPCitH that allows improving efficiency for a large number of parties in the MPC protocol. Indeed, a large number of parties leads to shorter signatures but increases signature generation and verification times. We detail the approach in the case of Biscuit in Section 3.1.

Proof Systems for Arbitrary Circuits

In [START_REF] Giacomelli | ZKBoo: Faster Zero-Knowledge for Boolean Circuits[END_REF], Giacomelli, Madsen and Orlandi demonstrated the efficiency of the MPCitH approach for generating ZKPoK. Doing so, the authors also introduced a new generic proof system, called ZKBoo, which ultimately resulted in the first version of the Picnic signature scheme. In such work, the virtual/emulated parties actually execute some MPC protocols, and the verifier checks this execution. In [START_REF] Baum | Concretely-efficient zero-knowledge arguments for arithmetic circuits and their application to lattice-based cryptography[END_REF], Baum and Nof proposed an improved proof system, called BN, for arithmetic circuits. [START_REF] Baum | Concretely-efficient zero-knowledge arguments for arithmetic circuits and their application to lattice-based cryptography[END_REF] observed that the prover knows all the wire values in the circuit, and instead of computing a protocol, the prover can distribute sharings for each intermediate wire value, and the virtual parties only need to execute a protocol that checks the correctness of the multiplication gates. This allows batching the checks by taking random linear combinations. In [START_REF] Kales | Efficient lifting for shorter zero-knowledge proofs and post-quantum signatures[END_REF], Kales and Zaverucha built on top of BN and introduced BN++ that includes several optimizations, leading to a roughly 2.5× communication improvement. The authors apply their techniques to AES as well as LowMC (Picnic signature).

The BN and BN++ proof systems rely on the concept of multiplicative triple (or Beaver triple [START_REF] Beaver | Efficient multiparty protocols using circuit randomization[END_REF]). Given x, y, z ∈ Fq, we say that the triple ( x , y , z ) ∈ F N q × F N q × F N q is a multiplicative triple if it holds that z = x • y. The Biscuit MPC protocol will rely on a somewhat standard protocol introduced in [START_REF] Baum | Concretely-efficient zero-knowledge arguments for arithmetic circuits and their application to lattice-based cryptography[END_REF] (along with the optimization given in [30, Section 2.5]) to check multiplicative triples of sharing (Section 2.6). A multiplication triple ( x , y , z ) ∈ F N q × F N q × F N q can be checked using a correlated triple ( a , y , c ) ∈ F N q × F N q × F N q with a ∈ Fq and c = a • y ∈ Fq as follows:

1. The parties get a random element ε

$ ← Fq. 2. The parties locally set α ← x • ε + a . 3.
The parties open α so that they all obtain α.

The party locally compute

v = y • α -z • ε -c . 5.
The parties open v to obtain v. 6. The parties output accept if v = 0 and reject otherwise.

The security of this simple protocol has been proven in [START_REF] Kales | Efficient lifting for shorter zero-knowledge proofs and post-quantum signatures[END_REF]. In particular, the false success probability is given by:

Lemma 2. Let x, y, z, a, c ∈ Fq. If the shared multiplicative triple ( x , y , z ) ∈ F N q × F N q × F N q is incorrect, i.e. z ̸ = x • y, or the helping multiplicative triple ( a , y , c ) ∈ F N q × F N q × F N q is incorrect, i.e. c ̸ = a • y,
then the parties outputs accept with probability at most 1/q.

Interactive Protocols for PowAff2

This section describes the MPC protocol underlying Biscuit (Section 3.1) and the corresponding ZKPoK (Section 3.2) obtained using the MPCitH paradigm (Section 2.5) together with the hypercube technique [START_REF] Aguilar Melchor | The return of the SDitH[END_REF].

Multi-Party Computation Protocol for PowAff2

In Figure 2, we detail the MPC protocol used in Biscuit to check a solution of a PowAff2 algebraic system. The protocol is executed by N parties sharing a secret vector s ∈ F n q . Every party knows the target vector t = (t1, . . . , tm) ∈ F n q , affine forms A1,0, A1,1, A1,2, . . . , Am,0, Am,1, Am,2 ∈ Fq[x1, . . . , xn] as in (1) and the corresponding PowAff2 algebraic equations f = (f1, . . . , fm) ∈ Fq[x1, . . . , xn] m defined as:

f k = A k,0 + A k,1 • A k,2 , ∀k ∈ [m]. (3)
The MPC protocol (Figure 2) consists of m iterations of the multiplicative checking protocol described in Section 2.6). At the end of the protocol, the parties output accept indicating they are convinced that the shared vector s satisfies t = f (s). Otherwise, they output reject.

Public data: t = (t1, . . . , tm) ∈ F m q , affine polynomials A1,0, . . . , Am,2 ∈ Fq[x1, . . . , xn] and f = (f1, . . . , fm) ∈ Fq[x1, . . . , xn] n as defined in [START_REF] Aaraj | PERK specification[END_REF] .

Inputs : The i-th party knows s i ∈ F n q , a i ∈ F m q where a = (a1, . . . , am)

$ ← F m q , and c i ∈ F m q where c = (c1, . . . , cm) ∈ F m q such that c k = A k,2 (s) • a k , ∀k ∈ [m]. MPC protocol: for k ∈ [m] do 1 : The parties locally compute z k ← t k -A k,0 ( s ), x k ← A k,1 (
s ), and y k ← A k,2 ( s ) .

2 : The parties get a random element ε k $ ← Fq.

3 : The parties locally set

α k ← x k • ε k + a k . 4 :
The parties open α k so that they all obtain α k .

5 : The party locally compute

v k = y k • α k -z k • ε k -c k . 6 : The parties open v k to obtain v k .
The parties output accept if v k = 0, ∀k ∈ [n] and reject otherwise.

Fig. 2: MPC protocol Π to check that t = f (s).

The following proposition follows easily from Lemma 2.

Proposition 1. Suppose that a set of N parties genuinely follow the MPC protocol given in Figure 2 with inputs t ∈ F m q , f = (f1, . . . , fm) ∈ Fq[x1, . . . , xn] m , and s ∈ F n q N . Suppose s ∈ F n q is a solution to PowAff2u(f , t) but not a solution to the PowAff2u-1(f , t). If u = 0, i.e., t = f (s), then the parties accept. Otherwise, the parties accept with probability at most 1/q u .

ZKPoK for PowAff2

In Figure 3, we derive a ZKPoK for the PowAff2 problem using the MPC protocol Π of Figure 2. To do so, we use the traditional MPCitH approach combined with the recent hypercube technique.

In Phase 1, for each ℓ ∈ [D] the prover generates an input set S ℓ = s (ℓ,j) , c (ℓ,j) , a j∈ [START_REF]Biscuit github repository[END_REF]) for a two parties instance the MPC protocol Π (Figure 2). The set S ℓ is called the ℓ-th set of main shares. The sets of main shares are computed in two steps. First, there prover generates and commits to inputs ( s i , c i , a i ) of one N = 2 D parties instance of Π. Then, for each (ℓ, j) ∈ [D] × [START_REF]Biscuit github repository[END_REF], the main share s (ℓ,j) is computed as the sum of the shares s i for which j equals the ℓ-th bit of i plus 1. Similarly, the main shares c (ℓ,j) and a (ℓ,j) . In Phase 3, the prover executes the protocol Π for every set of main shares using ε1, . . . , εm ∈ Fq as the random elements for all D executions. This particular execution of the protocol Π on the set of main shares S ℓ is shown in Figure 4. The output of each execution the shares α k (ℓ,j) , v k (ℓ,j) (k,j)∈[m]× [START_REF]Biscuit github repository[END_REF] of the opened values α k and v k , and its corresponding hash

H ℓ = H α k (ℓ,j) , v k (ℓ,j) (k,j)∈[m]×[2]
12 . In Phase 5, the prover sends (seed (i) , ρi) i̸ =i , com (i) , ∆s, ∆c, α i sends to the verifier, where α i = ( α1 i , . . . , αm i ),

α k i = x k i • ε k + a k i and x k i = A k,0 ( s i ).
We highlight that the prover does not send explicitly instead of sending N -1 strings of the form (seed (i) , ρi) but it sends instead the log 2 (N ) nodes of the tree TreePRG(root) so that the verifier can recompute the values (seed (i) , ρi) i̸ =i . Finally, in the verification phase, the verifier recomputes (seed (i) , ρi) i̸ =i , and uses them to recompute the sets main shares partially. We say partially recompute and not just recompute because for each set S ℓ one of the main shares triples (either the one corresponding to j = 1 or j = 2) is missing the addition of the shares corresponding to the i-th party. After, the verifier, for every set of main parties, follows the algorithm in Figure 5 to check the execution of the MPC protocol Π. Finally, the verifier recomputes h0 and h2 and outputs accept if these two values match the ones the prover sent. Otherwise, the verifier rejects.

Security proofs of the zero-knowledge protocol. The following theorem establishes the security properties of the proof of knowledge protocol described in Figure 3.

Theorem 1. The PowAff2 affine zero-knowledge protocol described in Figure 3 has the following properties:

-Completeness: A Prover with the knowledge of a solution to an instance (f , t) of the PowAff2 is always accepted by the Verifier.

-Soundness: Let ϵ = 1 N + 1 q u • 1 -1 N
, where p = 1/q u . Suppose there exists a prover P who convinces the verifier to accept with probability ε > ϵ. Then there is an efficient probabilistic extraction algorithm E, which has rewindable black-box access to P, that, in expectation, with at most

4 ε -ϵ • 1 + ε • 2 ln(2) ε -ϵ .
calls to P outputs either a solution to an instance (f , t) of the PowAff2u-1 problem or a collision to the commitment scheme Com or the hash H. -Honest-verifier zero-knowledge: If the pseudo-random generator PRG and the commitment scheme com are indistinguishable from the uniform random distribution, then the algorithm in Figure 3 honestverifier zero-knowledge.

Proof. (sketch) Here follow the same reasoning as the one in [10, Theorem 1]. We highlight the main parts of the proof. The details follow along the lines with [10, Theorem 1]

-Completeness: By following, step by step, the protocol in Figure 3 it is not hard to see that a Prover that follows the protocol with inputs (f , t, s) such that t = f (s) will always be accepted. -Soundness: The structure of the proof will be the following:

1. We proof that a prover P who has not a solution for the PowAff2u-1 problem can cheat with probability at most ϵ =

1 N + 1 q u • 1 -1 N . 2.
Assuming that (a) No collisions to Com nor H can be found. (b) There exists a cheater P who has cheating probability ε > ϵ.

We show how to extract a solution to the PowAff2u-1 problem whenever rewindable black-box access to P is given. For part 1, suppose that at step 7 the vector s = s 1 + • • • + s N is not a solution of the PowAff2u-1 problem defined by (f , t). With such a vector s the prover can be accepted by the verifier in only two situations:

• The prover honestly follows the protocol, and for each k

∈ [m], the value v k = y k α k -z k ε k -c k ,
which is the value that would be obtained from a genuine executing of the MPC protocol with challenges ε k (see Figure 2), equals zero, or • The prover dishonestly deviates from the protocol, yet the verifier believes that all the honest v k are zero, but in reality, at least one of them is not. In the first situation, we would have a false positive case of the MPC protocol in Figure 2. By Proposition 1, this happens with probability at most 1/q u . In the second situation, the prover cheats during the simulation of at least one party. Since the verifier checks the correct execution of all the parties but one, the prover has to cheat on exactly one party. Otherwise, the verifier rejects. Cheating in one party i ′ means that the prover uses a set of different shares than an honest party, holding the same input seed seed (i ′ ) , would use. Since every party aggregates to exactly one of the main shares for all of the D bi-party protocols. For each one of these bi-party protocols, there is one share that has been dishonestly computed, i.e., not following the MPC protocol. Thus, the prover won't be detected with PoK(Prover(f , t, s), Verifier(f , t)) Phase 1: Prover commits to the inputs of the MPC protocol in Figure 4 1 : root

$ ← {0, 1} λ , seed (i) , ρ (i) i∈[N ] ← TreePRG(root) for i ∈ [N ] do 2 :
s i , c i , a i , ← PRG(seed (i) )

3 : com (i) ← Com seed (i) , ρi 4 : h0 ← H(com (1) , . . . , com (N ) ), and send h0 to Verifier

5 : a ← i∈[N ] a i , c ← A k,2 (s) • a k k∈[m] 6 : ∆s ← s - i∈[N ] s i , ∆c ← c - i∈[N ] c i 7 : s 1 ← s 1 +
for ℓ ∈ [D] do 10 : s (ℓ,i ℓ +1) ← s (ℓ,i ℓ +1) + s i , c (ℓ,i ℓ +1) ← c (ℓ,i ℓ +1) + c i and 11 : a (ℓ,i ℓ +1) ← a (ℓ,i ℓ +1) + a i
α i ← ( α1 i , . . . , αm i ), where α k i = x k i • ε k + a k i and x k i = A k,0 ( s i ) 17 : rsp ← (seed (i) , ρi) i̸ =i , com (i)
, ∆s, ∆c, α i and send rsp to Verifier Verification:

18 : Verifier partially recomputes s p , c p , a p p∈[D]× [START_REF]Biscuit github repository[END_REF] from (seed (i) , ρi) i̸ =i by following Phase 1 but skipping the steps involving a i-th share or the seed seed (i)

for ℓ ∈ [D] do 19 :
Verifier gets H ℓ and α k (ℓ,j) , v k (ℓ,j) (k,j)∈[m]× [START_REF]Biscuit github repository[END_REF] from the algorithm in Figure 5 20 : Verifier accepts if and only if h0 = H(com (1) , . . . , com (N ) ) and h1 = H H1, . . . , HD , where

com (i) = Com(seed (i) , ρi) for each i ̸ = i.
Fig. 3: Proof of Knowledge protocol for PowAff2.

probability 1 N . Consequently, a prover without a correct solution of the PowAff2u-1 problem will be accepted with probability at most ϵ = 1 N + 1 q u • 1 -1 N . Now, for the second part, we assume that no collisions to Com nor H can be found and there exists a cheater P who has cheating probability ε > ϵ. First, we prove that a solution s of the PowAff2u-1

Inputs : A set of main shares s (ℓ,j) , c (ℓ,j) , a (ℓ,j) j∈ [START_REF]Biscuit github repository[END_REF] and the challenges ε1, . . . , εm

Outputs : H ℓ and α k (ℓ,j) , v k (ℓ,j) (k,j)∈[m]×[2] for k ∈ [m] do for j ∈ [2] do 1 : x k (ℓ,j) ← A k,1 ( s (ℓ,j) ) 2 : α k (ℓ,j) ← x k (ℓ,j) • ε k + a k (ℓ,j) 3 : α k ← α k (ℓ,1) + α k (ℓ,2) / / The parties open α k (ℓ,j) to obtain α k . 4 : z k (ℓ,1) ← t k -A k,0 ( s (ℓ,1) ) 5 : y k (ℓ,1) ← A k,2 ( s (ℓ,1) ) 6 : v k (ℓ,1) ← y k (ℓ,1) • α k -z k (ℓ,1) • ε k -c k (ℓ,1) 7 : v k (ℓ,2) ← -v k (ℓ,1) 8 : H ℓ ← H α k (ℓ,j) , v k (ℓ,j) (k,j)∈[m]×[2]
Fig. 4: Simulation of the MPC protocol Π for the ℓ-th set of main shares.

Inputs: Partially computed main shares s (ℓ,j) , c (ℓ,j) , a (ℓ,j) j∈ [START_REF]Biscuit github repository[END_REF] ,

the first challenges ε1, . . . , εm, the second challenge i, and the α i

Outputs :

H ℓ and α k (ℓ,j) , v k (ℓ,j) (k,j)∈[m]×[2]
1 : (i1, . . . , iD) ← i / / Binary representation of i.

2 : α1 i , . . . , αm i ← α i for k ∈ [m] do for j ∈ [2] do 3 : x k (ℓ,j) ← A k,1 ( s (ℓ,j) ) 4 : α k (ℓ,j) ← x k (ℓ,j) • ε k + a k (ℓ,j) 5 : α k (ℓ,i ℓ +1) ← α k (ℓ,i ℓ +1) + α k i / / Adding missing share of α k (ℓ,i ℓ +1) . 6 : α k ← α k (ℓ,1) + α k (ℓ,2) / / The parties open α k (ℓ,j) to obtain α k . 7 : Set i * = 2 if i ℓ = 0, otherwise set i * = 1. 8 : y k (ℓ,i * ) ← A k,2 ( s (ℓ,i * ) ) 9 : z k (ℓ,i * ) ← t k -A k,0 ( s (ℓ,i * ) ) 10 : v k (ℓ,i * ) ← y k (ℓ,i * ) • α k -z k (ℓ,i * ) • ε k -c k (ℓ,i * ) 11 : v k (ℓ,i ℓ +1) ← -v k (ℓ,i * ) 12 : H ℓ ← H α k (ℓ,j) , v k (ℓ,j) (k,j)∈[m]×[2]
Fig. 5: Check the simulation of the MPC protocol Π in the ℓ-th set of main shares.

problem can be extracted from two valid transcripts of the form T1 and T2 produced by P that have the same initial commitment h0 and different second challenges ī1 (for T1) and ī1. Finally, we prove that such transcripts T1 and T2 can be extracted from P (assuming rewindable black-box access to P ) with an expected number of calls upper bounded by

4 ε -ϵ • 1 + ε • 2 ln(2) ε -ϵ .
Details of how this second part is proven follow in a similar as shown in [10, Theorem 1]. -Honest-verifier zero-knowledge: Now we sketch the proof of the honest-verifier zero-knowledge property of the protocol in Figure 3. The goal here is to show that the distribution of the transcripts output by the simulator described in Figure 6 on input (f , t) are indistinguishable from those coming from a genuine interaction between a prover and an honest verifier, where the prover input is (f , t, s) and t = f (s).

Simulator(f , t)

1 : Sample first challenge: ε = (ε1, . . . , εm) $ ← F m q 2 : Sample second challenge: i $ ← [N ] 3 : root $ ← {0, 1} λ 4 : seed (i) , ρ (i) i∈[N ] ← TreePRG(root) for i ∈ [N ] do 5 : s i , c i , a i , ← PRG(seed (i) )
6 : com (i) ← Com seed (i) , ρi 7 : h0 ← H(com (1) , . . . , com (N ) )

8 : ∆s 12 :

$ ← F n q , ∆c $ ← F m
α k i $ ← Fq and v k i $ ← Fq for each k ∈ [m] 13 : com (i) $ ← {0, 1} λ 14 : For each (k, ℓ, j) ∈ [m] × [D] × [2] compute α k (ℓ,j) and v k (ℓ,j) 15 : Set H ℓ ← H α k (ℓ,j) , v k (ℓ,j) (k,j)∈[m]×[2] for each ℓ ∈ [D]
16 : h1 ← H H1, . . . , HD 17 : rsp ← (seed (i) , ρi) i̸ =i , com (i) , ∆s, ∆c, α i , where α i = ( α1 i , . . . , αm i )

Output (h0, ε, h1, i, rsp)

Fig. 6: Honest-verifier zero-knowledge simulator.

The idea is to create a sequence of simulators that ends with the simulator described in Figure 6. The first simulator of the sequence consists of a legitimate prover, which holds a solution s and simulates the verifier by randomly sampling the challenges, as an honest verifier would do. These transcripts are indistinguishable from those coming from a legitimate execution of the protocol in proof of knowledge protocol.

Finally, the proof is completed by showing that the transcripts output by any simulator in the sequence are indistinguishable from those in the previous simulator. This implies that the transcripts of the simulator in Figure 6 are indistinguishable from those in for deduced by the actual protocol. Details of this part follow similarly as shown in [10, Theorem 1]. ⊓ ⊔

4 Biscuit Signature Scheme

In this part, we describe the Biscuit signature scheme. It is obtained by applying the Fiat-Shamir transformation [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF] to the zero-knowledge protocol given in Figure 3. The corresponding key-generation, signing, and verification algorithms are described in figures 7, 8 and 9, respectively. The secret-key is a random vector s ∈ F n q and the public-key is a pair f = (f1, . . . , fm),

t = f (s) ∈ Fq[x1, . . . , xn] m × F m q such that for all k ∈ [m]: f k (x1, . . . , xn) = A k,0 (x1, . . . , xn) + A k,1 (x1, . . . , xn) • A k,2 (x1, . . . , xn), (4)
where A1,0, . . . , Am,2 ∈ Fq[x1, . . . , xn] are random affine forms as in [START_REF]Call for Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process[END_REF].

We use two seeds seed f , seeds ∈ {0, 1} λ that are extended by a pseudo-random generator (PRG) to obtain the public polynomials f ∈ Fq[x1, . . . , xn] m and the secret vector s ∈ Fq[x1, . . . , xn] m . Finally, the vector t ∈ F m q is computed as t = f (s).

Biscuit.KeyGen

1 : seed f $ ← {0, 1} λ , seed sk $ ← {0, 1} λ 2 : f ← PRG(seed f ), s ← PRG(seed sk ) 3 : t ← f (s) 4 : sk ← seed sk , pk ← (seed f , t) 5 : Output sk, pk
Fig. 7: Key-generation algorithm for Biscuit.

Remark 2. The notation f ← PRG(seed f ) is a shortcut for extending the seed from a PRG and casting the bit string into a set of algebraic equations as in (4). Similarly, s ← PRG(seed sk ) stands for extending the seed and interpreting the bit string as a vector in F n q .

The signing procedure Biscuit.Sign is given in Figure 8. It takes as input a key-pair (sk, pk) and the message msg ∈ {0, 1} * to sign. It is obtained by applying the Fiat-Shamir transform to the ZKPoK for PowAff2 described in Section 3.2. The verification process (Figure 9) is very similar to the signature process (Figure 8) as the verifier has to replay the MPC protocol for each of the τ participants except one. The algorithm takes as input a message msg ∈ {0, 1} * , a signature sig and a public-key pk. It returns a bit b ∈ {0, 1}.

Theorem 2 (EU-CMA). Let PRG be a (t, ϵPRG)-secure pseudo-random generator function, and that any adversary running in time t has advantage at most ϵPowAff2 against the underlying PowAff2u-1 problem. Suppose that H0, H1, H2 H4 behave as random oracles that output binary strings of size 2λ. Let A be an adversary, who has access to a signing oracle, making qi queries to Hi and qs queries to the signing oracle. Then, the probability that A outputs a forgery of for the Biscuit signature scheme is:

Pr[Forge] ≤ 3(q + τ N • qs) 2 2 • 2 2λ + qs(qs + 5q) 2 2λ + ϵPRG + ϵPowAff2 + Pr[X + Y = τ ],
where τ is the number of rounds of the signature, X = max [0,q 2 ] {Xi} with Xi ∼ B(τ, 1 q u ), and

Y = max i∈[0,q 4 ] {Yi} with Yi ∼ B(τ -X, 1 N ).
Sign(pk, sk, msg)

1 : seed f , t ← pk, seed sk ← sk 2 : f ← PRG(seed f ), s ← PRG(seed sk )
Step 1: Commit to the inputs of the MPC protocol in Figure 4 3 : salt

$ ← {0, 1} 2λ for e ∈ [τ ] 4 : seed (e) $ ← {0, 1} λ , seed (e,i) i∈[N ] ← TreePRG(salt, root (e) ) for i ∈ [N ] do 5 : s (e) i , c (e) i , a (e)
i ← PRG(seed (e,i) )

6 :

com (e,i) ← H0 salt, e, i, seed

0 ← H1(salt, e, com (e,1) , . . . , com (e,N ) )

8 : h1 ← H2 salt, msg, h (1) 0 , . . . , h (τ ) 0 9
: ℓ , which is defined instead as 18 :

a (e) ← i∈[N ] a (e) i , c (e) ← A k,2 (s) • a (e) k k∈[m] 10 : ∆s (e) ← s - i∈[N ] s (e) i , ∆c (e) ← c (e) - i∈[N ] c (e)
H

(e) ℓ = H3 salt, ℓ, α k (e) (ℓ,j) , v k (e) (ℓ,j) (k,j)∈[m]×[2]
19 : h2 ← H4 salt, msg, pk, h1, H Verify(pk, σ, msg)

1 : f , t ← ExpandPK(pk) / / Expanding the public key pk.

Step 1: Parse signature 2 : salt, h1, h2, (seed (e,i) ) i̸ =ie , com (e,ie) e∈[τ ] , ∆s (e) , ∆c (e) , α

for i ∈ [N ] \ {ie} do 4 : s (e) i , c (e) i , a (e)
i ← PRG(seed (e,i) )

5 :

com (e,i) ← H0 salt, e, i, seed (e,i)

6 : h (e) 0 ← H1(salt, e, com (e,1) , . . . , com (e,N ) ) Step 4: Verify signature

7 : h1 ← H2 salt, msg, h (1) 0 , . . . , h (τ )
19 : Output (h1 = h1) ∧ (h2 = h2)
Fig. 9: Biscuit verification algorithm.

Parameters

Table 2 provides the parameter sets Biscuit, along with the corresponding size of the keys and signatures. Each parameter set aims to provide a security level either I, III or V according to the NIST guidelines. A more detailed description of the claimed security level of each parameter set is given in Section 5. The size of the public-key is λ + log 2 (q) • m bits, the size of the secret-key is λ bits and the bit-size of the signature is:

Level Version

6λ salt,h 1 ,h 2 +τ      (n + 2m) log 2 q
∆s (e) ,∆c (e) , α

(e) ie + λ • D (seed (e,i) ) i̸ =ie + 2λ com (e,ie )      .

Security Analysis

This part is dedicated to the security analysis of Biscuit against key-recovery (Section 5.2) and forgery (Section 5.3) attacks. Before that, Section 5.1 discusses the motivations for using structured systems as PowAff and the connection with the Learning With Errors (LWE, [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]) problem. From now on, let f = (f1, . . . , fm), t = f (s) ∈ Fq[x1, . . . , xn] m × F m q be a Biscuit public-key and s ∈ F n q be the corresponding secret-key.

About the Hardness of PowAff2

A fundamental assumption in the design of Biscuit is that solving algebraic systems generated essentially from power of affine forms are not much easier to solve than a random system of quadratic equations. Whilst the complexity of solving structured equations can be difficult to assess in general, the hardness of solving random quadratic equations has been deeply investigated and only exponential algorithms are known, e.g. [START_REF] Bettale | Solving polynomial systems over finite fields: improved analysis of the hybrid approach[END_REF][START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF][START_REF] Bardet | On the Complexity of Solving Quadratic Boolean Systems[END_REF][START_REF] Bellini | An estimator for the hardness of the MQ problem[END_REF].

We emphasize PowAff2 algebraic equations already appeared previously in the literature. In particular, the authors of [START_REF] Albrecht | Algebraic algorithms for lwe[END_REF][START_REF] Arora | New algorithms for learning in presence of errors[END_REF] demonstrated that attacking the Learning With Errors (LWE) problem [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] reduces to solve a structured algebraic system similar to PowAff2. An instance of LWE is given by a pair (A = {ai,j}, c = sA + e) ∈ F n×m q × F m q where s ∈ F n q is a secret and e ∈ F m q is an error vector. LWE (search) asks to recover the secret s. Arora and Ge exhibits in [START_REF] Albrecht | Algebraic algorithms for lwe[END_REF][START_REF] Arora | New algorithms for learning in presence of errors[END_REF] a rather natural algebraic modeling of LWE. More precisely, Arora and Ge show that LWE secrets can be recovered by solving:

f1(x1, . . . , xn) = P (c1 - n k=1 a k,1 x k ) = 0, . . . , fm(x1, . . . , xn) = P (c1 - n k=1 a k,m x k ) = 0, (5)
where P depends on the error distribution. In particular, P (X) = X(X -1) ∈ Fq[X] for binary errors and [START_REF] Albrecht | Algebraic algorithms for lwe[END_REF] introduced the assumption that a system such as [START_REF] Aguilar Melchor | The return of the SDitH[END_REF] behaves such as a semi-regular sequence. As a consequence, a new fast algorithm for PowAff2 will lead to a new fast algebraic algorithm for binary LWE.

Let (f , t) a Biscuit public-key selected uniformly at random, and let S be a subset of the equations t = f (x) of size mu selected uniformly at random. Then, a random solution s ′ ∈ F n q of the equations in S follows a uniform distribution. Hence, f ℓ (s ′ ) is a uniform element in Fq. Therefore, the probability that s ′ is a solution of exactly j equations in S c is u j • (q -1) u-j /q u . Consequently, if p k denotes the probability that s ′ is not the solution of at most k equations in S c , then,

p k = u j=u-k+1 u j • (q -1) u-j q u .
In order to secure Biscuit against forgery attacks, we must have for every pair (k, u), where 0 ≤ k ≤ u ≤ m:

1. KZτ (q -k , N -1 ) > 2 λ , or 2. 1 p k • Cu(q, n, m) >

Implementation

Canonical Representation Optimization

As seen in Lemma 1, an equivalent system where, for the first n equations, one of the affine form is only composed of one variable. Without loss of generality, we can choose to have this variable in A k,0 . In other word, we can chose for the algorithm a system f1, . . . , fm as for n < k ⩽ m, where A k,j are affine forms. The effect is that the evaluation of the polynomial will be much faster as only 2 affine form evaluations have to be performed instead of 3 for most of the equations. In the implementation, we chose to simplify A k,0 to save some code, as A k,1 and A k,2 can be computed in the same way in a loop.

f k (x1, . . . , xn) = (x k + a k ) + A k,1 (x1, . . . , xn) • A k,2 (

Hypercube Optimization

The algorithms described in Figure 8 and Figure 9 use the hypercube variant. The simulation of the MPC protocol does not need to compute all the values as in Figure 4. We first compute α k using directly the opened values s and a. Then, need to compute α k (ℓ,j) only for j = 1. The value for j = 2 can be derived from α. Similarly, we can do the same for v k (ℓ,j) . This can also be applied to the verification. All in all, we usually require to keep only log 2 (N ) shares.

Vectorization

The main data structure in the algorithm is a vector of value in Fq. We have the secret value which is a vector of n elements in Fq the public key which is a vector of m elements in Fq intermediate values which are vectors of m elements in Fq.

For each of this vector, we need to compute operations component-wise. We can then pack all elements in the largest possible integer handled by the CPU. Typically this could be a 64-bit word that can contain 8 elements in F 2 8 for instance. When vectorized instructions are available (SSE, AVX, . . . ), even lagrer integer types can be used. For instance, with AVX2 a 256-bit integer can be used to pack vector of Fq elements. In characteristic 2, the component-wise addition of a vector of elements can be done in one instruction using the VPXOR instruction.

Performances and Memory Consumption

In this section, we show the performance and memory consumption of our instances. Our implementation is optimized to use avx2 vectorized instructions on a little-endian 64-bit CPU. The code is compiled with GCC version 12.2.0 on Debian GNU/Linux. Number of cycles was measured by counting PERF HW COUNT CPU CYCLES events on an 11th Gen Intel(R) Core(TM) i7-1185G7 @ 3.00GHz CPU. Even if frequency modification should not affect this metric, we deactivated Intel's TurboBoost feature anyway. The number of cycles is averaged over 100 executions. In Table 3, we give the figures for the implementation strictly following the description in the NIST submission but with the new parameters proposed in Table 2. In Table 4, we include the canonical representation optimization as described in Section 6.1. This improves the performances by 18 to 28 percent. Finally, in Table 5, in addition to the previous optimization, we integrated the hypercube variant. With this variant, the memory consumption is greatly improved especially for large values of N . This is because we have to keep track of only log 2 (N ) shares instead of N . The performances are improved by 50 to 83 percent for the small variant, and by 41 to 69 percent for the fast variant. The code is available in [START_REF]Biscuit github repository[END_REF]. Table 4: Time performance and memory consumption of Biscuit on avx2 impl. using canonical optimization.

Name

Security Against Side-Channel Attacks

In this section, we briefly discuss the possible side-channel vulnerabilities of our proposition, and how to address them. Timing Attacks. First of all, it is worth noticing that the signature procedure of Biscuit is independent of the secret value as long as the field arithmetic and the hash functions do not leak information on the manipulated data. Indeed, there is no branching that depends on the value of any secret in the algorithm. This allows to make an isochronous implementation by focusing on the field arithmetic.

Side-Channel Attacks. The most popular technique to prevent these attacks is to use masking: we compute a sharing of the secret using fresh random value at each execution.

In our scheme, it happens that most of the time, the secret value s is already shared into N shares due to the MPC protocol. Nevertheless, this does not guarantee security at order N -1 because all the shares (except one) will finally become public during the verification process. This sharing is not secure from a side-channel attacker point of view. However, as our construction uses fields of characteristic 2, classical Boolean masking techniques can be applied throughout the scheme.

Phase 2 :challenge 12 :← 3 : 13 : 4 14: 15 :

 212313415 First Verifier samples ε1, . . . , εm $ Fq and sends them to Prover Phase Prover's first response / / Prover executes MPC protocol for every set of main shares. for ℓ ∈ [D] do Prover gets H ℓ and α k (ℓ,j) , v k (ℓ,j) (k,j)∈[m]×[2] from the algorithm in Figure h1 ← H H1, . . . , HD and send h1 to Verifier Phase 4: Second challenge Verifier samples i $ ← [N ] and sends it to Prover Phase 5: Prover's second response 16 :

q 9 : s 1 ← s 1 +

 911 ∆s and c 1 ← c 1 + ∆c 10 : Initialize s p , c p and a p to zero objects for each p ∈ [D] × [2] for i ∈ [N ] \ { ī} do 11 : Simulate the i party to obtain α k i and v k i for each k ∈ [m]

1 +

 1 ∆s (e) and c (e) 1 ← c (e) 1 + ∆c (e) 12 : Initialize s (e) p , c (e) p and a (e) p to zero objects for each p ∈ [D] × [2] for i ∈ [N ] do 13 : (i1, . . . , iD) ← i / / Binary representation of i. for ℓ ∈ [D] do 14 : s (e) (ℓ,i ℓ +1) ← s (e) (ℓ,i ℓ +1) + s (e) i , c (e) (ℓ,i ℓ +1) ← c (e) (ℓ,i ℓ +1) + c (e) . . , ε (e) m ) e∈[τ ] $ ← PRG(h1) Step 3: First response for e ∈ [τ ] do for ℓ ∈ [D] do 17 :Follow the algorithm in Figure4to get H (e)

Fig. 8 :

 8 Fig. 8: Biscuit signing algorithm.

Step 2 :

 2 Recompute h1 and the inputs of the MPC protocol for e ∈ [τ ]

0 8 : 9 :Step 3 : 18 :

 89318 a (e) ← i∈[N ]\{ie} a (e) i , c (e) ← A k,2 (s) • a ∆s (e) ← s -i∈[N ]\{ie} s (e) i , ∆c (e) ← c (e) -i∈[N ]\{ie} c(e)i if ie ̸ = 1 then 10 : s (e) 1 ← s (e) 1 + ∆s (e) and c (e) 1 ← c (e) 1 + ∆c (e) 11 : Initialize s (e) p , c (e) p and a (e) p to zero objects for each p ∈ [D] × [2] for i ∈ [N ] \ {ie} do 12 : (i1, . . . , iD) ← i / / Binary representation of i. for ℓ ∈ [D] do 13 : s(e) (ℓ,i ℓ +1) ← s (e) (ℓ,i ℓ +1) + s (e) i , c (e) (ℓ,i ℓ +1) ← c (e) (ℓ,i ℓ +1) + c (e) i ℓ +1) ← a (e) (ℓ,i ℓ +1) + a (e) i Recompute h2 for e ∈ [τ ] do for ℓ ∈ [D] doie and the ℓ-th set of main shares as inputs in 16 : the algorithm in Figure5to get H h2 ← H4 salt, msg, pk, h1, H

  x1, . . . , xn), for k ⩽ n, and f k (x1, . . . , xn) = A k,0 (x1, . . . , xn) + A k,1 (x1, . . . , xn) • A k,2 (x1, . . . , xn),

  ∆s and c 1 ← c 1 + ∆c

8 : Initialize s p , c p and a p to zero objects for each p ∈ [D] × [2] for i ∈ [N ] do 9 :

(i1, . . . , iD) ← i / / Binary representation of i.

Table 2 :

 2 Parameters of Biscuit, bit security, public-key (pk), secret-key (sk) and signature (σ) sizes in bytes.

			λ	q	n	m	N	τ	Bit-Security sk pk	σ
	I	short fast	128 256 50	52	256 18 32 28	143 143	16 68	5748 7544
	III	short fast	192 256 89	92	256 25 32 40	207 210	24 116	12969 17784
	V	short fast	256 256 127 130	256 33 32 53	272 275	32 162	23523 32575

  2 λ+C λ , where C λ = 15 if λ = 128 or 192 and C λ = 16 otherwise. Following these analyses, we propose in Table 2 a set of 3 parameters for 128, 192 and 256 bits of classical security.

Table 3 :

 3 Time performance and memory consumption of Biscuit on avx2 impl.

	Name	keygen	Memory (bytes) sign	verify	keygen	Performance (cycles) sign verify
	biscuit128s	512	1 651 088	122 480	62 413	57 621 312	56 705 942
	biscuit128f	512	326 704	25 712	61 947	11 367 980	10 739 162
	biscuit192s	608	3 430 288	194 544	173 744	150 259 434	148 692 324
	biscuit192f	608	700 400	49 392	175 783	30 356 710	29 144 437
	biscuit256s	800	7 393 680	335 312	341 657	456 813 570	453 782 090
	biscuit256f	800	1 517 584	98 768	344 467	92 359 826	88 932 332

Table 5 :

 5 Time performance and memory consumption of Biscuit on avx2 impl. using canonical and hypercube optimization.

https://csrc.nist.gov/projects/pqc-dig-sig/round-1-additional-signatures

https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/sw8NueiNek0/m/2sa_emjABQAJ

https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/sw8NueiNek0/m/2sa_emjABQAJ

If only one party is opened then there are no pairs to check consistency. In this case, the prover does not commit to the views, but actually to the point-to-point channels between the parties.

As noted in[START_REF] Aragon | Mira: a digital signature scheme based on the minrank problem and the mpc-in-the-head paradigm[END_REF], the security of proof knowledge protocols using the hypercube technique with additive shares is the same with or without these intermediate hash values H ℓ , but it might help to reduce the memory demand of the protocol when the implementation of the hash H is not incremental.

Acknowledgements

The authors would like to thank Charles Bouillaguet and Julia Sauvage for discussions on the hardness of PowAff2 and choice of parameters. The third author would like to thank Google which partially supported this work thanks to a gift for supporting post-quantum research.

Key recovery attacks

A key-recovery attack against Biscuit consists of solving the PowAff2 problem, i.e. recovering s ∈ F m q from the system defined as : t = f (x), with x = (x1, . . . , xn).

Currently, the best attack against Biscuit is a dedicated hybrid approach for solving PowAff2 equations described by Charles Bouillaguet 13 . The hybrid approach is a classical technique for solving algebraic systems that combines exhaustive search and a Gröbner basis-like computations [START_REF] Bettale | Solving polynomial systems over finite fields: improved analysis of the hybrid approach[END_REF][START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF][START_REF] Bardet | On the Complexity of Solving Quadratic Boolean Systems[END_REF]. The efficiency of such approaches is related to the choice of a trade-off, denoted k ≤ n, between these two methods.

We sketch below the approach described on the NIST PQC mailing list. Let g = g1(x) = u1(x)

where An+1,0, An+1,1, An+1,2, . . . , Am,0, Am,1, Am,2 ∈ Fq[x1, . . . , xn] affine forms.

Then, for every guess (a1, . . . , a k ) ∈ F k q of the vector of variables (x1, . . . , x k ), we obtain k linear polynomials, namely g1(a1, . . . , a k , x k+1 , . . . , xn), . . . , g k (a1, . . . , a k , x k+1 , . . . , xn). These k linear polynomials are expected to be linearly independent with a probability close to 1 -1/q. Hence we can use them to substitute k additional variables in the remaining polynomials. The attack is finalized by solving the resulting quadratic system of mk equations in n -2k variables.

Complexity. The cost of the attack is dominated by min

where MQ(n, m, q) denotes the complexity of solving a random system of m quadratic equations over in n variables over Fq. To compute the exact complexity, we can rely on the MQEstimator software tool which is part of the more general CryptographicEstimators 14 library [START_REF] Esser | CryptographicEstimators: a software library for cryptographic hardness estimation[END_REF].

Forgery attacks

In the context of forgery, the attacker has to solve the PowAff2u problem (Definition 1) which is a variant of the problem considered before for key-recovery (Section 5.2). In the PowAff2u problem, the goal is to find a vector s ′ ∈ F n q that vanishes a subset of size mu of the system [START_REF] Alagic | Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process[END_REF]. Without loss of generality, we assume s ′ vanishes the first mu polynomials and not the remaining equations. That is,

By Proposition 1, a set of N parties that follows the MPC protocol in Figure 2 on inputs s ′ and (f , t) will output accept with probability p1 = 1/q u . In the context of MPCitH, the value p1 is referred in the literature as the false positive rate of the MPC protocol.

Thanks to the ', it is known that MPCitH-based signature scheme that consist of τ repetitions of a MPC protocol with false positive rate p1 can be forged by computing of average

, calls to some hash functions, where p2 is the probability of guessing some of the views of parties that remain unopened, e.g., p2 = 1/N for Biscuit.

Let Cu(q, n, m) denote the complexity of finding a preimage to a chosen subset S of the system t = f (x) of size mu and s ′ ∈ F n q be a solution than vanishes the equations of S. Then, s ′ might, by chance, be a solution of any equation in S c , i.e., any equation that is not in S. If there remain k ∈ [u] equations in S c for which s ′ is not a solution, then an attacker can mount a forgery attack with complexity KZτ (q -k , N -1 ). 13 https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/sw8NueiNek0/m/2sa_emjABQAJ 14 https://github.com/Crypto-TII/CryptographicEstimators