Quantum Proofs of Knowledge

Dominique Unruh.
in Eurocrypt 2012, LNCS vol. 7237, Springer, pp. 135-152, April 2012. Preprint on IACR ePrint 2010/212.

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.

Files available online

This publication is accompanied by links to downloadable versions of this publication. These documents do not necessarily correspond exactly to the cited version. Instead, in most cases full, updated or preliminary versions are provided. For access to the official version, follow the "Official version" link to the publishers site.

Slides used in my talks are available upon personal request, as long as you agree not to disseminate them to a wider audience or make them available online. If in doubt, please ask.