Zero-Knowledge Proofs of Quantumness

AI summary

Overview

Research area: Quantum cryptography — specifically proofs of quantumness (PoQ), the cryptographic protocols that let a quantum device convince a classical verifier of its quantum capability. This paper sits at the intersection of quantum computing, zero-knowledge proof systems, and post-quantum security.

Technical level: Advanced. The paper assumes familiarity with interactive proof systems, the common reference string (CRS) model, non-interactive zero-knowledge (NIZK) arguments, learning with errors (LWE), and trapdoor claw-free functions.

Scope (one sentence): The paper formalizes a zero-knowledge notion for proofs of quantumness and shows how two existing schemes — Shor's factoring-based scheme and the LWE-based scheme of Brakerski et al. (FOCS 2018) — can be compiled into zero-knowledge proofs of quantumness by requiring an extractable NIZK argument on the verifier's side.

What This Paper Is About

Existing proofs of quantumness protect the classical verifier from a cheating classical prover, but say nothing about protecting the quantum prover from a cheating classical verifier. In the factoring-based scheme, a malicious verifier can simply hand the quantum device an integer of its own choosing (for example one taken from an RSA public key) and have the device factor it, extracting useful work for free. The paper's goal is to define — and then achieve — a "zero-knowledge" variant of proofs of quantumness in which the verifier learns nothing beyond the fact that the prover is quantum.

Key Contributions

1. A formal definition of zero-knowledge proofs of quantumness (ZKPoQ). Definition 1.1 requires three properties: quantum completeness, classical soundness, and computational zero-knowledge. The zero-knowledge condition is that whatever a classical verifier gains from interacting with the quantum prover must be simulable by a polynomial-time probabilistic classical prover interacting with the same verifier — so the verifier cannot harvest quantum advantage through the protocol.

2. An argument that putting the zero-knowledge proof on the prover's side does not work in general. The authors explain that a prover-side ZK proof happens to work for the factoring scheme (the prover can prove knowledge of the factorization (p, q) of N), but fails for the LWE-based scheme of Brakerski et al., because there the verifier challenges the prover with a statement the prover does not know. In the equation test, the prover must supply a witness σ₁ = (c, d) ∈ {0,1} × {0,1}ⁿ for the statement c = dᵀ · (x₀ ⊕ x₁) mod 2, where x₀ and x₁ are the two preimages of the same output y under a claw-free function — and by claw-freeness even a quantum prover cannot obtain both preimages, hence cannot know the statement.

3. A verifier-side transformation using extractable NIZK. The paper's technical core is to require the verifier to submit an extractable non-interactive zero-knowledge argument: a proof of the factorization (p, q) of N in the factoring scheme (Theorem 1.2), and a proof of the LWE instance's secret in the LWE-based scheme (Theorem 1.3). The NIZK must be zero-knowledge as well as extractable, so that soundness of the underlying PoQ is preserved.

4. A discussion of what security level the NIZK needs, and of why the transformation is not generic. The authors argue a classically secure extractable NIZK suffices for the ZKPoQ constructions themselves, while post-quantum security (available from LWE via Theorem 2.5, citing [12, Corollary 4.4]) becomes necessary if the scheme is reused for certifiable randomness or key leasing. They also set out why no general transformation is currently known.

Main Findings

• The factoring attack is concrete and simple. In the factoring-based PoQ scheme, a malicious verifier 𝒱* can replace the large integer N with a carefully chosen N* (e.g., taken from an RSA public key) and thereby exploit the prover's quantum factoring capability for its own benefit.

• The LWE case is subtler but still leaks. In the LWE-based scheme of [6], assuming post-quantum hardness of LWE, the classical verifier should not gain much advantage on the LWE instance itself. However, the transcripts from the quantum prover contain more information than any classical prover could possess — which is exactly what lets the verifier distinguish a quantum from a classical prover. So the verifier cannot be prevented from obtaining information beyond mere conviction of the prover's quantumness.

• Both parties end up playing dual roles. Because the zero-knowledge requirement is placed on the verifier side, each party plays its PoQ role plus the complementary role in the added classical zero-knowledge proof. Intuitively this moves the verifier from malicious to honest-but-curious.

• Extractability gives zero-knowledge; zero-knowledge preserves soundness. For ZK, the simulator extracts the witness — the factorization (p, q), or the LWE secret — from the verifier's extractable-NIZK proof and then perfectly simulates the prover's transcripts. For soundness, the added proof must itself be zero-knowledge, otherwise any classical prover could use the extracted knowledge to fake the transcript without any quantum resource. The authors note such proofs can be constructed from one-way functions and public-key encryption [12]. This is stated as a joint satisfaction of zero-knowledge and soundness.

• Extractability blocks the malicious verifier. Since a valid extractable-NIZK proof cannot be produced without knowing the factorization, a cheating verifier in the factoring setting is effectively forced to know (p, q), which removes the attack of Figure 1.

• Classical-grade NIZK is enough for the transformation; post-quantum NIZK is needed for reuse. For certifiable randomness from a quantum device [6] or key leasing [10], a post-quantum secure extractable NIZK appears necessary, so that even the quantum prover gains no extra advantage from it; Theorem 2.5 gives such a construction from LWE.

• No generic transformation is available yet. Other LWE-based protocols add assumptions — the scheme in [8] requires a random oracle, and those in [13, 7] assume Bell's inequality — so it is unclear whether the verifier-side extractable-NIZK idea carries over. Sampling-based schemes (boson sampling [1, 9], random circuit sampling [4, 19]) are non-interactive and not efficiently classically verifiable, and fall outside the framework studied here. The paper focuses its formalization on classically verifiable PoQ, particularly factoring-based and LWE-based.

• No experimental data. The paper is entirely theoretical: it reports no implementations, benchmarks, dataset sizes, or runtimes. The only quantitative parameter appearing in the formal statements is the security parameter λ, and completeness/soundness/zero-knowledge errors are stated as negligible in λ (e.g., the honest factoring prover is accepted with probability 1 − negl(λ)).

Methodology in Plain English

The authors proceed in three steps. First, they define what "zero-knowledge" should mean for a proof of quantumness: whatever a classical verifier can learn from talking to the quantum device must be reproducible by a fake, purely classical prover talking to the same verifier. This is the same simulation-based idea used in classical zero-knowledge, but the simulated party is classical rather than quantum, which is precisely what blocks the verifier from extracting quantum advantage.

Second, they check whether the natural fix — have the quantum prover prove its answers in zero-knowledge — works. It does for factoring, but not for the LWE-based scheme, where the prover is challenged on a statement only the verifier knows. So they flip the direction: require the verifier to prove, in an extractable NIZK, that it knows the secret underlying the instance it handed over (the factorization of N, or the LWE secret).

Third, they verify that this flip does not destroy the protocol. Adding an extractable proof on the verifier's side would let a classical prover extract the secret and fake everything, so they also demand that the proof be zero-knowledge — hiding the secret from any classical prover — while remaining extractable for the simulator. The two requirements pull in opposite directions but can be met simultaneously, and the authors argue this for both the factoring-based scheme (Figure 3) and the LWE-based scheme (Figure 4).

Why This Matters

Proofs of quantumness are being positioned as the first step in a commercial relationship: a classical user subscribes to a quantum cloud service and must first verify that the server really is quantum. Without a zero-knowledge guarantee, that same verification handshake is an opportunity for the client to siphon off the server's quantum capability — the paper's motivating example being a client who submits its own RSA modulus and walks away with the factorization. ZKPoQ gives the quantum server a formal guarantee that the act of proving its quantumness reveals nothing else.

Real-world applications implied by the paper:

• Quantum cloud service onboarding: a classical customer verifies a quantum server's quantumness without being able to redirect that power to its own cryptographic targets.
• Certifiable randomness from quantum devices: cited as a use case where a post-quantum secure extractable NIZK would be required.
• Key leasing: also cited as a use case motivating post-quantum secure extractable NIZKs, so the quantum prover gains no extra advantage from the added proof.
• Delegated factoring and LWE-based cryptographic services: the two concrete attack surfaces the paper analyzes are exactly the settings where a client might try to outsource hard-instance solving under the guise of testing.

Industry relevance: the work matters to operators of quantum hardware and quantum-cloud platforms who need contractual-grade security arguments before exposing their devices to untrusted clients, and to cryptography groups tracking how post-quantum primitives (LWE-based NIZKs, trapdoor claw-free functions) compose with quantum protocols.

Future Directions

• A general transformation framework. The authors explicitly ask whether one can formalize the characteristics a PoQ scheme must have for the extractable-NIZK upgrade to apply, noting that sampling-based schemes do not fit the cryptographic interactive framework and lack efficient classical verification.

• Extending to other LWE-based protocols. Protocols in [8, 2, 13, 14, 3, 7] rely on differing heuristic assumptions (random oracles, Bell's inequality), so applying the approach is non-trivial; the authors propose looking for common characteristics that would enable it.

• Removing the CRS. The current constructions use post-quantum NIZK in the CRS model to minimize interaction. The open question is whether interactive zero-knowledge proofs [11, 5] can replace the NIZKs and yield a plain-model solution.

• Choosing the right NIZK strength per application. Determining when classically secure extractable NIZK suffices versus when post-quantum security is required (as suggested for certifiable randomness and key leasing) is left as guidance rather than a settled criterion.

Target Audience

Cryptography researchers and graduate students working on quantum protocols, proof systems, and post-quantum security will get the most from this paper, as will quantum-hardware and quantum-cloud operators who need to reason about what an untrusted classical client can extract during a verification protocol. Readers without a background in zero-knowledge arguments and LWE-based cryptography will find the technical sections demanding, though the introduction's attack scenarios are accessible to a general computer-science audience.

Authors’ abstract

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.