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

arXiv:2005.01510

Anti-Forging Quantum Data: Cryptographic Verification of Quantum Computational Power

Man‐Hong Yung, Bin Cheng

Published May 4, 2020• 12 citations
arXivHTMLPDF

Abstract

Quantum cloud computing is emerging as a popular model for users to experience the power of quantum computing through the internet, enabling quantum computing as a service. The question is, when the scale of the computational problems becomes out of reach of classical computers, how can users be sure that the output strings sent by the server are really from a quantum hardware? In 2008, Shepherd and Bremner proposed a cryptographic verification protocol based on a simplified circuit model called IQP (instantaneous quantum polynomial-time), which can potentially be applied to most existing quantum cloud platforms. However, the Shepherd-Bremner protocol has recently been shown to be insecure by Kahanamoku-Meyer. Here we present an extended model of IQP-based cryptographic verification protocol, where the Shepherd-Bremner construction can be regarded as a special case. This protocol not only can avoid the attack by Kahanamoku-Meyer but also provide several additional security measures for anti-forging quantum data. In particular, our protocol admits a simultaneous encoding of multiple secret strings, strengthening significantly the hardness for classical hacking. Furthermore, we provide methods for estimating the correlation functions associated with the secret strings, which are the key elements in our verification protocol.

DOI
10.48550/arxiv.2005.01510

Related papers

Anti-Forging Quantum Data: Cryptographic Verification of Quantum Cloud Computing

Man‐Hong Yung, Bin Cheng

Quantum cloud computing is emerging as a popular model for users to experience the power of quantum computing through the internet, enabling quantum computing as a service (QCaaS). The question is, when the scale of the computational problems becomes out of reach of classical computers, how can users be sure that the output strings sent by the server are really from a quantum hardware? In 2008, Shepherd and Bremner proposed a cryptographic verification protocol based on a simplified circuit model called IQP (instantaneous quantum polynomial-time), which can potentially be applied to most existing quantum cloud platforms. However, the Shepherd-Bremner protocol has recently been shown to be insecure by Kahanamoku-Meyer. Here we present a generalized model of cryptographic verification protocol, where the Shepherd-Bremner model can be regarded as a special case. This protocol not only can avoid the attack by Kahanamoku-Meyer but also provide several additional security measures for anti-forging quantum data. In particular, our protocol admits a simultaneous encoding of multiple secret strings, strengthening significantly the hardness for classical hacking. Furthermore, we provide methods for estimating the correlation functions associated with the secret strings, which are the key elements in our verification protocol.

•May 4, 2020•2 citations

Secret-Extraction Attacks against Obfuscated Instantaneous Quantum Polynomial-Time Circuits

David Gross, Dominik Hangleiter

Quantum computing devices can now perform sampling tasks that, according to complexity-theoretic and numerical evidence, are beyond the reach of classical computers. This raises the question of how one can efficiently verify that a quantum computer operating in this regime works as intended. In 2008, Shepherd and Bremner proposed a protocol in which a verifier constructs a unitary from the comparatively easy-to-implement family of so-called and challenges a prover to execute it on a quantum computer. The challenge problem is designed to contain an obfuscated secret, which can be turned into a statistical test that accepts samples from a correct quantum implementation. It was conjectured that extracting the secret from the challenge problem is -hard, so that the ability to pass the test constitutes strong evidence that the prover possesses a quantum device and that it works as claimed. Unfortunately, about a decade later, Kahanamoku-Meyer found an efficient classical secret-extraction attack. Bremner, Cheng, and Ji very recently followed up by constructing a wide-ranging generalization of the original protocol. Their has been explicitly designed to circumvent the known weakness. They also suggested that the original construction can be made secure by adjusting the problem parameters. In this work, we develop a number of secret-extraction attacks that are effective against both new approaches in a wide range of problem parameters. In particular, we find multiple ways to recover the 300 -bit secret hidden in a challenge data set published by Bremner, Cheng, and Ji. The important problem of finding an efficient and reliable verification protocol for sampling-based proofs of quantum advantage thus remains open.

arXiv:2312.10156•PRX Quantum•Apr 22, 2025•8 citations

Forging quantum data: classically defeating an IQP-based quantum test

Gregory D. Kahanamoku–Meyer

Recently, quantum computing experiments have for the first time exceeded the capability of classical computers to perform certain computations – a milestone termed "quantum computational advantage." However, verifying the output of the quantum device in these experiments required extremely large classical computations. An exciting next step for demonstrating quantum capability would be to implement tests of quantum computational advantage with efficient classical verification, such that larger system sizes can be tested and verified. One of the first proposals for an efficiently-verifiable test of quantumness consists of hiding a secret classical bitstring inside a circuit of the class IQP, in such a way that samples from the circuit's output distribution are correlated with the secret. The classical hardness of this protocol has been supported by evidence that directly simulating IQP circuits is hard, but the security of the protocol against other (non-simulating) classical attacks has remained an open question. In this work we demonstrate that the protocol is not secure against classical forgery. We describe a classical algorithm that can not only convince the verifier that the (classical) prover is quantum, but can in fact can extract the secret key underlying a given protocol instance. Furthermore, we show that the key extraction algorithm is efficient in practice for problem sizes of hundreds of qubits. Finally, we provide an implementation of the algorithm, and give the secret vector underlying the "\$25 challenge" posted online by the authors of the original paper.

arXiv:1912.05547•Quantum•Sep 11, 2023•23 citations

Advancing Quantum Cryptography Algorithms for Secure Data Storage and Processing in Cloud Computing: Enhancing Robustness Against Emerging Cyber Threats

Devulapally Swetha, Shaik Khaja Mohiddin

The rise of cloud computing has transformed data storage and processing but introduced new vulnerabilities, especially with the impending threat of quantum computing. Traditional cryptographic methods, though currently effective, are at risk of being compromised by quantum attacks. This research aims to develop a quantum-resistant security framework for cloud environments, combining lattice-based cryptography with Quantum Key Distribution (QKD) protocols, particularly the E91 protocol, for secure key management. The framework also incorporates quantum authentication protocols to enhance user identity verification, protecting against unauthorized access and tampering. The proposed solution balances robust security with practical implementation, ensuring scalability and efficiency in real-world cloud environments. Performance evaluations indicate an encryption time of approximately 30 milliseconds, outperforming existing methods such as RSA and DES. This research contributes to the development of future-proof cryptographic standards, addressing both current security challenges and emerging quantum computing threats. By leveraging quantum mechanics, the framework strengthens cloud-based data protection, providing a resilient solution against evolving cyber risks. The results hold significant promise for advancing cloud security, laying the groundwork for next-generation encryption techniques that can withstand the threats posed by quantum computing.

International Journal of Advanced Computer Science and Applications•Jan 1, 2024•7 citations

Efficient verification of universal and intermediate quantum computing

Theodoros Kapourniotis

The promise of scalable quantum technology appears more realistic, after recent advances in both theory and experiment. Assuming a quantum computer is developed, the task of verifying the correctness of its outcome becomes crucial. Unfortunately, for a system that involves many particles, predicting its evolution via classical simulation becomes intractable. Moreover, verification of the outcome by computational methods, i.e. involving a classical witness, is believed inefficient for the hardest problems solvable by a quantum computer. A feasible alternative to verify quantum computation is via cryptographic methods, where an untrusted prover has to convince a weak verifier for the correctness of his outcome. This is the approach we take in this thesis. In the most standard configuration the prover is capable of computing all polynomial-time quantum circuits and the verifier is restricted to classical with very modest quantum power. The goal of existing verification protocols is to reduce the quantum requirements for the verifier - ideally making it purely classical - and reduce the communication complexity. In Part II we propose a composition of two existing verification protocols [Fitzsimons and Kashefi, 2012], [Aharonov et al., 2010] that achieves quadratic improvement in communication complexity, while keeping the quantum requirements for the verifier modest. Along this result, several new techniques are proposed, including the generalization of [Fitzsimons and Kashefi, 2012] to prime dimensions. In Part III we discuss the idea of model-specific quantum verification, where the prover is restricted to intermediate quantum power, i.e. between full-fledged quantum and purely classical, thus more feasible experimentally. As a proof of principle we propose a verification protocol for the One-Pure-Qubit computer [Knill and Laflamme, 1998], which tolerates noise and is capable of computing hard problems such as large matrix trace estimation. The verification protocol is an adaptation of [Fitzsimons and Kashefi, 2012] running on Measurement-Based Quantum Computing with newly proved properties of the underlying resources. Connections of quantum verification to other security primitives are considered in Part IV. Authenticated quantum communication has been already proved to relate to quantum verification. We expand this by proposing a quantum authentication protocol derived from [Fitzsimons and Kashefi, 2012] and discuss implications to verification with purely classical verifier. Connections between quantum security primitives, namely blindness - prover does not learn the computation -, and classical security are considered in Part V. We introduce a protocol where a client with restricted classical resources computes blindly a universal classical gate with the help of an untrusted server, by adding modest quantum capabilities to both client and server. This example of quantum-enhanced classical security we prove to be a task classically impossible.

•Nov 29, 2016•1 citation

Quantum-resistant cryptographic protocols for securing cloud storage and data transmission in hybrid enterprise IT environments

Martha Masunda

The exponential growth of cloud computing and hybrid enterprise IT infrastructures has significantly transformed how organizations store, process, and transmit data. As reliance on distributed systems deepens, ensuring the confidentiality, integrity, and availability of sensitive information has become a paramount concern especially in the face of emerging quantum computing capabilities. Quantum computers, once fully realized, will render many current public-key cryptographic systems such as RSA, ECC, and DH obsolete due to their vulnerability to quantum algorithms like Shor’s and Grover’s. This looming threat demands a paradigm shift toward quantum-resistant cryptographic protocols that can safeguard digital assets across dynamic and heterogeneous environments. This study presents a comprehensive analysis of quantum-resistant cryptographic schemes, focusing on lattice-based, hash-based, multivariate polynomial, and code-based approaches. These protocols are critically evaluated in terms of computational efficiency, scalability, resistance to side-channel attacks, and adaptability to multi-tenant cloud architectures. Special emphasis is placed on their integration into hybrid enterprise IT ecosystems, which often comprise on-premises servers, private clouds, and public cloud services each with unique security and compliance requirements. Additionally, the research proposes a layered security model that leverages post-quantum encryption for data-at-rest, hybrid key exchange mechanisms for secure data-in-transit, and secure bootstrapping protocols for cross-domain identity verification. Through simulations and policy analysis, this work demonstrates how quantum-resilient cryptography can be effectively deployed without compromising system performance or interoperability. Ultimately, the findings aim to guide enterprises, cloud providers, and cybersecurity professionals in building forward-compatible, future-proof data protection strategies.

World Journal of Advanced Research and Reviews•Jun 30, 2022•2 citations
Quantum cloud computing is emerging as a popular model for users to experience the power of quantum computing through the internet, enabling quantum computing as a service. The question is, when the scale of the computational problems becomes out of reach of classical computers, how can users be sure that the output strings sent by the server are really from a quantum hardware? In 2008, Shepherd and Bremner proposed a cryptographic verification protocol based on a simplified circuit model called IQP (instantaneous quantum polynomial-time), which can potentially be applied to most existing quantum cloud platforms. However, the Shepherd-Bremner protocol has recently been shown to be insecure by Kahanamoku-Meyer. Here we present an extended model of IQP-based cryptographic verification protocol, where the Shepherd-Bremner construction can be regarded as a special case. This protocol not only can avoid the attack by Kahanamoku-Meyer but also provide several additional security measures for anti-forging quantum data. In particular, our protocol admits a simultaneous encoding of multiple secret strings, strengthening significantly the hardness for classical hacking. Furthermore, we provide methods for estimating the correlation functions associated with the secret strings, which are the key elements in our verification protocol.
Quantum cloud computing is emerging as a popular model for users to experience the power of quantum computing through the internet, enabling quantum computing as a service (QCaaS). The question is, when the scale of the computational problems becomes out of reach of classical computers, how can users be sure that the output strings sent by the server are really from a quantum hardware? In 2008, Shepherd and Bremner proposed a cryptographic verification protocol based on a simplified circuit model called IQP (instantaneous quantum polynomial-time), which can potentially be applied to most existing quantum cloud platforms. However, the Shepherd-Bremner protocol has recently been shown to be insecure by Kahanamoku-Meyer. Here we present a generalized model of cryptographic verification protocol, where the Shepherd-Bremner model can be regarded as a special case. This protocol not only can avoid the attack by Kahanamoku-Meyer but also provide several additional security measures for anti-forging quantum data. In particular, our protocol admits a simultaneous encoding of multiple secret strings, strengthening significantly the hardness for classical hacking. Furthermore, we provide methods for estimating the correlation functions associated with the secret strings, which are the key elements in our verification protocol.
Quantum computing devices can now perform sampling tasks that, according to complexity-theoretic and numerical evidence, are beyond the reach of classical computers. This raises the question of how one can efficiently verify that a quantum computer operating in this regime works as intended. In 2008, Shepherd and Bremner proposed a protocol in which a verifier constructs a unitary from the comparatively easy-to-implement family of so-called and challenges a prover to execute it on a quantum computer. The challenge problem is designed to contain an obfuscated secret, which can be turned into a statistical test that accepts samples from a correct quantum implementation. It was conjectured that extracting the secret from the challenge problem is -hard, so that the ability to pass the test constitutes strong evidence that the prover possesses a quantum device and that it works as claimed. Unfortunately, about a decade later, Kahanamoku-Meyer found an efficient classical secret-extraction attack. Bremner, Cheng, and Ji very recently followed up by constructing a wide-ranging generalization of the original protocol. Their has been explicitly designed to circumvent the known weakness. They also suggested that the original construction can be made secure by adjusting the problem parameters. In this work, we develop a number of secret-extraction attacks that are effective against both new approaches in a wide range of problem parameters. In particular, we find multiple ways to recover the 300 -bit secret hidden in a challenge data set published by Bremner, Cheng, and Ji. The important problem of finding an efficient and reliable verification protocol for sampling-based proofs of quantum advantage thus remains open.
Recently, quantum computing experiments have for the first time exceeded the capability of classical computers to perform certain computations – a milestone termed "quantum computational advantage." However, verifying the output of the quantum device in these experiments required extremely large classical computations. An exciting next step for demonstrating quantum capability would be to implement tests of quantum computational advantage with efficient classical verification, such that larger system sizes can be tested and verified. One of the first proposals for an efficiently-verifiable test of quantumness consists of hiding a secret classical bitstring inside a circuit of the class IQP, in such a way that samples from the circuit's output distribution are correlated with the secret. The classical hardness of this protocol has been supported by evidence that directly simulating IQP circuits is hard, but the security of the protocol against other (non-simulating) classical attacks has remained an open question. In this work we demonstrate that the protocol is not secure against classical forgery. We describe a classical algorithm that can not only convince the verifier that the (classical) prover is quantum, but can in fact can extract the secret key underlying a given protocol instance. Furthermore, we show that the key extraction algorithm is efficient in practice for problem sizes of hundreds of qubits. Finally, we provide an implementation of the algorithm, and give the secret vector underlying the "$25 challenge" posted online by the authors of the original paper.
The rise of cloud computing has transformed data storage and processing but introduced new vulnerabilities, especially with the impending threat of quantum computing. Traditional cryptographic methods, though currently effective, are at risk of being compromised by quantum attacks. This research aims to develop a quantum-resistant security framework for cloud environments, combining lattice-based cryptography with Quantum Key Distribution (QKD) protocols, particularly the E91 protocol, for secure key management. The framework also incorporates quantum authentication protocols to enhance user identity verification, protecting against unauthorized access and tampering. The proposed solution balances robust security with practical implementation, ensuring scalability and efficiency in real-world cloud environments. Performance evaluations indicate an encryption time of approximately 30 milliseconds, outperforming existing methods such as RSA and DES. This research contributes to the development of future-proof cryptographic standards, addressing both current security challenges and emerging quantum computing threats. By leveraging quantum mechanics, the framework strengthens cloud-based data protection, providing a resilient solution against evolving cyber risks. The results hold significant promise for advancing cloud security, laying the groundwork for next-generation encryption techniques that can withstand the threats posed by quantum computing.
The promise of scalable quantum technology appears more realistic, after recent advances in both theory and experiment. Assuming a quantum computer is developed, the task of verifying the correctness of its outcome becomes crucial. Unfortunately, for a system that involves many particles, predicting its evolution via classical simulation becomes intractable. Moreover, verification of the outcome by computational methods, i.e. involving a classical witness, is believed inefficient for the hardest problems solvable by a quantum computer. A feasible alternative to verify quantum computation is via cryptographic methods, where an untrusted prover has to convince a weak verifier for the correctness of his outcome. This is the approach we take in this thesis. In the most standard configuration the prover is capable of computing all polynomial-time quantum circuits and the verifier is restricted to classical with very modest quantum power. The goal of existing verification protocols is to reduce the quantum requirements for the verifier - ideally making it purely classical - and reduce the communication complexity. In Part II we propose a composition of two existing verification protocols [Fitzsimons and Kashefi, 2012], [Aharonov et al., 2010] that achieves quadratic improvement in communication complexity, while keeping the quantum requirements for the verifier modest. Along this result, several new techniques are proposed, including the generalization of [Fitzsimons and Kashefi, 2012] to prime dimensions. In Part III we discuss the idea of model-specific quantum verification, where the prover is restricted to intermediate quantum power, i.e. between full-fledged quantum and purely classical, thus more feasible experimentally. As a proof of principle we propose a verification protocol for the One-Pure-Qubit computer [Knill and Laflamme, 1998], which tolerates noise and is capable of computing hard problems such as large matrix trace estimation. The verification protocol is an adaptation of [Fitzsimons and Kashefi, 2012] running on Measurement-Based Quantum Computing with newly proved properties of the underlying resources. Connections of quantum verification to other security primitives are considered in Part IV. Authenticated quantum communication has been already proved to relate to quantum verification. We expand this by proposing a quantum authentication protocol derived from [Fitzsimons and Kashefi, 2012] and discuss implications to verification with purely classical verifier. Connections between quantum security primitives, namely blindness - prover does not learn the computation -, and classical security are considered in Part V. We introduce a protocol where a client with restricted classical resources computes blindly a universal classical gate with the help of an untrusted server, by adding modest quantum capabilities to both client and server. This example of quantum-enhanced classical security we prove to be a task classically impossible.
The exponential growth of cloud computing and hybrid enterprise IT infrastructures has significantly transformed how organizations store, process, and transmit data. As reliance on distributed systems deepens, ensuring the confidentiality, integrity, and availability of sensitive information has become a paramount concern especially in the face of emerging quantum computing capabilities. Quantum computers, once fully realized, will render many current public-key cryptographic systems such as RSA, ECC, and DH obsolete due to their vulnerability to quantum algorithms like Shor’s and Grover’s. This looming threat demands a paradigm shift toward quantum-resistant cryptographic protocols that can safeguard digital assets across dynamic and heterogeneous environments. This study presents a comprehensive analysis of quantum-resistant cryptographic schemes, focusing on lattice-based, hash-based, multivariate polynomial, and code-based approaches. These protocols are critically evaluated in terms of computational efficiency, scalability, resistance to side-channel attacks, and adaptability to multi-tenant cloud architectures. Special emphasis is placed on their integration into hybrid enterprise IT ecosystems, which often comprise on-premises servers, private clouds, and public cloud services each with unique security and compliance requirements. Additionally, the research proposes a layered security model that leverages post-quantum encryption for data-at-rest, hybrid key exchange mechanisms for secure data-in-transit, and secure bootstrapping protocols for cross-domain identity verification. Through simulations and policy analysis, this work demonstrates how quantum-resilient cryptography can be effectively deployed without compromising system performance or interoperability. Ultimately, the findings aim to guide enterprises, cloud providers, and cybersecurity professionals in building forward-compatible, future-proof data protection strategies.