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

The MPC-in-the-Head paradigm is a promising approach for constructing post-quantum signatures, and its variants VOLE-in-the-Head (VOLEitH) and TC-in-the-Head (TCitH) are adopted in some NIST PQC candidates. Recent works by Aguilar-Melchor et al. (ASIACRYPT 2023), Hülsing et al. (CRYPTO 2024), and Baum et al. (CRYPTO 2025) establish EUF-CMA security for MPCitH/VOLEitH in the quantum random oracle model (QROM), but these proofs either ignore crucial optimizations such as rejection sampling and grinding or rely on round-by-round soundness and key-generation lossiness. Due to these restrictions, they do not directly apply to TCitH signatures such as Mirath, RYDE, or MQOM.

This paper addresses this gap by analyzing the QROM security of TCitH signatures that incorporate the crucial optimizations. Our treatment of rejection sampling and grinding applies more generally to MPCitH signatures, while our complete security proofs are instantiated for the TCitH signatures Mirath and RYDE. Our contributions are twofold: 1) We provide a new (strong) EUF-CMA security proof that accommodates rejection sampling and grinding. 2) We identify a gap in the EUF-CMA proof of MQOM and show that this issue extends to some schemes, including SBC (Huth and Joux, CRYPTO 2024) and rBN++ (Kim, Lee, and Son, EUROCRYPT 2025).