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

IEEE Access

Quantum Random Oracle Model for Quantum Public-Key Encryption

Tao Shang, Ranyiliu Chen, Qi Lei

Published Jan 1, 2019• 12 citations
Publisher

Abstract

Random oracle model is a general security analysis tool for rigorous security proof and effective cryptographic protocol design. In the quantum world, the attempts of constructing a quantum random oracle (QRO) have been made, such as quantum-accessible random oracle for post-quantum cryptography and quantum random oracle for quantum digital signature. As in the classical circumstance, it is crucial and challenging to design and instantiate the QRO model with an appropriate quantum hash function. In this work, we construct a QRO model for quantum public-key encryption against key-collision attack, due to the near-orthogonality property of the QRO. To explore a feasible instantiation procedure in the quantum setting, we distinctively give two instantiation examples of QRO by means of single-qubit rotation and quantum fingerprinting, and compare the numerical results of their performances under the key-collision attack. As a result, we extend the QRO model to the security analysis of quantum public-key encryption beyond quantum digital signature, and immunity from collision-type attacks.

DOI
10.1109/access.2019.2940406

Related papers

Quantum random oracle model for quantum digital signature

Tao Shang, Qi Lei, Jianwei Liu

The goal of this work is to provide a general security analysis tool, namely, the quantum random oracle (QRO), for facilitating the security analysis of quantum cryptographic protocols, especially protocols based on quantum one-way function. QRO is used to model quantum one-way function and different queries to QRO are used to model quantum attacks. A typical application of quantum one-way function is the quantum digital signature, whose progress has been hampered by the slow pace of the experimental realization. Alternatively, we use the QRO model to analyze the provable security of a quantum digital signature scheme and elaborate the analysis procedure. The QRO model differs from the prior quantum-accessible random oracle in that it can output quantum states as public keys and give responses to different queries. This tool can be a test bed for the cryptanalysis of more quantum cryptographic protocols based on the quantum one-way function.

Physical Review A•Oct 10, 2016•21 citations

Post-Quantum Security of Authenticated Key Establishment Protocols

Jason T. LeGrow

We present a security model for authenticated key establishment that allows for quantum interactions between the adversary and quantum oracles that emulate classical parties, resulting in a truly post-quantum security definition. We then give a generic construction for a secure protocol in the quantum random oracle model by combining a signature scheme which is existentially unforgeable under adaptive quantum chosen message attack in the quantum random oracle model (EUF-qCMA-QRO secure) with an unauthenticated key establishment protocol which is secure against a passive adversary. This construction allows us to give an explicit example of a secure protocol whose security is based on a variant of the Diffie-Hellman problem for isogenies of supersingular elliptic curves; in particular, generic security-strengthening transformations allow us to take a signature scheme which is EUF-CMA-RO secure against a quantum adversary and transform it into an EUF-qCMA-QRO signature scheme, which we combine with a standard secure unauthenticated key establishment protocol to achieve the desired result.

•Apr 20, 2016•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

Analysis of DSTU 8961:2019 in the quantum random oracle model

Serhii Kandii, І.Д. Горбенко

Modern cryptographic transformations require provable security against a relatively wide class of threats. Typically, such evidentiary security is achieved through formal analysis within the chosen security model. The development of quantum computers led to the emergence of new attack vectors to which classical cryptography was vulnerable. However, there are cryptographic systems that are considered resistant to quantum attacks and some of them are even standardized. The formal analysis of such systems has faced difficulties for a long time, which were associated with the impossibility of applying classical methods of proof to formal models that take into account quantum effects. However, in recent years, many new results have appeared that allow obtaining formal security proofs for quite complex cryptographic transformations, and most of the existing post-quantum asymmetric encryption and key encapsulation schemes currently have corresponding formal proofs within the quantum random oracle model, the most widespread security model for of post-quantum cryptography. DSTU 8961:2019 is the Ukrainian post-quantum standard for asymmetric encryption and key encapsulation. However, security proofs in the quantum random oracle model have not yet been published for it. As part of this work, security evidence was obtained for the design of the key encapsulation mechanism described in DSTU 8961:209. The obtained result is generalized for an arbitrary asymmetric encryption scheme, which may contain decryption errors and can be used to assess the security of not only DSTU 8961:2019, but also other similar asymmetric transformations.

Radiotekhnika•Sep 29, 2023•2 citations

Practical Quantum Public Key Encryption from One-way Functions

Kyohei Sudo, Keisuke Fujii, Keisuke Hara +3 more

We construct a quantum public key encryption scheme from oneway functions in the random oracle model. While our construction only has indistinguishability against restricted adversaries, who perform individual attacks and can only make classical queries to the random oracle, it possesses two practical advantages that were not achieved in previous works. First, legitimate participants can discard noisy quantum public keys. Second, the scheme only requires products of single-qubit states, and it does not require quantum computing or quantum memory for legitimate participants. Although the security does not hold against adversaries capable of large-scale quantum computation, we believe that our protocol is well-suited for the near-term stage of the quantum era.

ACM ASIA Public-Key Cryptography Workshop (APKC)•Jun 6, 2025•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
Random oracle model is a general security analysis tool for rigorous security proof and effective cryptographic protocol design. In the quantum world, the attempts of constructing a quantum random oracle (QRO) have been made, such as quantum-accessible random oracle for post-quantum cryptography and quantum random oracle for quantum digital signature. As in the classical circumstance, it is crucial and challenging to design and instantiate the QRO model with an appropriate quantum hash function. In this work, we construct a QRO model for quantum public-key encryption against key-collision attack, due to the near-orthogonality property of the QRO. To explore a feasible instantiation procedure in the quantum setting, we distinctively give two instantiation examples of QRO by means of single-qubit rotation and quantum fingerprinting, and compare the numerical results of their performances under the key-collision attack. As a result, we extend the QRO model to the security analysis of quantum public-key encryption beyond quantum digital signature, and immunity from collision-type attacks.
The goal of this work is to provide a general security analysis tool, namely, the quantum random oracle (QRO), for facilitating the security analysis of quantum cryptographic protocols, especially protocols based on quantum one-way function. QRO is used to model quantum one-way function and different queries to QRO are used to model quantum attacks. A typical application of quantum one-way function is the quantum digital signature, whose progress has been hampered by the slow pace of the experimental realization. Alternatively, we use the QRO model to analyze the provable security of a quantum digital signature scheme and elaborate the analysis procedure. The QRO model differs from the prior quantum-accessible random oracle in that it can output quantum states as public keys and give responses to different queries. This tool can be a test bed for the cryptanalysis of more quantum cryptographic protocols based on the quantum one-way function.
We present a security model for authenticated key establishment that allows for quantum interactions between the adversary and quantum oracles that emulate classical parties, resulting in a truly post-quantum security definition. We then give a generic construction for a secure protocol in the quantum random oracle model by combining a signature scheme which is existentially unforgeable under adaptive quantum chosen message attack in the quantum random oracle model (EUF-qCMA-QRO secure) with an unauthenticated key establishment protocol which is secure against a passive adversary. This construction allows us to give an explicit example of a secure protocol whose security is based on a variant of the Diffie-Hellman problem for isogenies of supersingular elliptic curves; in particular, generic security-strengthening transformations allow us to take a signature scheme which is EUF-CMA-RO secure against a quantum adversary and transform it into an EUF-qCMA-QRO signature scheme, which we combine with a standard secure unauthenticated key establishment protocol to achieve the desired result.
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.
Modern cryptographic transformations require provable security against a relatively wide class of threats. Typically, such evidentiary security is achieved through formal analysis within the chosen security model. The development of quantum computers led to the emergence of new attack vectors to which classical cryptography was vulnerable. However, there are cryptographic systems that are considered resistant to quantum attacks and some of them are even standardized. The formal analysis of such systems has faced difficulties for a long time, which were associated with the impossibility of applying classical methods of proof to formal models that take into account quantum effects. However, in recent years, many new results have appeared that allow obtaining formal security proofs for quite complex cryptographic transformations, and most of the existing post-quantum asymmetric encryption and key encapsulation schemes currently have corresponding formal proofs within the quantum random oracle model, the most widespread security model for of post-quantum cryptography. DSTU 8961:2019 is the Ukrainian post-quantum standard for asymmetric encryption and key encapsulation. However, security proofs in the quantum random oracle model have not yet been published for it. As part of this work, security evidence was obtained for the design of the key encapsulation mechanism described in DSTU 8961:209. The obtained result is generalized for an arbitrary asymmetric encryption scheme, which may contain decryption errors and can be used to assess the security of not only DSTU 8961:2019, but also other similar asymmetric transformations.
We construct a quantum public key encryption scheme from oneway functions in the random oracle model. While our construction only has indistinguishability against restricted adversaries, who perform individual attacks and can only make classical queries to the random oracle, it possesses two practical advantages that were not achieved in previous works. First, legitimate participants can discard noisy quantum public keys. Second, the scheme only requires products of single-qubit states, and it does not require quantum computing or quantum memory for legitimate participants. Although the security does not hold against adversaries capable of large-scale quantum computation, we believe that our protocol is well-suited for the near-term stage of the quantum era.
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.