Cryptology ePrint Archive: Report 2010/212
Quantum Proofs of Knowledge
Abstract: We motivate, define and construct quantum proofs of knowledge, that
is, proofs of knowledge secure against quantum adversaries. Our
constructions are based on a new quantum rewinding technique that
allows us to extract witnesses in many classical proofs of
knowledge. We give criteria under which a classical proof of knowledge
is a quantum proof of knowledge. Combining our results with Watrous'
results on quantum zero-knowledge, we show that there are
zero-knowledge quantum proofs of knowledge for all languages in NP
(assuming quantum 1-1 one-way functions).
Category / Keywords: foundations / Quantum cryptography, proofs of knowledge
Original Publication (with major differences): IACR-EUROCRYPT-2012
Date: received 15 Apr 2010, last revised 11 Feb 2015
Contact author: unruh at ut ee
Available format(s): PDF | BibTeX Citation
Note: Definitions now include a security parameter, definition of quantum arguments of knowledge added, section on zero-knowledge added, improved bound for sigma-protocols with two challenges, candidates for quantum 1-1 one-way functions, various updates of the discussions.
Version: 20150211:174234 (All versions of this report)
Short URL: ia.cr/2010/212
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]