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

A New Identification Scheme based on Syndrome Decoding Problem with Provable Security against Quantum Adversaries

Bagus Santoso, Chunhua Su

Published Apr 7, 2020• 0 citations
Publisher

Abstract

Recently, in order to guarantee security against quantum adversaries, several identification (ID) schemes based on computational problems which are supposed to be hard even for quantum computers have been proposed. However, their security are only proven against non-quantum adversaries. In this paper, we proposed a novel four-pass code-based identification scheme. By using quantum random oracle model, we provide a security proof for our scheme against quantum adversaries which aim to impersonate the prover under concurrent active attacks, based on the hardness assumption of syndrome decoding (SD) problem. Our security proof is interesting in its own right, since it only requires a non-programmable quantum random oracle, in contrast to existing security proofs of digital signatures generated from ID scheme via Fiat-Shamir transform which require programmable quantum random oracles.

DOI
10.3217/jucs-025-03-0294

Related papers

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 provable secure signature in the quantum random oracle model

Zhen Zhang, Huiyan Chen, Yufan Chen

With the development of quantum computation, quantum computers will break the almost classical cryptography. It is imminent to design post-quantum cryptography algorithm that could resist quantum adversaries. Lattice-based problem has been verified that could resist quantum attacks. Our goal is to design a signature and try to prove it is secure in the quantum random oracle model. Our new signature scheme is redesigned based on the signature proposed by Lyu, but that scheme only proved secure in the random oracle model. The difference between the two signature is that we introduce the middle-product operation. So our signature is based on middle-product LWE hard assumption, which enjoys a security proof from PL WE. Then we combine the secure chameleon hash function and our new scheme, prove that our new combined signature is still secure in the quantum random oracle model.

International Conference on Blockchain Technology and Information Security (ICBCTIS)•Jul 1, 2022•2 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

A Provably Secure Group Signature Scheme from Code-Based Assumptions.

Martianus Frederic Ezerman, Hyung Tae Lee, San Ling +2 more

Abstract. We solve an open question in code-based cryptography by introducing the first provably secure group signature scheme from code-based assumptions. Specifically, the scheme satisfies the CPA-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise prob-lem, and a variant of the Syndrome Decoding problem. Our construction produces smaller key and signature sizes than the existing post-quantum group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed the population of the Netherlands ( ≈ 224 users). The feasibility of the scheme is supported by implementa-tion results. Additionally, the techniques introduced in this work might be of independent interest: a new verifiable encryption protocol for the randomized McEliece encryption and a new approach to design formal security reductions from the Syndrome Decoding problem.

•Jan 1, 2015•0 citations

Secure Identity-Based Encryption in the Quantum Random Oracle Model

Mark Zhandry

We give the first proof of security for an identity-based encryption scheme in the quantum random oracle model. This is the first proof of security for any scheme in this model that requires no additional assumptions. Our techniques are quite general and we use them to obtain security proofs for two random oracle hierarchical identity-based encryption schemes and a random oracle signature scheme, all of which have previously resisted quantum security proofs, even using additional assumptions. We also explain how to remove the extra assumptions from prior quantum random oracle model proofs. We accomplish these results by developing new tools for arguing that quantum algorithms cannot distinguish between two oracle distributions. Using a particular class of oracle distributions, so called semi-constant distributions, we argue that the aforementioned cryptosystems are secure against quantum adversaries.

•Jan 1, 2012•83 citations

A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions

Pedro Costa Branco

In this work, we propose a post-quantum UC-commitment scheme in the Global Random Oracle Model, where only one non-programmable random oracle is available. The security of our proposal is based on two well-established post-quantum hardness assumptions from coding theory: The Syndrome Decoding and the Goppa Distinguisher. We prove that our proposal is perfectly hiding and computationally binding.

Advances in Mathematics of Communications•Nov 25, 2019•2 citations
Recently, in order to guarantee security against quantum adversaries, several identification (ID) schemes based on computational problems which are supposed to be hard even for quantum computers have been proposed. However, their security are only proven against non-quantum adversaries. In this paper, we proposed a novel four-pass code-based identification scheme. By using quantum random oracle model, we provide a security proof for our scheme against quantum adversaries which aim to impersonate the prover under concurrent active attacks, based on the hardness assumption of syndrome decoding (SD) problem. Our security proof is interesting in its own right, since it only requires a non-programmable quantum random oracle, in contrast to existing security proofs of digital signatures generated from ID scheme via Fiat-Shamir transform which require programmable quantum random oracles.
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.
With the development of quantum computation, quantum computers will break the almost classical cryptography. It is imminent to design post-quantum cryptography algorithm that could resist quantum adversaries. Lattice-based problem has been verified that could resist quantum attacks. Our goal is to design a signature and try to prove it is secure in the quantum random oracle model. Our new signature scheme is redesigned based on the signature proposed by Lyu, but that scheme only proved secure in the random oracle model. The difference between the two signature is that we introduce the middle-product operation. So our signature is based on middle-product LWE hard assumption, which enjoys a security proof from PL WE. Then we combine the secure chameleon hash function and our new scheme, prove that our new combined signature is still secure in the quantum random oracle model.
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.
Abstract. We solve an open question in code-based cryptography by introducing the first provably secure group signature scheme from code-based assumptions. Specifically, the scheme satisfies the CPA-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise prob-lem, and a variant of the Syndrome Decoding problem. Our construction produces smaller key and signature sizes than the existing post-quantum group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed the population of the Netherlands ( ≈ 224 users). The feasibility of the scheme is supported by implementa-tion results. Additionally, the techniques introduced in this work might be of independent interest: a new verifiable encryption protocol for the randomized McEliece encryption and a new approach to design formal security reductions from the Syndrome Decoding problem.
We give the first proof of security for an identity-based encryption scheme in the quantum random oracle model. This is the first proof of security for any scheme in this model that requires no additional assumptions. Our techniques are quite general and we use them to obtain security proofs for two random oracle hierarchical identity-based encryption schemes and a random oracle signature scheme, all of which have previously resisted quantum security proofs, even using additional assumptions. We also explain how to remove the extra assumptions from prior quantum random oracle model proofs. We accomplish these results by developing new tools for arguing that quantum algorithms cannot distinguish between two oracle distributions. Using a particular class of oracle distributions, so called semi-constant distributions, we argue that the aforementioned cryptosystems are secure against quantum adversaries.