Biscuit: new MPCitH signature scheme from structured multivariate polynomials
type: Item
instance of: scholarly article
title: Biscuit: new MPCitH signature scheme from structured multivariate polynomials
DOI: 10.1007/978-3-031-54770-6_18
author: Luk Bettale
author: Delaram Kahrobaei
author: Ludovic Perret
author: Javier A. Verbel
publication date: 2024-05-31T00:00:00Z
review text: 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 …
reviewed by: Jaak Henno
Mathematics Subject Classification ID: 94A62
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 81P94
zbMATH DE Number: 7857898
zbMATH Keywords: cryptography
zbMATH Keywords: cryptanalysis
zbMATH Keywords: post-quantum
zbMATH Keywords: digital signature
zbMATH Keywords: multivariate polynomials
MaRDI profile type: Publication
cites work: The return of the SDitH
cites work: New Algorithms for Learning in Presence of Errors
cites work: On the complexity of solving quadratic Boolean systems
cites work: Concretely-Efficient Zero-Knowledge Arguments for Arithmetic Circuits and Their Application to Lattice-Based Cryptography
cites work: Q4035736
cites work: An estimator for the hardness of the MQ problem
cites work: Hybrid approach for solving multivariate systems over finite fields
cites work: Solving polynomial systems over finite fields
cites work: How To Prove Yourself: Practical Solutions to Identification and Signature Problems
cites work: Q3549593
cites work: An Attack on Some Signature Schemes Constructed from Five-Pass Identification Schemes
cites work: On lattices, learning with errors, random linear codes, and cryptography
description: scientific article; zbMATH DE number 7857898