Quantum proofs of knowledge
D Unruh - Annual international conference on the theory and …, 2012 - Springer
Annual international conference on the theory and applications of …, 2012•Springer
We motivate, define and construct quantum proofs of knowledge, 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 …
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 …
Abstract
We motivate, define and construct quantum proofs of knowledge, 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).
Springer