CS Colloquium, April 6, 4pm.
Computer Science Dept Room 104 (Small Auditorium). Statistical Zero Knowledge
Amit Sahai
Lab for Computer Science, MIT
| Zero-knowledge proofs, introduced by Goldwasser, Micali, and
Rackoff, are fascinating constructs in which one party (the "prover") convinces
another party (the "verifier") that some assertion is true, withoutrevealing
anything else to the verifier. Zero-knowledge proofs are powerful tools for constructing
secure cryptographic protocols, and also 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. Our goal is to build a unified understanding of Statistical Zero Knowledge. We accomplish this goal by establishing two results: - 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 system 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 Salil Vadhan) |