The Complexity of Zero Knowledge
Zero-knowledge proofs are interactive protocols whereby one party, the prover, can convince another, the verifier, that some assertion is true with the remarkable property that the verifier learns nothing other than the fact that the assertion being proven is true. In the quarter-century since they were introduced, zero-knowledge proofs have provided one of the most fertile grounds for interaction between cryptography and complexity theory. On one hand, zero-knowledge proofs and their cryptographic applications naturally raise interesting complexity issues, such as characterizing the statements that can be proven in zero knowledge and identifying the minimal complexity assumptions needed to do so. On the other hand, the study of proofs is intimately related to the central questions of complexity theory, and zero knowledge enriches this study by incorporating such intriguing concepts as interaction, randomness, knowledge, and secrecy.
In the talks and article below, we survey some of the complexity-theoretic study of zero-knowledge proofs, including our recent works (with Shien Jin Ong and others) providing exact characterizations and unconditional results about each of the main flavors of zero-knowledge proofs.
[The talks at IPAM and Harvard are primarily focused on the work my students and I have been doing; the others are broader.]