Paper 2025/1999

New Security Proofs of MPC-in-the-Head Signatures in the Quantum Random Oracle Model

Abstract

The MPC-in-the-Head paradigm is a promising approach for constructing post-quantum signature schemes. Its significance is underscored by NIST's selection of six signatures based on this paradigm and its variants, TC-in-the-Head and VOLE-in-the-Head, among the fourteen round-2 candidates in its additional post-quantum cryptography standardization process. Recent works by Aguilar-Melchor et al. (ASIACRYPT 2023), Hülsing et al. (CRYPTO 2024), and Baum et al. (CRYPTO 2025) have established EUF-CMA security for these signatures in the Quantum Random Oracle Model (QROM). However, their proofs do not account for crucial optimization techniques such as rejection sampling and grinding, rendering them inapplicable to practical schemes like the NIST round-2 candidates Mirath and RYDE. This paper addresses this gap by analyzing the QROM security of MPC-in-the-Head signatures that incorporate these optimizations, with a focus on Mirath and RYDE. We make two main contributions: 1) We provide a new (strong) EUF-CMA security proof that accommodates rejection sampling and grinding. We also present a new EUF-NMA security proof compatible with these optimizations, by extending the techniques of Don et al. (CRYPTO 2022) and Aguilar-Melchor et al. (ASIACRYPT 2023). 2) We also point out a gap in the EUF-CMA security proof of the MPC-in-the-Head signature schemes using correlated-tree techniques, MQOM, SBC (Huth and Joux, CRYPTO 2024), and rBN++ (Kim, Lee, and Son, EUROCRYPT 2025).