TY - GEN
T1 - Making classical honest verifier zero knowledge protocols secure against quantum attacks
AU - Hallgren, Sean
AU - Kolla, Alexandra
AU - Sen, Pranab
AU - Zhang, Shengyu
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=49049100467&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=49049100467&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-70583-3_48
DO - 10.1007/978-3-540-70583-3_48
M3 - Conference contribution
AN - SCOPUS:49049100467
SN - 3540705821
SN - 9783540705826
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 592
EP - 603
BT - Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings
T2 - 35th International Colloquium on Automata, Languages and Programming, ICALP 2008
Y2 - 7 July 2008 through 11 July 2008
ER -