Biscuit

About Biscuit

Biscuit is a new multivariate-based Digital Signature Scheme (DSS) based on the hardness of solving a set of generic structured algebraic equations. It has been submitted to NIST Post-quantum Cryptography Project on June 1, 2023. 

It has been designed by:

• Luk Bettale, IDEMIA, France

• Delaram Kahrobaei, Queens College, City University of New York, USA

• Ludovic Perret, Sorbonne University, France

• Javier Verbel, Technology Innovation Institute, UAE

Biscuit is in the lineage of the MQDSS and Picnic signature schemes submitted to the previous NIST post-quantum cryptography (PQC) standardization process. The high-level framework of Biscuit is similar to MQDSS and Picnic. It is derived from a Zero-Knowledge Proof-of-Knowledge (ZKPoK) using the Fiat-Shamir transform.

Algorithm Highlight

The central building block of MQDSS is a ZKPoK for the problem of solving a system of non-linear quadratic equations over a finite field Fq(MQq problem).

Biscuit differs from MQDSS as it relies on special structured polynomials. The crucial hardness assumption underlying the design of Biscuit is that structured equations considered in Biscuit, which are roughly power of random affine forms (PowAff2 problem), are generics and as difficult to solve as random instances of MQq for Gröbner bases algorithms.

From Picnic, we borrow the uses of Multi-Party Computation (MPC) techniques, in particular the so-called MPC-in-the-Head (MPCitH) approach, that was used to derive a ZKPoK for a block-cipher key-recovery problem.

Biscuit relies on a different hard problem, but borrows from Picnic the uses of MPCitH-based proof system to derive ZKPoK. In particular, Biscuit is based on MPCitH -based proof systems, BN and some optimizations from BN++, that allow generating a ZK proof for the pre-image of an arbitrary arithmetic circuit defined over F.

The signature size of a DSS derived from a MPCitH -based proof system is usually related to the number of multiplications required to evaluate the circuit. This motivates the use of systems of algebraic equations generated by the power of affine forms. Such systems can be evaluated using a much smaller number of multiplications than random algebraic equations while not being easier to solve for generic algorithms. 

Performance

Biscuit is resistant against quantum computers and achieves the following performance:

Resources

Here are some Biscuit resources:

• Biscuit specification version February 11, 2024 [pdf]

• Biscuit source code [github]

• Biscuit submission package [zip] (specification, source code)

• Related Publications: 

  • Biscuit: New MPCitH Signature Scheme from Structured Multivariate Polynomials, L.Bettale, D.Kahrobaei, L.Perret, J.Verbel [ACNS 2024].

  • Preliminary Cryptanalysis of the Biscuit Signature Scheme, C.Bouillaguet, J.Sauvage [eprint 2024]