An Unconditional Study of Computational Zero Knowledge
View/ Open
Author
Vadhan, Salil P.
Published Version
https://doi.org/10.1137/S0097539705447207Metadata
Show full item recordCitation
Vadhan, Salil P. 2006. “An Unconditional Study of Computational Zero Knowledge.” SIAM Journal on Computing 36 (4): 1160–1214. https://doi.org/10.1137/s0097539705447207.Abstract
We prove a number of general theorems about ZK, the class of problems possessing ( computational) zero-knowledge proofs. Our results are unconditional, in contrast to most previous works on ZK, which rely on the assumption that one-way functions exist. We establish several new characterizations of ZK and use these characterizations to prove results such as the following:1. Honest-verifier ZK equals general ZK.2. Public-coin ZK equals private-coin ZK.3. ZK is closed under union.4. ZK with imperfect completeness equals ZK with perfect completeness.5. Any problem in ZK boolean AND NP can be proven in computational zero knowledge by a BPPNP prover.6. ZK with black-box simulators equals ZK 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 ZK 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 ZK can be decomposed into a problem in SZK together with a set of instances from which a one-way function can be constructed.Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAACitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:41467482
Collections
- FAS Scholarly Articles [18172]
Contact administrator regarding this item (to report mistakes or request changes)