A Caltech Library Service

Making Classical Honest Verifier Zero Knowledge Protocols Secure against Quantum Attacks

Hallgren, Sean and Kolla, Alexandra and Sen, Pranab and Zhang, Shengyu (2008) Making Classical Honest Verifier Zero Knowledge Protocols Secure against Quantum Attacks. In: Automata, Languages and Programming. Lecture Notes in Computer Science. Vol.2. No.5126. Springer , Berlin, pp. 592-603. ISBN 9783540705826.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We show that any problem that has a classical zero-knowledge protocol against the honest verifier also has, under a reasonable condition, a classical zero-knowledge protocol which is secure against all classical and quantum polynomial time verifiers, even cheating ones. Here we refer to the generalized notion of zero-knowledge with classical and quantum auxiliary inputs respectively. Our condition on the original protocol is that, for positive instances of the problem, the simulated message transcript should be quantum computationally indistinguishable from the actual message transcript. This is a natural strengthening of the notion of honest verifier computational zero-knowledge, and includes in particular, the complexity class of honest verifier statistical zero-knowledge. Our result answers an open question of Watrous [Wat06], and generalizes classical results by Goldreich, Sahai and Vadhan [GSV98], and Vadhan [Vad06] who showed that honest verifier statistical, respectively computational, zero knowledge is equal to general statistical, respectively computational, zero knowledge.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© Springer-Verlag Berlin Heidelberg 2008. We are grateful to an anonymous referee of an earlier version of this paper for detecting a subtle bug in that version, and also for informing us about the recent work of Ong and Vadhan [OV08] on zero-knowledge.We thank Shien Jin Ong and Salil Vadhan for clarifying many doubts about instance-dependent bit commitments and zero-knowledge.We also thank the anonymous referees of this version for helpful comments. S.Z. thanks Iordanis Kerenidis, Manoj Prabhakaran, Ben Reichardt, Amit Sahai, Yaoyun Shi, Robert Spalek, Shanghua Teng, Umesh Vazirani and Andy Yao for listening to the progress of the work, clarifying things and giving interesting comments. P.S. thanks Jaikumar Radhakrishnan and Thomas Vidick for helpful feedback. All authors thank Wei Huang and Martin Rötteler for discussions at an early stage of the work.
Subject Keywords:Positive Instance; Commitment Scheme; Quantum Simulator; Total Variation Distance; Message Transcript
Series Name:Lecture Notes in Computer Science
Issue or Number:5126
Record Number:CaltechAUTHORS:20180809-133557708
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:88706
Deposited By: George Porter
Deposited On:09 Aug 2018 21:25
Last Modified:16 Nov 2021 00:29

Repository Staff Only: item control page