Strong Existential Unforgeability and More of MPC-in-the-Head Signatures

Mukul Kulkarni; Keita Xagawa

Paper 2024/1069

Strong Existential Unforgeability and More of MPC-in-the-Head Signatures

Mukul Kulkarni, Technology Innovation Institute

Keita Xagawa

, Technology Innovation Institute

Abstract

NIST started the standardization of additional post-quantum signatures in 2022. Among 40 candidates, a few of them showed their stronger security than existential unforgeability, strong existential unforgeability and BUFF (beyond unforgeability features) securities. Recently, Aulbach, Düzlü, Meyer, Struck, and Weishäupl (PQCrypto 2024) examined the BUFF securities of 17 out of 40 candidates. Unfortunately, on the so-called MPC-in-the-Head (MPCitH) signature schemes, we have no knowledge of strong existential unforgeability and BUFF securities. This paper studies the strong securities of all nine MPCitH signature candidates: AIMer, Biscuit, FAEST, MIRA, MiRitH, MQOM, PERK, RYDE, and SDitH. We show that the MPCitH signature schemes are strongly existentially unforgeable under chosen message attacks in the (quantum) random oracle model. To do so, we introduce a new property of the underlying multi-pass identification, which we call _non-divergency_. This property can be considered as a weakened version of the computational unique response for three-pass identification defined by Kiltz, Lyubashevsky, and Schaffner (EUROCRYPT 2018) and its extension to multi-pass identification defined by Don, Fehr, and Majentz (CRYPTO 2020). In addition, we show that the SSH11 protocol proposed by Sakumoto, Shirai, and Hiwatari (CRYPTO 2011) is _not_ computational unique response, while Don et al. (CRYPTO 2020) claimed it. We also survey BUFF securities of the nine MPCitH candidates in the quantum random oracle model. In particular, we show that Biscuit and MiRitH do not have some of the BUFF security.

Note: 2024-07-10: Correct minor typos.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: signature sEUF-CMA security BUFF security MPC-in-the-Head signature QROM
Contact author(s): mukul kulkarni @ tii ae
keita xagawa @ tii ae
History: 2024-07-10: revised; 2024-07-01: received; See all versions
Short URL: https://ia.cr/2024/1069
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1069,
      author = {Mukul Kulkarni and Keita Xagawa},
      title = {Strong Existential Unforgeability and More of {MPC}-in-the-Head Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1069},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1069}
}