Paper 2010/212 Original: eprint.iacr.org/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).
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2015-02-11: last updated
- 2010-04-19: published
- Short URL
- https://ia.cr/2010/212
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2010/212,
author = {Dominique Unruh},
title = {Quantum Proofs of Knowledge},
howpublished = {Cryptology {ePrint} Archive, Paper 2010/212},
year = {2010},
url = {https://eprint.iacr.org/2010/212}
}