Cryptology ePrint Archive: Report 2010/212

Quantum Proofs of Knowledge

Dominique Unruh

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
DOI: 10.1007/978-3-642-29011-4_10

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