Classical Proofs of Quantum Knowledge

被引:9
作者
Vidick, Thomas [1 ]
Zhang, Tina [2 ]
机构
[1] CALTECH, Dept Comp & Math Sci, Pasadena, CA 91125 USA
[2] CALTECH, Div Phys Math & Astron, Pasadena, CA 91125 USA
来源
ADVANCES IN CRYPTOLOGY - EUROCRYPT 2021, PT II | 2021年 / 12697卷
关键词
D O I
10.1007/978-3-030-77886-6_22
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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 non-destructive 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.
引用
收藏
页码:630 / 660
页数:31
相关论文
共 28 条
[1]  
Aaronson S, 2012, STOC'12: PROCEEDINGS OF THE 2012 ACM SYMPOSIUM ON THEORY OF COMPUTING, P41
[2]   Quantum Money [J].
Aaronson, Scott ;
Farhi, Edward ;
Gosset, David ;
Hassidim, Avinatan ;
Kelner, Jonathan ;
Lutomirski, Andrew .
COMMUNICATIONS OF THE ACM, 2012, 55 (08) :84-92
[3]  
Badertscher C., 2019, IACR CRYPTOL EPRINT
[4]  
Badertscher C, 2020, Arxiv, DOI arXiv:2007.01668
[5]  
Bellare M., 1993, Advances in Cryptology - CRYPTO '92. 12th Annual International Cryptology Conference Proceedings, P390
[6]  
Ben-David S, 2017, Arxiv, DOI [arXiv:1609.09047, 10.48550/ARXIV.1609.09047]
[7]  
Broadbent A, 2021, Arxiv, DOI arXiv:1911.07782
[8]  
Chase M, 2006, LECT NOTES COMPUT SC, V4117, P78
[9]  
Coladangelo A, 2020, Arxiv, DOI [arXiv:1911.07546, 10.1007/978-3-030-56877-1.28]
[10]  
Feige U., 1988, Journal of Cryptology, V1, P77, DOI 10.1007/BF02351717