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, without revealing 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. 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. From the Series:CSE Colloquia - 2000