Vadhan, Salil. “
An unconditional study of computational zero knowledge.”
SIAM Journal on Computing: Special Issue on Randomness and Complexity 36, no. 4 (2006): 11601214.
Publisher's VersionAbstract
Version History: Extended abstract in FOCS '04.
We prove a number of general theorems about \(\mathbf{ZK}\), the class of problems possessing (computational) zeroknowledge proofs. Our results are unconditional, in contrast to most previous works on \(\mathbf{ZK}\), which rely on the assumption that oneway functions exist. We establish several new characterizations of \(\mathbf{ZK}\) and use these characterizations to prove results such as the following:

Honestverifier \(\mathbf{ZK}\) equals general \(\mathbf{ZK}\).

Publiccoin \(\mathbf{ZK}\) equals privatecoin \(\mathbf{ZK}\).

\(\mathbf{ZK}\) is closed under union.

\(\mathbf{ZK}\) with imperfect completeness equals \(\mathbf{ZK}\) with perfect completeness.

Any problem in \(\mathbf{ZK}\) \(\cap\) \(\mathbf{NP} \) can be proven in computational zero knowledge by a \(\mathbf{BPP^{NP}}\)prover.

\(\mathbf{ZK}\) with blackbox simulators equals \(\mathbf{ZK}\) with general, non–blackbox 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 \(\mathbf{ZK}\) with the unconditional techniques developed in the study of \(\mathbf{SZK}\), the class of problems possessing statistical zeroknowledge proofs. To enable this combination, we prove that every problem in \(\mathbf{ZK}\) can be decomposed into a problem in \(\mathbf{SZK}\) together with a set of instances from which a oneway function can be constructed.
SICOMP2006.pdf Micciancio, Daniele, Shien Jin Ong, Amit Sahai, and Salil Vadhan. “
Concurrent zero knowledge without complexity assumptions.” In
S. Halevi and T. Rabin, eds., Proceedings of the Third Theory of Cryptography Conference (TCC '06), 3876:120. New York, NY, USA: Springer Verlag, Lecture Notes in Computer Science, 2006.
Publisher's VersionAbstract
Version History. Full version available at https://eccc.weizmann.ac.il//ecccreports/2005/TR05093/ (Attached as ECCC2005).
We provide unconditional constructions of concurrent statistical zeroknowledge proofs for a variety of nontrivial problems (not known to have probabilistic polynomialtime algorithms). The problems include Graph Isomorphism, Graph Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a restricted version of Statistical Difference, and approximate versions of the (\(\mathsf{coNP}\) forms of the) Shortest Vector Problem and Closest Vector Problem in lattices. For some of the problems, such as Graph Isomorphism and Quadratic Residuosity, the proof systems have provers that can be implemented in polynomial time (given an \(\mathsf{NP}\) witness) and have \(\tilde{O}(\log n)\) rounds, which is known to be essentially optimal for blackbox simulation. To the best of our knowledge, these are the first constructions of concurrent zeroknowledge proofs in the plain, asynchronous model (i.e., without setup or timing assumptions) that do not require complexity assumptions (such as the existence of oneway functions).
ECCC2005.pdf TCC2006.pdf Nguyen, Minh, and Salil Vadhan. “
Zero knowledge with efficient provers.” In
Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC ‘06), 287295. ACM, 2006.
Publisher's VersionAbstractWe prove that every problem in NP that has a zeroknowledge proof also has a zeroknowledge proof where the prover can be implemented in probabilistic polynomial time given an NP witness. Moreover, if the original proof system is statistical zero knowledge, so is the resulting efficientprover proof system. An equivalence of zero knowledge and efficientprover zero knowledge was previously known only under the assumption that oneway functions exist (whereas our result is unconditional), and no such equivalence was known for statistical zero knowledge. Our results allow us to translate the many general results and characterizations known for zero knowledge with inefficient provers to zero knowledge with efficient provers.
STOC2006.pdf