The Complexity of Zero Knowledge


Salil Vadhan


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



  • Talk at NY Theory Day, November 18, 2005. [pps]
  • Talk at IPAM Workshop on the Foundations of Secure Multiparty Computation and Zero Knowledge and its Applications, November 13-17, 2006. [pps][audio]
  • Colloquium (“tenure talk”), Harvard University, November 21, 2006. [pps]
  • Survey to appear in FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 27th International Conference, Springer-Verlag LNCS 4855, pages 52-70, December 2007. [ps][pdf]

 [ back to Salil Vadhan's research]