With the rapid development of quantum computers, proofs of quantumness have recently become an interesting research direction. However, in current schemes for proofs of quantumness, quantum provers face the risk of being maliciously exploited by classical verifiers. Through malicious strategies in interaction with quantum provers, classical verifiers could solve some instances of hard problems that arise from the specific scheme in use. This is due to the lack of formalization that prevents malicious verifiers from extracting useful information in proofs of quantumness. To address this issue, we formalize zero-knowledge proofs of quantumness. Intuitively, the zero-knowledge property necessitates that the information gained by the classical verifier from interactions with the quantum prover should not surpass what can be simulated using a simulated classical prover interacting with the same verifier. As a result, the new zero-knowledge notion can prevent a malicious verifier from exploiting quantum advantage. We find that the classical zero-knowledge proof is sufficient to compile some existing proofs of quantumness schemes into zero-knowledge proofs of quantumness schemes. It appears to be more general to require zero-knowledge proof on the verifier side instead of the prover side. This helps to regulate the verifier's behavior from malicious to be honest-but-curious. As a result, both parties will play not only one role in the proofs of quantumness but also the dual role in the classical zero-knowledge proof. Specifically, Shor's factoring-based scheme and the learning with errors-based scheme in [Brakerski et al., FOCS, 2018] can be transformed into zero-knowledge proofs of quantumness by requiring an extractable non-interactive zero-knowledge argument on the verifier side. Zero-knowledge proofs of quantumness can thus be viewed as an enhanced security notion for proofs of quantumness.
AI Summary
Proofs of quantumness usually protect against classical provers impersonating quantum devices, but need not protect quantum provers against malicious verifiers. For example, a verifier could submit an RSA modulus as a factoring challenge and obtain its factors. This paper defines zero-knowledge proofs of quantumness (ZKPoQ), requiring quantum completeness, classical soundness, and classical polynomial-time simulation of a malicious classical verifier’s view.
Two constructions modify factoring-based proofs of quantumness and the LWE-based trapdoor-claw-free-function protocol of Brakerski et al. The verifier supplies an extractable noninteractive zero-knowledge argument demonstrating knowledge of the challenge’s factorization or LWE secret. The quantum prover checks this argument before continuing. For zero knowledge, a classical simulator generates a reference string with an extraction trapdoor, extracts the verifier’s witness, and uses it to simulate the quantum prover’s responses. Classical soundness is established by replacing the verifier’s argument with a simulated argument and reducing to the original protocol’s soundness. The claimed guarantees are acceptance probability $1-\operatorname{negl}(\lambda)$ for honest quantum provers, negligible acceptance for classical provers, and computational zero knowledge; the LWE construction uses $\lambda$ repetitions.
The constructions require a common reference string and existing extractable-NIZK machinery. Classically secure arguments suffice for the stated PoQ guarantees; post-quantum security is discussed for possible extensions such as randomness certification and key leasing. No generic transformation is established: applicability to other LWE protocols and sampling-based demonstrations remains open, as does a formal plain-model replacement using interactive zero-knowledge proofs.
Little sign of AI-generated textPossible errorOverclaimsUnclear writing
Central claim may not hold: The factoring ZKPoQ theorem omits classical hardness of factoring, although its soundness proof requires that assumption in addition to the stated LWE assumption.
The LWE construction proves knowledge of an LWE secret without enforcing the NTCF key conditions needed for its simulation, admitting degenerate keys for which the supplied simulator produces distinguishable Hadamard responses.
The LWE simulator uses x XOR (x−s) regardless of its sampled branch, although branch 1 requires (x+s) XOR x, invalidating its claimed transcript-distribution equality.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Journal reference
IACR Communications in Cryptology, vol. 1, no. 4, 2025
With the rapid development of quantum computers, proofs of quantumness have recently become an interesting research direction. However, in current schemes for proofs of quantumness, quantum provers face the risk of being maliciously exploited by classical verifiers. Through malicious strategies in interaction with quantum provers, classical verifiers could solve some instances of hard problems that arise from the specific scheme in use. This is due to the lack of formalization that prevents malicious verifiers from extracting useful information in proofs of quantumness. To address this issue, we formalize zero-knowledge proofs of quantumness. Intuitively, the zero-knowledge property necessitates that the information gained by the classical verifier from interactions with the quantum prover should not surpass what can be simulated using a simulated classical prover interacting with the same verifier. As a result, the new zero-knowledge notion can prevent a malicious verifier from exploiting quantum advantage. We find that the classical zero-knowledge proof is sufficient to compile some existing proofs of quantumness schemes into zero-knowledge proofs of quantumness schemes. It appears to be more general to require zero-knowledge proof on the verifier side instead of the prover side. This helps to regulate the verifier's behavior from malicious to be honest-but-curious. As a result, both parties will play not only one role in the proofs of quantumness but also the dual role in the classical zero-knowledge proof. Specifically, Shor's factoring-based scheme and the learning with errors-based scheme in [Brakerski et al., FOCS, 2018] can be transformed into zero-knowledge proofs of quantumness by requiring an extractable non-interactive zero-knowledge argument on the verifier side. Zero-knowledge proofs of quantumness can thus be viewed as an enhanced security notion for proofs of quantumness.
Proofs of quantumness usually protect against classical provers impersonating quantum devices, but need not protect quantum provers against malicious verifiers. For example, a verifier could submit an RSA modulus as a factoring challenge and obtain its factors. This paper defines zero-knowledge proofs of quantumness (ZKPoQ), requiring quantum completeness, classical soundness, and classical polynomial-time simulation of a malicious classical verifier’s view.
Two constructions modify factoring-based proofs of quantumness and the LWE-based trapdoor-claw-free-function protocol of Brakerski et al. The verifier supplies an extractable noninteractive zero-knowledge argument demonstrating knowledge of the challenge’s factorization or LWE secret. The quantum prover checks this argument before continuing. For zero knowledge, a classical simulator generates a reference string with an extraction trapdoor, extracts the verifier’s witness, and uses it to simulate the quantum prover’s responses. Classical soundness is established by replacing the verifier’s argument with a simulated argument and reducing to the original protocol’s soundness. The claimed guarantees are acceptance probability 1−negl(λ) for honest quantum provers, negligible acceptance for classical provers, and computational zero knowledge; the LWE construction uses λ repetitions.
The constructions require a common reference string and existing extractable-NIZK machinery. Classically secure arguments suffice for the stated PoQ guarantees; post-quantum security is discussed for possible extensions such as randomness certification and key leasing. No generic transformation is established: applicability to other LWE protocols and sampling-based demonstrations remains open, as does a formal plain-model replacement using interactive zero-knowledge proofs.
In a proof of knowledge (PoK), a verifier becomes convinced that a prover possesses privileged information. In combination with zero-knowledge proof systems, PoKs play an important role in security protocols such as in digital signatures and authentication schemes, as they enable a prover to demonstrate possession of certain information (such as a private key or a credential), without revealing it. A PoK is formally defined via the existence of an extractor, which is capable of reconstructing the key information that makes a verifier accept, given oracle access to any accepting prover. We extend this concept to the setting of a single classical verifier and multiple quantum provers and present the first statistical zero-knowledge (ZK) PoK proof system for problems in QMA. To achieve this, we establish the PoK property for the ZK protocol of Broadbent, Mehta, and Zhao (TQC 2024), which applies to the local Hamiltonian problem. More specifically, we construct an extractor which, given oracle access to a provers' strategy that leads to high acceptance probability, is able to reconstruct the ground state of a local Hamiltonian. Our result can be seen as a new form of self-testing, where, in addition to certifying a pre-shared entangled state, the verifier also certifies that provers have access to a quantum system, in particular, a ground state; this indicates a new level of verification for a proof of quantumness.
This work presents a new scheme based on a quantum zero-knowledge proof for identity authentication. The novelty of this research is the migration of the classical concept Zero-knowledge into the quantum cryptographic framework that, to the best of our knowledge, has never been explored. This approach allows us to take advantage of the principles of quantum mechanics to build a protocol, which is secure against quantum computer attacks, for authenticating several users having access to the same network node. The protocol has been designed, its security analysed and implemented in modified Quantum Key Distribution devices. Two scenarios have been analysed experimentally, the first being both the prover and the verifier honest players, and the second case being the prover a malicious player, the latter demonstrating a notable increase in the quantum bit error rate that prevents a fraudulent authentication.
We show that every language in QMA admits a classical-verifier, quantum-prover zero-knowledge argument system which is sound against quantum polynomial-time provers and zero-knowledge for classical (and quantum) polynomial-time verifiers. The protocol builds upon two recent results: a computational zero-knowledge proof system for languages in QMA, with a quantum verifier, introduced by Broadbent et al. (FOCS 2016), and an argument system for languages in QMA, with a classical verifier, introduced by Mahadev (FOCS 2018).
Prior work has established that all problems in NP admit classical zero-knowledge proof systems, and under reasonable hardness assumptions for quantum computations, these proof systems can be made secure against quantum attacks. We prove a result representing a further quantum generalization of this fact, which is that every problem in the complexity class QMA has a quantum zero-knowledge proof system. More specifically, assuming the existence of an unconditionally binding and quantum computationally concealing commitment scheme, we prove that every problem in the complexity class QMA has a quantum interactive proof system that is zero-knowledge with respect to efficient quantum computations. Our QMA proof system is sound against arbitrary quantum provers, but only requires an honest prover to perform polynomial-time quantum computations, provided that it holds a quantum witness for a given instance of the QMA problem under consideration.
A Zero-Knowledge Proof basically is a protocol between two parties, the Prover and the Verifier, that allows the Prover to convince the Verifier about the truthness of a non trivial statement without revealing any additional information. Zero Knowledge Proofs have found a lot of practical applications covering most of the protocols concerning about data privacy and protocol verification. Examples of that are anonymous cash or electronic voting. The possibility to have real quantum computers with a reasonable size in a near future is forcing the cryptographic community to devise new methods to provide security that resist quantum attacks. Most of the zero-knowledge protocols used nowadays are based on computational problems like the discrete logarithm problem that can no longer be considered hard, since there are known efficient ways to solve them with quantum algorithms. Cryptographic research about the quantum security of zero knowledge proofs started nearly 20 years ago in a very theoretical approach, but not many papers on that topic appeared since then. The goal of this thesis is writing a survey including the main concepts about quantum secure zero-knowledge protocols, the state-of-the-art both from the theoretical and practical approaches, and an exploration of their potential application areas. The survey will be a good starting document for further students willing to do research in this topic.
The concept of zero-knowledge (ZK) has become of fundamental importance in cryptography. However, in a setting where entities are modeled by quantum computers, classical arguments for proving ZK fail to hold since, in the quantum setting, the concept of rewinding is not generally applicable. Moreover, known classical techniques that avoid rewinding have various shortcomings in the quantum setting. We propose new techniques for building quantum zero-knowledge (QZK) protocols, which remain secure even under (active) quantum attacks. We obtain computational QZK proofs and perfect QZK arguments for any NP language in the common reference string model. This is based on a general method converting an important class of classical honest-verifier ZK (HVZK) proofs into QZK proofs. This leads to quite practical protocols if the underlying HVZK proof is efficient. These are the first proof protocols enjoying these properties, in particular the first to achieve perfect QZK. As part of our construction, we propose a general framework for building unconditionally hiding (trapdoor) string commitment schemes, secure against quantum attacks, as well as concrete instantiations based on specific (believed to be) hard problems. This is of independent interest, as these are the first unconditionally hiding string commitment schemes withstanding quantum attacks. Finally, we give a partial answer to the question whether QZK is possible in the plain model. We propose a new notion of QZK, non-oblivious verifier QZK, which is strictly stronger than honest-verifier QZK but weaker than full QZK, and we show that this notion can be achieved by means of efficient (quantum) protocols.