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.]