A Caltech Library Service

Classical Proofs of Quantum Knowledge

Vidick, Thomas and Zhang, Tina (2021) Classical Proofs of Quantum Knowledge. In: Advances in Cryptology – EUROCRYPT 2021. Lecture Notes in Computer Science. Vol.12697. No.12697. Springer , Cham, pp. 630-660. ISBN 9783030778859.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We define the notion of a proof of knowledge in the setting where the verifier is classical, but the prover is quantum, and where the witness that the prover holds is in general a quantum state. We establish simple properties of our definition, including that, if a nondestructive classical proof of quantum knowledge exists for some state, then that state can be cloned by an unbounded adversary, and that, under certain conditions on the parameters in our definition, a proof of knowledge protocol for a hard-to-clone state can be used as a (destructive) quantum money verification protocol. In addition, we provide two examples of protocols (both inspired by private-key classical verification protocols for quantum money schemes) which we can show to be proofs of quantum knowledge under our definition. In so doing, we introduce techniques for the analysis of such protocols which build on results from the literature on nonlocal games. Finally, we show that, under our definition, the verification protocol introduced by Mahadev (FOCS 2018) is a classical argument of quantum knowledge for QMA relations. In all cases, we construct an explicit quantum extractor that is able to produce a quantum witness given black-box quantum (rewinding) access to the prover, the latter of which includes the ability to coherently execute the prover’s black-box circuit controlled on a superposition of messages from the verifier.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Chapter ReadCube Link ItemarXiv preprint
Vidick, Thomas0000-0002-6405-365X
Additional Information:We thank Alexandru Gheorghiu for useful feedback and Or Sattath for comments. Thomas Vidick is supported by NSF CAREER Grant CCF-1553477, AFOSR YIP award number FA9550-16-1-0495, MURI Grant FA9550-18-1-0161 and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). This material is based upon work supported by DARPA under Agreement No. HR00112020023. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0161
Gordon and Betty Moore FoundationGBMF-12500028
Defense Advanced Research Projects Agency (DARPA)HR00112020023
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Series Name:Lecture Notes in Computer Science
Issue or Number:12697
Record Number:CaltechAUTHORS:20221011-458984000.5
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:117322
Deposited By: Donna Wrublewski
Deposited On:12 Oct 2022 19:50
Last Modified:12 Oct 2022 19:50

Repository Staff Only: item control page