arXiv:1911.07546

Non-interactive zero-knowledge arguments for QMA, with preprocessing

Andrea Coladangelo, Thomas Vidick, Tina Zhang

Published Nov 18, 2019• 5 citations

Abstract

We initiate the study of non-interactive zero-knowledge (NIZK) arguments for languages in QMA. Our first main result is the following: if Learning With Errors (LWE) is hard for quantum computers, then any language in QMA has an NIZK argument with preprocessing. The preprocessing in our argument system consists of (i) the generation of a CRS and (ii) a single (instance-independent) quantum message from verifier to prover. The instance-dependent phase of our argument system involves only a single classical message from prover to verifier. Importantly, verification in our protocol is entirely classical, and the verifier needs not have quantum memory; its only quantum actions are in the preprocessing phase. Our second contribution is to extend the notion of a classical proof of knowledge to the quantum setting. We introduce the notions of arguments and proofs of quantum knowledge (AoQK/PoQK), and we show that our non-interactive argument system satisfies the definition of an AoQK. In particular, we explicitly construct an extractor which can recover a quantum witness from any prover which is successful in our protocol. Finally, we show that any language in QMA has an (interactive) proof of quantum knowledge.

DOI: 10.48550/arxiv.1911.07546

Related papers

Classically Verifiable (Dual-Mode) NIZK for QMA with Preprocessing.

Tomoyuki Morimae, Takashi Yamakawa

We propose three constructions of classically verifiable non-interactive proofs (CV-NIP) and non-interactive zero-knowledge proofs and arguments (CV-NIZK) for QMA in various preprocessing models. - We construct an information theoretically sound CV-NIP for QMA in the secret parameter model where a trusted party generates a quantum proving key and classical verification key and gives them to the corresponding parties while keeping it secret from the other party. Alternatively, we can think of the protocol as one in a model where the verifier sends an instance-independent quantum message to the prover as preprocessing. - We construct a CV-NIZK for QMA in the secret parameter model. It is information theoretically sound and zero-knowledge. - Assuming the quantum hardness of the leaning with errors problem, we construct a CV-NIZK for QMA in a model where a trusted party generates a CRS and the verifier sends an instance-independent quantum message to the prover as preprocessing. This model is the same as one considered in the recent work by Coladangelo, Vidick, and Zhang (CRYPTO '20). Our construction has the so-called dual-mode property, which means that there are two computationally indistinguishable modes of generating CRS, and we have information theoretical soundness in one mode and information theoretical zero-knowledge property in the other. This answers an open problem left by Coladangelo et al, which is to achieve either of soundness or zero-knowledge information theoretically. To the best of our knowledge, ours is the first dual-mode NIZK for QMA in any kind of model.

Feb 18, 20212 citations

Certified-Everlasting Quantum NIZK Proofs

Nikhil Pappu

We study non-interactive zero-knowledge proofs (NIZKs) for NP satisfying: 1) statistical soundness, 2) computational zero-knowledge (ZK) and 3) certified-everlasting zero-knowledge (CE-ZK). The CE-ZK property allows a verifier of a quantum proof to revoke the proof in a way that can be checked (certified) by the prover. Conditioned on successful certification, the verifier's state can be efficiently simulated with only the statement, in a statistically indistinguishable way. Our contributions regarding these certified-everlasting NIZKs (CE-NIZKs) are as follows: - We identify a barrier to obtaining CE-NIZKs in the CRS model via generalizations of known interactive ZK proofs that satisfy CE-ZK. - We circumvent this by constructing CE-NIZK using non-black-box use of NIZK for NP satisfying certain properties, along with OWFs. As a result, we obtain CE-NIZKs for NP in the CRS model, based on polynomial hardness of the learning with errors (LWE) assumption. - In addition, we observe that the aforementioned barrier does not apply to the shared EPR model. We leverage this to construct CE-NIZK for NP in this model based on any statistical binding hidden bits generator, which is known from LWE. The only quantum computation here involves single-qubit measurements of the EPR pairs.

quant-pharXiv:2512.13628Dec 16, 20250 citations

How to Classically Verify a Quantum Cat without Killing It

Yael Tauman Kalai, Dakshita Khurana, Justin Raizes

A quantum verifier decides membership in QMA using a (single) quantum witness state. This witness may be arbitrary, and no requirement is placed on it beyond its acceptance probability. A protocol claiming to classically verify QMA should offer the same guarantee: any witness that would convince a quantum verifier should also suffice to convince a classical verifier. Unfortunately, existing classical verification of quantum computation (CVQC) protocols behave quite differently from the original QMA verifier: they require many copies of the witness and destroy every one, effectively demanding that the prover solve the hard problem of witness duplication before verification can begin. We build a protocol to classically verify QMA languages that uses a single copy of the prover's QMA witness. Whenever the original QMA verifier accepts that witness with overwhelming probability, our protocol has negligible completeness and soundness errors and returns the witness negligibly disturbed after interaction with an honest verifier. The soundness of our CVQC is based on the post-quantum Learning With Errors (LWE) assumption. As an intermediate step of independent interest, we introduce witness-preserving classical arguments for NP which enable provers that start out with a superposition over NP witnesses to convince a verifier without disturbing their superposition.

quant-pharXiv:2602.09282Feb 11, 20260 citations

Classical zero-knowledge arguments for quantum computations

Thomas Vidick, Tina Zhang

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).

arXiv:1902.05217QuantumMay 14, 202020 citations

Zero-Knowledge Proofs of Quantumness

Duong Hieu Phan, Weiqiang Wen, Xingyu Yan +1 more

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.

quant-pharXiv:2609.23455IACR Communications in CryptologySep 22, 20260 citations

Multi-theorem (Malicious) Designated-Verifier NIZK for QMA

Omri Shmueli

We present the first non-interactive zero-knowledge argument system for QMA with multi-theorem security. Our protocol setup constitutes an additional improvement and is constructed in the malicious designated-verifier (MDV-NIZK) model (Quach, Rothblum, and Wichs, EUROCRYPT 2019), where the setup consists of a trusted part that includes only a common uniformly random string and an untrusted part of classical public and secret verification keys, which even if sampled maliciously by the verifier, the zero knowledge property still holds. The security of our protocol is established under the Learning with Errors Assumption. Our main technical contribution is showing a general transformation that compiles any sigma protocol into a reusable MDV-NIZK protocol, using NIZK for NP. Our technique is classical but works for quantum protocols and allows the construction of a reusable MDV-NIZK for QMA.

arXiv:2007.12923Jul 25, 20206 citations