An Unconditional Study of
Computational Zero Knowledge
Salil P. Vadhan
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:
- Honest-verifier ZK equals
- Public-coin ZK equals
- ZK is closed under union (and
more generally, "monotone formula closure").
- ZK with imperfect
completeness equals ZK with perfect completeness.
- Any problem in [ZK intersect
NP] can be proven in computational zero knowledge by a BPP^NP prover.
- 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.
- In Proceedings of the 45th
Annual Symposium on Foundations of Computer Science (FOCS `04),
pages 176-185, Rome, Italy, October 2004.
- Full version, March 2005. [postscript][pdf]
- Electronic Colloquium on
Computational Complexity, Technical Report TR06-056, April 2006. [postscript][pdf][official
- SIAM Journal on
Computing 36 (4), pp.
1160-1214, 2006. Special Issue on Randomness and Complexity.
[official SICOMP page]
[ back to
Salil Vadhan's research]