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

Lecture notes in computer science

SOFIA: $$\mathcal {MQ}$$-Based Signatures in the QROM

Ming-Shing Chen, Andreas Hülsing, Joost Rijneveld, Simona Samardjiska, Peter Schwabe

Published Jan 1, 2018• 14 citations
Publisher

Abstract

We propose SOFIA, the first $$\mathcal {MQ}$$ -based signature scheme provably secure in the quantum-accessible random oracle model (QROM). Our construction relies on an extended version of Unruh’s transform for 5-pass identification schemes that we describe and prove secure both in the ROM and QROM. Based on a detailed security analysis, we provide concrete parameters for SOFIA that achieve 128-bit post-quantum security. The result is SOFIA-4-128 with parameters carefully optimized to minimize signature size and maximize performance. SOFIA-4-128 comes with an implementation targeting recent Intel processors with the AVX2 vector-instruction set; the implementation is fully protected against timing attacks.

DOI
10.1007/978-3-319-76581-5_1

Related papers

An Efficient MQ-Based Signature in the QROM

Hiroki Furue, Dung Hoang Duong, Tsuyoshi Takagi

At PKC 2018, Chen et al. proposed SOFIA, the first MQ-based digital signature scheme secure in the quantum random oracle model (QROM). SOFIA is constructed by applying an extended version of the Unruh transform (EUROCRYPT 2015) to the 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 secure in the QROM. The signature size with our digital signature scheme decreases by about 30% compared with SOFIA.

International Symposium on Computing and Networking•Nov 1, 2019•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

The Fiat-Shamir Transformation in a Quantum World

Özgür Dagdelen, Marc Fischlin

The Fiat-Shamir transformation is a famous technique to turn identification schemes into signature schemes. The derived scheme is provably secure in the random-oracle model against classical adversaries. Still, the technique has also been suggested to be used in connection with quantum-immune identification schemes, in order to get quantum-immune signature schemes. However, a recent paper by Boneh et al. (Asiacrypt 2011) has raised the issue that results in the random-oracle model may not be immediately applicable to quantum adversaries, because such adversaries should be allowed to query the random oracle in superposition. It has been unclear if the Fiat-Shamir technique is still secure in this quantum oracle model (QROM). Here, we discuss that giving proofs for the Fiat-Shamir transformation in the QROM is presumably hard. We show that there cannot be black-box extractors, as long as the underlying quantum-immune identification scheme is secure against active adversaries and the first message of the prover is independent of its witness. Most schemes are of this type. We then discuss that for some schemes one may be able to resurrect the Fiat-Shamir result in the QROM by modifying the underlying protocol first. We discuss in particular a version of the Lyubashevsky scheme which is provably secure in the QROM.

arXiv:1306.0315•Jun 3, 2013•0 citations

A tight security reduction in the quantum random oracle model for code-based signature schemes

André Chailloux, Thomas Debris-Alazard

Quantum secure signature schemes have a lot of attention recently, in particular because of the NIST call to standardize quantum safe cryptography. However, only few signature schemes can have concrete quantum security because of technical difficulties associated with the Quantum Random Oracle Model (QROM). In this paper, we show that code-based signature schemes based on the full domain hash paradigm can behave very well in the QROM i.e. that we can have tight security reductions. We also study quantum algorithms related to the underlying code-based assumption. Finally, we apply our reduction to a concrete example: the SURF signature scheme. We provide parameters for 128 bits of quantum security in the QROM and show that the obtained parameters are competitive compared to other similar quantum secure signature schemes.

arXiv:1709.06870•Sep 20, 2017•3 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

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
SOFIA: MQ\mathcal {MQ}MQ-Based Signatures in the QROM
We propose SOFIA, the first MQ\mathcal {MQ}MQ -based signature scheme provably secure in the quantum-accessible random oracle model (QROM). Our construction relies on an extended version of Unruh’s transform for 5-pass identification schemes that we describe and prove secure both in the ROM and QROM. Based on a detailed security analysis, we provide concrete parameters for SOFIA that achieve 128-bit post-quantum security. The result is SOFIA-4-128 with parameters carefully optimized to minimize signature size and maximize performance. SOFIA-4-128 comes with an implementation targeting recent Intel processors with the AVX2 vector-instruction set; the implementation is fully protected against timing attacks.
At PKC 2018, Chen et al. proposed SOFIA, the first MQ-based digital signature scheme secure in the quantum random oracle model (QROM). SOFIA is constructed by applying an extended version of the Unruh transform (EUROCRYPT 2015) to the 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 secure in the QROM. The signature size with our digital signature scheme decreases by about 30% compared with SOFIA.
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.
The Fiat-Shamir transformation is a famous technique to turn identification schemes into signature schemes. The derived scheme is provably secure in the random-oracle model against classical adversaries. Still, the technique has also been suggested to be used in connection with quantum-immune identification schemes, in order to get quantum-immune signature schemes. However, a recent paper by Boneh et al. (Asiacrypt 2011) has raised the issue that results in the random-oracle model may not be immediately applicable to quantum adversaries, because such adversaries should be allowed to query the random oracle in superposition. It has been unclear if the Fiat-Shamir technique is still secure in this quantum oracle model (QROM). Here, we discuss that giving proofs for the Fiat-Shamir transformation in the QROM is presumably hard. We show that there cannot be black-box extractors, as long as the underlying quantum-immune identification scheme is secure against active adversaries and the first message of the prover is independent of its witness. Most schemes are of this type. We then discuss that for some schemes one may be able to resurrect the Fiat-Shamir result in the QROM by modifying the underlying protocol first. We discuss in particular a version of the Lyubashevsky scheme which is provably secure in the QROM.
Quantum secure signature schemes have a lot of attention recently, in particular because of the NIST call to standardize quantum safe cryptography. However, only few signature schemes can have concrete quantum security because of technical difficulties associated with the Quantum Random Oracle Model (QROM). In this paper, we show that code-based signature schemes based on the full domain hash paradigm can behave very well in the QROM i.e. that we can have tight security reductions. We also study quantum algorithms related to the underlying code-based assumption. Finally, we apply our reduction to a concrete example: the SURF signature scheme. We provide parameters for 128 bits of quantum security in the QROM and show that the obtained parameters are competitive compared to other similar quantum secure signature schemes.
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.
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.