loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)
An Unconditional Study of Computational Zero Knowledge
Rome, Italy
October 17-October 19
ISBN: 0-7695-2228-9
ASCII Text
x 
 
Salil P. Vadhan, "An Unconditional Study of Computational Zero Knowledge," Foundations of Computer Science, IEEE Annual Symposium on, pp. 176-185, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/FOCS.2004.13,
author = {Salil P. Vadhan},
title = {An Unconditional Study of Computational Zero Knowledge},
journal ={Foundations of Computer Science, IEEE Annual Symposium on},
volume = {0},
year = {2004},
issn = {0272-5428},
pages = {176-185},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.13},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, IEEE Annual Symposium on
TI - An Unconditional Study of Computational Zero Knowledge
SN - 0272-5428
SP176
EP185
A1 - Salil P. Vadhan,
PY - 2004
KW - null
VL - 0
JA - Foundations of Computer Science, IEEE Annual Symposium on
ER -
 
Salil P. Vadhan, Harvard University

We prove a number of general theorems about CZK, the class of problems possessing computational zero knowledge proofs. Our results are unconditional, in contrast to most previous works on CZK which rely on the assumption that one-way functions exist.

We establish several new characterizations ofCZK, and use these characterizations to prove results such as:

  • 1. Honest-verifier CZK equals general CZK.
  • 2. Public-coin CZK equals private-coin CZK.
  • 3. CZK is closed under union (and more generally, "monotone formula closure").
  • 4. CZK with imperfect completeness equals CZK with perfect completeness.
  • 5. Any problem in CZK ∩ NP can be proven in computational zero knowledge by a BPP^NP prover.
  • 6. CZK with black-box simulators equals CZK with general, non-black-box simulators.
    • The above equalities refer to the resulting class of problems (and do not necessarily preserve other efficiency measures such as round complexity).

    Our approach is to combine the conditional techniques previously used in the study of CZK with the unconditional techniques developed in the study of SZK, the class of problems possessing statistical zero knowledge proofs. To enable this combination, we prove that every problem in CZK can be decomposed into a a problem in SZK together with a set of instances from which a one-way function can be constructed.

    Citation:
    Salil P. Vadhan, "An Unconditional Study of Computational Zero Knowledge," focs, pp.176-185, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004
    Usage of this product signifies your acceptance of the Terms of Use.