Zero-knowledge interactive proofs, introduced by Goldwasser, Micali, and Rackoff, are fascinating constructs which enable one party (the "prover") to convince another party (the "verifier") of an assertion, with the property that the verifier learns nothing other than the fact that the assertion being proven is true. In addition to being powerful tools for constructing secure cryptographic protocols, zero-knowledge proofs yield rich classes of computational problems that are of both complexity-theoretic and cryptographic interest. This thesis is a detailed investigation of statistical zero-knowledge proofs, which are zero-knowledge proofs in which the condition that the verifier "learns nothing" is interpreted in a strong statistical sense. We begin by showing that the class SZK of problems possessing such proofs has two natural complete problems. These problems essentially amount to approximating the statistical difference or the difference in entropies between two "efficiently samplable" distributions. Thus, they give a new characterization of SZK which makes no reference to interaction or zero knowledge. They also simplify the study of statistical zero knowledge, as questions about the entire class SZK can be reduced to examining these two particular complete problems. Using these complete problems as tools, we proceed to answer a number of fundamental questions about zero-knowledge proofs, including:
Thesis Supervisor: Shafi Goldwasser, RSA Professor of Computer Science
Submitted to the Department of Mathematics of MIT, Septemeber 1999.
Winner of the ACM Doctoral Dissertation Award, 2000.
Available: the thesis in PS and in PDF.
Related papers with O.G.: 1st, 2nd and 3rd.
Back to Oded Goldreich's homepage.