Biscuit: new MPCitH signature scheme from structured multivariate polynomials (Q6547993)

In response to the advances of quantum computing the U.S. Department of Commerce's National Institute of Standards and Technology (NIST) published in August 2024 results of its eight-year Post-Quantum Cryptography Standardization Process -- the set of encryption algorithms designed to withstand cyberattacks from quantum computers. All the finalized digital signature schemes (except one) were based on the computational hardness of problems involving structured lattices, thus in October 2022, NIST called for additional digital general-purpose signature schemes that are not based on structured lattices. This paper describes a new (second) version of a multivariate-based digital signature scheme Biscuit submitted to NIST in the first round of the call; the scheme is presented by a pseudocode in 8 figures, for executable implementation look up the Biscuit website. The scheme is an improvement of the scheme Picnic which was selected as an alternate candidate in the first NIST post-quantum cryptography standardization process. To sign a document \(p\) it is encrypted with a block cipher using a private key \(sk\). The scheme for the creation of \(sk\) is based on a well-known NP-complete Multivariate Quadratic problem of solving a system of quadratic equations over a finite field. Let \(f = ({f_1},\dots,{f_m}) \in \mathbb{F}_q{[{x_1},\dots,{x_n}]^m}\) be \(m\) quadratic affine equations over a finite field whose order \(q\) is a prime or a prime power, \(s \in \mathbb{F}_q^n\) is the private value used for the creation of \(sk\), and the pair \((f,t)\), where \(t = f(s)\) in made public. The security of the system is based on the difficulty of finding \(s\) from the knowledge of the pair \((f,t)\) -- solving the equation (finding \(s\)) would allow everybody to sign documents. The whole cryptography (starting already from DEC) is a search for the balance between linear and nonlinear operations. For security are needed nonlinear operations (e.g. multiplication) which break the natural order of integers, thus creating security, but also making programs slower and blowing up the size of results. To reduce complexity the quadratic equations in Biscuit have the form \({f_i} = {A_{i0}} + {A_{i1}} \cdot {A_{i2}}\), where all \({A_{ij}} \in \mathbb{F}_q[{x_1},\dots,{x_n}]\) are affine polynomials, i.e. contain only one multiplication. This substantially reduces the number of coefficients and speeds up computations. Proving security (lower bounds of computational work needed) is a `high art' and common agreements are achieved only after substantial research. The security/complexity of the `classical' quadratic equations is rather well studied (it is NP-hard), but this reduced form is not. The first version of Biscuit was submitted to NIST on 1.06.2023, but already on 18.07.2023, it appeared on the NIST list of comments posting, where Biscuit security was put under doubt. Biscuit authors did not agree, but other researchers supported the critics; the results of cryptanalysis were published in [\textit{Ch. Bouillaguet}, ``Preliminary cryptanalysis of the Biscuit signature scheme'', Cryptology ePrint Archive, Paper 2024/148 (2024), \url{https://ia.cr/2024/148}] and Biscuit did not appear in the NIST list (\url{https://doi.org/10.6028/NIST.IR.8528}, published on 24.11.2024) of 14 candidates for the round 2. In this paper is described the second version of Biscuit with modified `tuning parameters' \(q\), \(n\), \(m\), e.g. instead of \(q = 16\) (used in the first proposal to NIST) now \(q = 256\). Nobody knows whether this is the last one.\N\NFor the entire collection see [Zbl 1539.94002].