Quantum Proofs of Knowledge

Dominique Unruh

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

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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in EUROCRYPT 2012
DOI: 10.1007/978-3-642-29011-4_10
Keywords: Quantum cryptography proofs of knowledge
Contact author(s): unruh @ ut ee
History: 2015-02-11: last of 4 revisions; 2010-04-19: received; See all versions
Short URL: https://ia.cr/2010/212
License: CC BY

BibTeX

@misc{cryptoeprint:2010/212,
      author = {Dominique Unruh},
      title = {Quantum Proofs of Knowledge},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/212},
      year = {2010},
      doi = {10.1007/978-3-642-29011-4_10},
      url = {https://eprint.iacr.org/2010/212}
}