The Complexity of Zero Knowledge

Salil Vadhan
Harvard University

I will survey our efforts to carry out a complexity-theoretic study of zero-knowledge protocols, including the following results:
A characterization of the class of problems having general, computational zero-knowledge proofs in terms of the class of problems having statistical zero-knowledge proofs; an equivalence between zero-knowledge proofs and certain kinds of "instance-dependent" commitment schemes; a transformation converting zero-knowledge proofs with computationally unbounded provers into ones where the prover can be implemented in probabilistic polynomial time given an NP witness; the novelty of these results comes from the fact that they are *unconditional, i.e. do not rely on complexity assumptions such as the existence of one-way functions.

Joint works with Minh Nguyen, Shien Jin Ong, and others.

Audio (MP3 File, Podcast Ready) Presentation (PowerPoint File)

Back to Workshop III: Foundations of secure multi-party computation and zero-knowledge and its applications