ASIACRYPT 2024
Faster Signatures from MPC-in-the-Head
Dung Bui
IRIF, Université Paris Cité
Eliana Carozza
IRIF, Université Paris Cité
Geoffroy Couteau
CNRS, IRIF, Université Paris Cité
Dahmun Goudarzi
Quarkslab
Antoine Joux
CISPA
Keywords:
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 of 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.
Publication
ASIACRYPT 2024
PaperArtifact
Artifact number
asiacrypt/2024/a11
Artifact published
February 7, 2025
Badge
IACR Artifacts Available
Some files in this archive are licensed under a different license. See the contents of this archive for more information.
Note that license information is supplied by the authors and has not been confirmed by the IACR.
BibTeX How to cite
Bui, D., Carozza, E., Couteau, G., Goudarzi, D., & Joux, A. (2024). Faster Signatures from MPC-in-the-Head. In: Chung, KM., Sasaki, Y. (eds) Advances in Cryptology — ASIACRYPT 2024. pp. 396—428. Lecture Notes in Computer Science, Vol. 15484. Springer, Singapore. https://doi.org/10.1007/978-981-96-0875-1_13. Artifact at https://artifacts.iacr.org/asiacrypt/2024/a11.