Shorter MPC-based Signature from PoSSo
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.
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.
Biscuit is resistant against quantum computers and achieves the following performance: