2026-05-12T03:55:19Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00240938 2025-03-06T05:57:42Z 6164:6165:6462:11854

MPC-in-the-Head署名の強存在的偽造不可能性 Strong Existential Unforgeability of MPC-in-the-Head Signatures Mukul, Kulkarni 草川, 恵太 Mukul, Kulkarni Keita, Xagawa 耐量子計算機署名, NIST PQC 追加標準化, MPC-in-the-Head 署名, 強存在的偽造不可能性 2022年，米国国立標準技術研究所 (NIST) は耐量子計算機電子署名の追加募集を開始した．要件として適応的選択文書攻撃下での存在的偽造不可能性（EUF-CMA安全性）が求められている．しかし実際の応用を考えると，より強い安全性である強存在的偽造不可能性が求められることもある．40件の候補の中で，強存在的偽造不可能性を証明しているものはかなり少ない．MPC-in-the-Head署名 (MPCitH署名) と呼ばれる構成が9件で採用されているが，これらの署名の強存在的偽造不可能性は証明されていない．本論文では，これら9件のMPCitH署名について適切な仮定の下で（量子）ランダムオラクルモデルでの強存在的偽造不可能性を示す．これらMPCitH署名はn≥2の(2n+1)-パス認証方式にFiat-Shamir変換を適用して署名を構成している．強存在的偽造不可能性を示すために，(2n+1)-パス認証方式に非分岐性 (non-divergency) を導入する．これはKiltz, Lyubashevsky, Schaffner (EUROCRYPT 2018) が定義した3-パス認証方式の計算量的単一返答性 (computational unique response) およびDon, Fehr, Majentz (CRYPTO 2020) が定義したその複数ラウンド版を緩和した概念である． 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. Unfortunately, on the so-called MPC-in-the-Head (MPCitH) signature schemes, we have no knowledge of strong existential unforgeability. 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). 情報処理学会 2024-10-15 jpn conference paper https://ipsj.ixsq.nii.ac.jp/records/240938 コンピュータセキュリティシンポジウム2024論文集 1441 1448 https://ipsj.ixsq.nii.ac.jp/record/240938/files/IPSJ-CSS2024192.pdf application/pdf 385.1 kB 2026-10-15