The Complexity of Zero Knowledge

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 line of work establishing general
theorems about zero-knowledge proofs without making any complexity
assumptions (such as the existence of one-way functions).  Most recently, we
have obtained a way to transform zero-knowledge proofs with computationally
unbounded provers into ones where the prover can be implemented in
polynomial time (given an NP witness).