International Association for Cryptologic Research

International Association
for Cryptologic Research

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

Paper

Artifact

Artifact number
asiacrypt/2024/a11

Artifact published
February 7, 2025

Badge
IACR Artifacts Available

README

ZIP (1.5 MB)  

License

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.