Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IACR Communications in Cryptology

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

Haruhisa Kosuge, Keita Xagawa

Published Oct 26, 2026• 0 citations
Publisher

Abstract

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).

DOI
10.62056/akmpxruc2

Related papers

MiRitH: Efficient Post-Quantum Signatures from MinRank in the Head

Gora Adj, Stefano Barbero, Emanuele Bellini +5 more

Since 2016’s NIST call for standardization of post-quantum cryptographic primitives, developing efficient post-quantum secure digital signature schemes has become a highly active area of research. The difficulty in constructing such schemes is evidenced by NIST reopening the call in 2022 for digital signature schemes, because of missing diversity in existing proposals. In this work, we introduce the new postquantum digital signature scheme MiRitH. As direct successor of a scheme recently developed by Adj, Rivera-Zamarripa and Verbel (Africacrypt ’23), it is based on the hardness of the MinRank problem and follows the MPC-in-the-Head paradigm. We revisit the initial proposal, incorporate design-level improvements and provide more efficient parameter sets. We also provide the missing justification for the quantum security of all parameter sets following NIST metrics. In this context we design a novel Grover-amplified quantum search algorithm for solving the MinRank problem that outperforms a naive quantum brute-force search for the solution.MiRitH obtains signatures of size 5.7 kB for NIST category I security and therefore competes for the smallest signatures among any post-quantum signature following the MPCitH paradigm.At the same time MiRitH offers competitive signing and verification timings compared to the state of the art. To substantiate those claims we provide extensive implementations. This includes a reference implementation as well as optimized constant-time implementations for Intel processors (AVX2), and for the ARM (NEON) architecture. The speedup of our optimized AVX2 implementation relies mostly on a redesign of the finite field arithmetic, improving over existing implementations as well as an improved memory management.

IACR Transactions on Cryptographic Hardware and Embedded Systems•Mar 12, 2024•6 citations

Speedup signing: pre-rejection sampling towards dilithium

Lianglin Yan, Ming Luo, Mingsheng Wang

Abstract Security and efficiency have always been two critical factors in the development of post-quantum digital signatures. As the best-known scheme, (Ducas et al., TCHES 2018) is SUF-CMA in QROM and has a relatively fast efficiency with many untrivial optimizations. The goal of this paper is to propose some techniques that can promote signing speed without sacrificing security. We first propose the pre-rejection sampling technique in stage to reduce the rejections of the fourth condition, consequently resulting in some speedup in stage. To prove security, we propose the c-selected MLWE problem, a variant of MLWE that can offer the equivalent security as original MLWE. Applying these two techniques to , we obtain an advanced signature scheme with better efficiency, and without any other losses except some pre-computations. Security reduction demonstrates that our scheme is also SUF-CMA in QROM. The experimental results show that pre-rejection sampling achieves a $$47\%$$ 47 % , $$22\%$$ 22 % , and $$17\%$$ 17 % reduction in the rejection probability of the fourth condition over scheme when the parameter set corresponds to NIST’s security levels 2, 3 and 5, respectively. This type of reduction increases signing speed by approximately $$1\%$$ 1 % under the parameter set 2 of .

Cybersecurity•Feb 8, 2025•0 citations

Alati kaks : Kahe osapoolega SDitH digiallkirjad

Veri, Hans Kristjan

The rise of quantum computing threatens to break many of the cryptographic systems that secure today’s digital world. In response, researchers are developing new tools designed to remain secure in a post-quantum future. Most of the promising candidates for post-quantum digital signatures rely on security assumptions based on lattices or properties of hash functions. Another promising approach transforms secure multi-party computation protocols into zero-knowledge proofs, which are then turned into digital signatures. This technique, known as multi-party computation in-the-head (MPCitH), offers strong security properties and flexibility for distributed applications. This thesis investigates whether MPCitH digital signatures can be efficiently adapted for use by two cooperating parties to jointly produce a signature. Here we show how to construct two-party signatures based on syndrome decoding in-the-head (SDitH) signatures. We propose a provably secure scheme that achieves the smallest known communication overhead among two-party MPCitH signatures, while resulting in a signature size approximately double that of a single-prover variant. This result provides a new data point in the design space of multi-party MPCitH signatures and post-quantum digital signatures in general.

•Jan 1, 2025•0 citations

Quantum resilient security proofs

Hélder Vieira de Freitas Maia Martins

Recent developments in quantum computers pose an imminent threat to cryptography since many widely used cryptographic schemes will no longer be secure. This worrisome scenario motivated a growing interest in the field of post-quantum cryptography, which aims to design cryptosystems that are postquantum secure, i.e. secure against quantum-capable adversaries. While finding post-quantum computational hardness assumptions is pivotal to achieve this goal, an issue that is often overlooked is provable security. In fact, to prove that the post-quantum computational hardness necessarily implies post-quantum security of the derived cryptosystem, the reduction argument that establishes this implication also needs to be post-quantum. As such, many new methods have been devised in the last few years to handle this adaptation to the quantum setting. In particular, the quantum analogue of the Random Oracle Model has garnered special interest, as it is the foundation of many cryptographic schemes, from public-key encryption to digital signatures. It is also very problematic and usually the main culprit of the failure of security proofs when transitioning to the quantum setting. This work offers a comprehensive exposition on the most influential techniques developed in the last decade to enable or facilitate the construction of security proofs in the Quantum Random Oracle Model (QROM). Each presented technique offers an unique purpose and a solution to a problem provoked by the QROM, and, as such, as a whole, this works allows for an understanding of the most common strategies to construct these type of security proofs. This is accomplished by presenting and analyzing the security proof of three cryptographic schemes set in this model, which underlines the central role these techniques take in provable quantum security.

•Dec 21, 2024•0 citations

An Efficient MQ-based Signature with Tight Security Proof

Hiroki Furue, Dung Hoang Duong, Tsuyoshi Takagi

At PKC 2018, Chen et al. proposed SOFIA, the first MQ-based digital signature scheme having tight security in the quantum random oracle model (QROM). SOFIA is constructed by applying an extended version of the Unruh transform (EUROCRYPT 2015) to the mathcal MQ-based 5-pass identification scheme (IDS) proposed by Sakumoto et al. (CRYPTO 2011). In this paper, we propose an MQ-based 3-pass IDS with impersonation probability of 1/2 and apply the original version of the Unruh transform to it to obtain a more efficient MQ-based digital signature scheme tightly secure in the QROM. The signature size of our digital signature scheme decreases by about 35% compared with SOFIA in the level I of NIST PQC security category, and is supposed to be the shortest among that of MQ-based signatures tightly secure in the QROM.

International Journal of Networking and Computing•Jan 1, 2020•3 citations

Quantum-Access Security of the Winternitz One-Time Signature Scheme

Christian Majenz, Chanelle Matadah Manfouo, Māris Ozols

Quantum-access security, where an attacker is granted superposition access to secret-keyed functionalities, is a fundamental security model and its study has inspired results in post-quantum security. We revisit, and fill a gap in, the quantum-access security analysis of the Lamport one-time signature scheme (OTS) in the quantum random oracle model (QROM) by Alagic et al.~(Eurocrypt 2020). We then go on to generalize the technique to the Winternitz OTS. Along the way, we develop a tool for the analysis of hash chains in the QROM based on the superposition oracle technique by Zhandry (Crypto 2019) which might be of independent interest.

arXiv:2103.12448•Leibniz international proceedings in informatics•Jan 1, 2021•2 citations
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).
Since 2016’s NIST call for standardization of post-quantum cryptographic primitives, developing efficient post-quantum secure digital signature schemes has become a highly active area of research. The difficulty in constructing such schemes is evidenced by NIST reopening the call in 2022 for digital signature schemes, because of missing diversity in existing proposals. In this work, we introduce the new postquantum digital signature scheme MiRitH. As direct successor of a scheme recently developed by Adj, Rivera-Zamarripa and Verbel (Africacrypt ’23), it is based on the hardness of the MinRank problem and follows the MPC-in-the-Head paradigm. We revisit the initial proposal, incorporate design-level improvements and provide more efficient parameter sets. We also provide the missing justification for the quantum security of all parameter sets following NIST metrics. In this context we design a novel Grover-amplified quantum search algorithm for solving the MinRank problem that outperforms a naive quantum brute-force search for the solution.MiRitH obtains signatures of size 5.7 kB for NIST category I security and therefore competes for the smallest signatures among any post-quantum signature following the MPCitH paradigm.At the same time MiRitH offers competitive signing and verification timings compared to the state of the art. To substantiate those claims we provide extensive implementations. This includes a reference implementation as well as optimized constant-time implementations for Intel processors (AVX2), and for the ARM (NEON) architecture. The speedup of our optimized AVX2 implementation relies mostly on a redesign of the finite field arithmetic, improving over existing implementations as well as an improved memory management.
Abstract Security and efficiency have always been two critical factors in the development of post-quantum digital signatures. As the best-known scheme, (Ducas et al., TCHES 2018) is SUF-CMA in QROM and has a relatively fast efficiency with many untrivial optimizations. The goal of this paper is to propose some techniques that can promote signing speed without sacrificing security. We first propose the pre-rejection sampling technique in stage to reduce the rejections of the fourth condition, consequently resulting in some speedup in stage. To prove security, we propose the c-selected MLWE problem, a variant of MLWE that can offer the equivalent security as original MLWE. Applying these two techniques to , we obtain an advanced signature scheme with better efficiency, and without any other losses except some pre-computations. Security reduction demonstrates that our scheme is also SUF-CMA in QROM. The experimental results show that pre-rejection sampling achieves a 47%47\%47% 47 % , 22%22\%22% 22 % , and 17%17\%17% 17 % reduction in the rejection probability of the fourth condition over scheme when the parameter set corresponds to NIST’s security levels 2, 3 and 5, respectively. This type of reduction increases signing speed by approximately 1%1\%1% 1 % under the parameter set 2 of .
The rise of quantum computing threatens to break many of the cryptographic systems that secure today’s digital world. In response, researchers are developing new tools designed to remain secure in a post-quantum future. Most of the promising candidates for post-quantum digital signatures rely on security assumptions based on lattices or properties of hash functions. Another promising approach transforms secure multi-party computation protocols into zero-knowledge proofs, which are then turned into digital signatures. This technique, known as multi-party computation in-the-head (MPCitH), offers strong security properties and flexibility for distributed applications. This thesis investigates whether MPCitH digital signatures can be efficiently adapted for use by two cooperating parties to jointly produce a signature. Here we show how to construct two-party signatures based on syndrome decoding in-the-head (SDitH) signatures. We propose a provably secure scheme that achieves the smallest known communication overhead among two-party MPCitH signatures, while resulting in a signature size approximately double that of a single-prover variant. This result provides a new data point in the design space of multi-party MPCitH signatures and post-quantum digital signatures in general.
Recent developments in quantum computers pose an imminent threat to cryptography since many widely used cryptographic schemes will no longer be secure. This worrisome scenario motivated a growing interest in the field of post-quantum cryptography, which aims to design cryptosystems that are postquantum secure, i.e. secure against quantum-capable adversaries. While finding post-quantum computational hardness assumptions is pivotal to achieve this goal, an issue that is often overlooked is provable security. In fact, to prove that the post-quantum computational hardness necessarily implies post-quantum security of the derived cryptosystem, the reduction argument that establishes this implication also needs to be post-quantum. As such, many new methods have been devised in the last few years to handle this adaptation to the quantum setting. In particular, the quantum analogue of the Random Oracle Model has garnered special interest, as it is the foundation of many cryptographic schemes, from public-key encryption to digital signatures. It is also very problematic and usually the main culprit of the failure of security proofs when transitioning to the quantum setting. This work offers a comprehensive exposition on the most influential techniques developed in the last decade to enable or facilitate the construction of security proofs in the Quantum Random Oracle Model (QROM). Each presented technique offers an unique purpose and a solution to a problem provoked by the QROM, and, as such, as a whole, this works allows for an understanding of the most common strategies to construct these type of security proofs. This is accomplished by presenting and analyzing the security proof of three cryptographic schemes set in this model, which underlines the central role these techniques take in provable quantum security.
At PKC 2018, Chen et al. proposed SOFIA, the first MQ-based digital signature scheme having tight security in the quantum random oracle model (QROM). SOFIA is constructed by applying an extended version of the Unruh transform (EUROCRYPT 2015) to the mathcal MQ-based 5-pass identification scheme (IDS) proposed by Sakumoto et al. (CRYPTO 2011). In this paper, we propose an MQ-based 3-pass IDS with impersonation probability of 1/2 and apply the original version of the Unruh transform to it to obtain a more efficient MQ-based digital signature scheme tightly secure in the QROM. The signature size of our digital signature scheme decreases by about 35% compared with SOFIA in the level I of NIST PQC security category, and is supposed to be the shortest among that of MQ-based signatures tightly secure in the QROM.
Quantum-access security, where an attacker is granted superposition access to secret-keyed functionalities, is a fundamental security model and its study has inspired results in post-quantum security. We revisit, and fill a gap in, the quantum-access security analysis of the Lamport one-time signature scheme (OTS) in the quantum random oracle model (QROM) by Alagic et al.~(Eurocrypt 2020). We then go on to generalize the technique to the Winternitz OTS. Along the way, we develop a tool for the analysis of hash chains in the QROM based on the superposition oracle technique by Zhandry (Crypto 2019) which might be of independent interest.