The Complexity of Zero Knowledge

Abstract

The study of zero-knowledge proofs has been 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 tradeoffs between various efficiency measures and the minimal assumptions needed to construct zero-knowledge proofs. 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 this talk, I will survey some of the complexity-theoretic study of zero-knowledge proofs, focusing on our recent work giving unconditional proofs of results that were previously known only under the assumption that one-way functions exist.