Faster Signatures from MPC-in-the-Head

Dung Bui; Eliana Carozza; Geoffroy Couteau; Dahmun Goudarzi; Antoine Joux

Paper 2024/252

Faster Signatures from MPC-in-the-Head

Dung Bui

, IRIF, Université Paris Cité, Paris, France

Eliana Carozza, IRIF, Université Paris Cité, Paris, France

Geoffroy Couteau

, CNRS, IRIF, Université Paris Cité, Paris, France

Dahmun Goudarzi, Quarkslab

Antoine Joux

, CISPA Helmholtz Center for Information Security, Saarbrücken, Germany

Abstract

We revisit the construction of signature schemes using the MPC-in-the-head paradigm. We obtain two main contributions: – We observe that previous signatures in the MPC-in-the-head paradigm must rely on a salted version of the GGM puncturable pseudorandom function (PPRF) to avoid collision attacks. We design a new efficient PPRF construction that is provably secure in the multi-instance setting. The security analysis of our PPRF, in the ideal cipher model, is quite involved and forms a core technical contribution to our work. While previous constructions had to rely on a hash function, our construction uses only a fixed-key block cipher and is considerably more efficient as a result: we observe a 12× to 55× speed improvement for a recent signature scheme (Joux and Huth, Crypto’24). Our improved PPRF can be used to speed up many MPC-in-the-head signatures. – We introduce a new signature scheme from the regular syndrome decoding assumption, based on a new protocol for the MPC-in-the-head paradigm, which significantly reduces communication compared to previous works. Our scheme is conceptually simple, though its security analysis requires a delicate and nontrivial combinatorial analysis.

Note: Better tables of performance

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A minor revision of an IACR publication in ASIACRYPT 2024
Keywords: Code-based cryptography Design of Symmetric Primitives Post-Quantum Cryptography Signature Schemes
Contact author(s): bui @ irif fr
carozza @ irif fr
couteau @ irif fr
dahmun goudarzi @ gmail com
joux @ cispa de
History: 2024-11-29: last of 3 revisions; 2024-02-15: received; See all versions
Short URL: https://ia.cr/2024/252
License: CC BY

BibTeX

@misc{cryptoeprint:2024/252,
      author = {Dung Bui and Eliana Carozza and Geoffroy Couteau and Dahmun Goudarzi and Antoine Joux},
      title = {Faster Signatures from {MPC}-in-the-Head},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/252},
      year = {2024},
      url = {https://eprint.iacr.org/2024/252}
}