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 cryptographyproofs 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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.