⚛️ quantum physics

Zero-Knowledge Proofs of Quantumness

This paper introduces the concept of zero-knowledge proofs of quantumness to prevent malicious classical verifiers from exploiting quantum provers by formalizing a security notion that restricts information leakage and demonstrates how existing quantumness schemes can be transformed into zero-knowledge variants using extractable non-interactive arguments.

Original authors: Duong Hieu Phan, Weiqiang Wen, Xingyu Yan, Jinwei Zheng

Published 2026-09-22

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Duong Hieu Phan, Weiqiang Wen, Xingyu Yan, Jinwei Zheng

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the coming decades, the world of computing is poised for a fundamental shift. For decades, the most powerful computers have been classical machines, processing information in a linear fashion of ones and zeros. Now, a new generation of devices, known as quantum computers, is emerging. These machines operate on the strange laws of quantum physics, allowing them to solve certain problems with a speed that classical computers simply cannot match. As these devices move from theory to reality, a critical question arises: how can a person with a standard computer be certain that a remote device is truly quantum and not just a clever imitation? This is the challenge of "proofs of quantumness." It is a digital handshake where a quantum machine must prove its unique capabilities to a classical observer. However, this interaction carries a hidden risk. Just as a person might try to trick a bank teller to withdraw money they don't own, a dishonest observer could potentially trick a quantum machine into solving difficult problems for them, effectively stealing its computational power without paying for it.

A team of researchers has now addressed this vulnerability by introducing a new layer of security called "zero-knowledge proofs of quantumness." In their work, they formalize a method where a quantum device can prove it is quantum without revealing any extra information that a dishonest observer could exploit. The researchers demonstrate that in current systems, a malicious observer could manipulate the interaction to extract useful data, such as the factors of a large number or the solution to a complex mathematical puzzle, simply by posing as a standard verifier. The new framework prevents this by ensuring that the information gained by the observer is no more than what could be generated by a standard, non-quantum computer. This means the quantum device's unique power remains protected, and the observer cannot use the interaction to gain an unfair advantage.

The researchers focused on two of the most prominent methods used to prove quantumness today. The first relies on the difficulty of factoring large numbers, a task that is easy for quantum computers but hard for classical ones. The second is based on a mathematical problem involving errors in data, known as learning with errors. In both cases, the researchers found a way to upgrade the existing protocols. They did this by requiring the observer, the classical verifier, to provide a special kind of digital certificate before the interaction begins. This certificate proves that the observer is not attempting to act dishonestly or extract hidden secrets. It acts as a guarantee that the observer is behaving honestly, or at least not maliciously. If the observer tries to use a fake or manipulated number to trick the quantum machine, they cannot produce this certificate without knowing the secret solution themselves, which defeats the purpose of the trick.

To make this work, the researchers combined the quantum proof with a classical security tool known as an extractable non-interactive zero-knowledge argument. This tool allows the system to verify that the observer possesses the necessary secret knowledge to generate the certificate, without the observer ever having to reveal that knowledge. If the observer is honest, the certificate is valid, and the quantum proof proceeds. If the observer is malicious and tries to use a fake number, they cannot generate a valid certificate, and the interaction fails. This creates a system where the quantum device is safe from exploitation. The researchers showed that this approach works for both the factoring-based method and the learning-with-errors method. They proved that a classical computer simulating the interaction could produce the exact same results as the quantum computer, meaning no extra information leaked out.

The significance of this work lies in its ability to protect the interests of the quantum device owner. In a future where quantum computers are offered as a service, users might want to verify that the server is truly quantum before paying for a task. Without this new security layer, a dishonest user could potentially trick the server into solving a difficult problem for free, or worse, extract the solution to a problem the user was supposed to solve themselves. By implementing zero-knowledge proofs of quantumness, the researchers ensure that the verification process itself does not become a loophole for theft. The quantum server can demonstrate its power without giving away any of its secrets or computational edge.

The study also highlights a subtle but important shift in how these interactions are viewed. Traditionally, security in these proofs focused on ensuring the quantum machine was not lying. This new approach flips the script, focusing on ensuring the observer is not lying. It treats the observer as the party that needs to be constrained, requiring them to prove they are not acting maliciously. This dual role, where both the prover and the verifier play parts in a classical security check alongside the quantum test, creates a more robust system. The researchers found that for the factoring method, the observer must prove they know the factors of a number. For the learning-with-errors method, they must prove they know the secret key associated with the data. In both instances, the requirement for this proof stops the observer from using the quantum machine as a tool to solve their own hard problems.

While the researchers successfully transformed these two specific schemes, they acknowledge that not every method of proving quantumness can be easily upgraded in this way. Some existing methods rely on different assumptions or do not fit the standard challenge-and-response format used in their work. For example, methods based on sampling random patterns are harder to adapt because they do not follow the same interactive structure. The researchers suggest that while their approach is powerful for the most common schemes, finding a universal solution for all types of quantum proofs remains an open question. They also note that for the system to be fully secure against future quantum computers, the underlying classical tools used for the certificates must themselves be resistant to quantum attacks. They point to existing mathematical constructions that can provide this level of security.

Ultimately, this work provides a blueprint for a safer future in quantum verification. It moves the field from a simple test of capability to a secure, trustless interaction where the quantum device's power is respected. By formalizing the concept of zero-knowledge in this context, the researchers have shown that it is possible to verify quantumness without compromising the integrity of the quantum machine. This is a crucial step toward the practical deployment of quantum services, ensuring that the transition to the quantum age is built on a foundation of security and trust. The result is a system where the unique power of quantum computing can be demonstrated and utilized without the fear of being exploited by those who seek to steal its secrets.

=== SUMMARY ===

Technical Summary: Zero-Knowledge Proofs of Quantumness

Problem Statement

Proofs of Quantumness (PoQ) are cryptographic protocols designed to allow a quantum prover to convince a classical verifier of its quantum computational capabilities. While existing PoQ schemes (e.g., based on factoring or Learning With Errors) address the risk of a classical prover masquerading as a quantum device (soundness), they lack formal protections against malicious classical verifiers.

In current schemes, a malicious verifier ( $V^*$ ) can potentially exploit the interaction to extract useful information or solve hard problems without paying the computational cost. For instance:

In factoring-based schemes, a malicious verifier can substitute the challenge integer $N$ with a specific composite number $N^*$ (e.g., from an RSA public key) to force the quantum prover to factor it, effectively outsourcing a hard computational task.
In LWE-based schemes (e.g., [BCM+18]), while the verifier cannot necessarily solve the LWE instance directly, the transcripts generated by the quantum prover contain information that a classical prover could not possess. A malicious verifier could potentially leverage this interaction to gain advantages beyond merely verifying quantumness.

The core problem is the absence of a formalization that prevents a verifier from extracting useful information during the proof process. The paper asks: Is there a "zero-knowledge" proof of quantumness that allows a prover to demonstrate quantum capability without revealing any other useful information?

Methodology

The authors propose Zero-Knowledge Proofs of Quantumness (ZKPoQ). The central intuition is that the information gained by a classical verifier from interacting with a quantum prover should not exceed what could be simulated by a simulated classical prover interacting with the same verifier.

Key Technical Approach: Verifier-Side Zero-Knowledge

The paper argues that requiring the prover to generate a zero-knowledge proof is often infeasible. In LWE-based schemes, the verifier challenges the prover with a statement (e.g., a witness to a specific equation) that only the verifier knows. A prover cannot generate a zero-knowledge proof for a statement it does not know.

Instead, the authors propose a dual-role framework where the verifier must provide a zero-knowledge proof to claim it is not behaving maliciously. Specifically:

Extractable Non-Interactive Zero-Knowledge (NIZK): The verifier must submit an extractable NIZK proof attesting to the validity of the secret parameters used in the PoQ challenge (e.g., the factorization of $N$ or the LWE secret $s$ ).
Simulation via Extraction: A simulator (for the zero-knowledge property) can extract the secret witness from the verifier's NIZK proof. With this witness, the simulator can perfectly reproduce the interaction transcripts without needing a quantum device.
Soundness Preservation: To prevent a classical prover from using the extracted secret to pass verification, the NIZK proof itself must be zero-knowledge. This ensures a malicious classical prover cannot learn the secret from the proof and must solve the underlying hard problem (factoring or LWE) independently to pass verification.

Key Contributions

1. Formal Definition of ZKPoQ

The paper defines ZKPoQ as a Quantum-Prover Interactive Proof (QPIP) system satisfying three properties:

Quantum Completeness: An honest quantum prover is accepted with high probability.
Classical Soundness: No classical prover can pass verification with non-negligible probability.
Computational Zero-Knowledge: For any PPT verifier $V^*$ , there exists a PPT simulator $Sim_{V^*}$ such that the view of $V^*$ interacting with the quantum prover is computationally indistinguishable from the view of $V^*$ interacting with the simulator.

2. Transformation of Factoring-Based PoQ

The authors demonstrate how to transform Shor's factoring-based PoQ into a ZKPoQ scheme (Figure 7):

The verifier generates $N = p \cdot q$ and provides an extractable NIZK proof of the factorization $(p, q)$ .
The quantum prover verifies this proof before proceeding.
Security: The zero-knowledge property relies on the extractability of the NIZK (allowing the simulator to get $p, q$ ). The soundness relies on the zero-knowledge property of the NIZK (preventing a classical prover from learning $p, q$ from the proof).

3. Transformation of LWE-Based PoQ

The authors transform the [BCM+18] LWE-based PoQ scheme into a ZKPoQ scheme (Figure 8):

The verifier generates an NTCF key $k$ and the corresponding trapdoor $t_k$ .
The verifier provides an extractable NIZK proof of the LWE secret $s$ associated with $k$ .
Security: Similar to the factoring case, the simulator extracts $s$ to simulate the protocol. The soundness is maintained because the zero-knowledge property of the NIZK prevents a classical prover from learning $s$ to pass verification.

4. Feasibility and Assumptions

The transformations rely on the existence of extractable NIZK proofs for NP in the Common Reference String (CRS) model.
The paper notes that classically secure extractable NIZK is sufficient for the ZKPoQ schemes themselves. However, for applications like certifiable randomness or key leasing where the quantum prover itself might be malicious, post-quantum secure extractable NIZK (based on LWE) is required.

Results

The paper establishes two main theorems:

Theorem 1: Given an extractable NIZK, the factoring-based PoQ scheme can be transformed into a ZKPoQ scheme.
Theorem 2: Given an extractable NIZK, the LWE-based PoQ scheme [BCM+18] can be transformed into a ZKPoQ scheme.

The authors prove that these transformed schemes satisfy quantum completeness, classical soundness, and computational zero-knowledge. They explicitly show that the zero-knowledge property prevents malicious verifiers from exploiting the quantum device to solve hard problems (like factoring specific integers or solving LWE instances) that they could not solve on their own.

Significance and Claims

The paper positions ZKPoQ as an enhanced security notion for proofs of quantumness.

Regulating Verifier Behavior: The framework effectively regulates the verifier's behavior from "malicious" to "honest-but-curious," ensuring that the quantum device's computational power is not swindled during verification.
Practical Relevance: In the post-quantum era, where classical users may subscribe to quantum services, ZKPoQ ensures that the verification process does not leak the quantum server's capabilities or secrets.
Limitations and Open Problems: The authors acknowledge that their generic transformation using extractable NIZK applies specifically to challenge-response protocols (Factoring and LWE). They note that it is unclear if this approach applies to other LWE-based protocols with different assumptions (e.g., random oracles) or to non-interactive schemes like Boson Sampling, which lack efficient classical verification. They also identify the removal of the CRS model (moving to the plain model) as a future research direction.

In summary, the paper provides the first formalization of zero-knowledge in the context of proofs of quantumness and offers a concrete, provably secure method to upgrade existing PoQ schemes to protect against malicious verifiers.