Zero-knowledge proofs, introduced by Goldwasser, Micali, and Rackoff, are fascinating constructs which enable one party (the "prover") to convince another party (the "verifier") that some assertion is true, without revealing anything else to the verifier. In addition to being powerful tools for constructing secure cryptographic protocols, zero-knowledge proofs yield rich classes of computational problems that are of complexity-theoretic interest as well.

In this talk, we investigate *statistical* zero-knowledge proofs, which are zero-knowledge proofs where the condition that nothing is revealed to the verifier is interpreted in a strong information-theoretic sense.

We establish two main results about statistical zero-knowledge proofs:
- We show that the class of all problems possessing statistical zero-knowledge proofs has a natural complete problem. This problem provides a new and simple characterization of statistical zero knowledge -- one which makes no reference to interaction or zero knowledge.
- We show how to transform any interactive proof that is statistical zero knowledge only for an honest verifier (i.e., a verifier that follows the specified protocol) into one which is also zero knowledge against dishonest verifiers -- ones that may deviate arbitrarily from the specified protocol.

Using these results, we are able to unify and simplify nearly all previously known results about statistical zero knowledge, and prove several results answering many fundamental questions in this area.

An important feature of all our results is that, unlike many results in cryptography, we require no unproven assumptions.

(Joint work with Oded Goldreich and/or Salil Vadhan)