### 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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2010/212

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},
note = {\url{https://eprint.iacr.org/2010/212}},
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.