Abstract
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.
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.
No video available