Knowledge complexity measures how much a party gains from an interaction with another (possibly stronger) party. Making sure that a party learns nothing or very little >from an interaction is a fundamental issue in cryptography, hence the extensive study of the special case of zero knowledge complexity. We consider Knowledge Complexity to be also a fundamental issue in complexity, where we would like to understand not only the computational abilities of machines working on their own, but also their computational abilities following an interaction with the rest of the world.
In this work, we study "what can be done" in low knowledge complexity. In particular, we ask which languages can be proven in low knowledge complexity. We show that all languages which have interactive proofs with logarithmic knowledge complexity are in the class co-AM. This class does not contain NP unless the Polynomial Time Hierarchy (PH) collapses. Thus, if the Polynomial Time Hierarchy does not collapse, then complete NP langauges cannot be proven without yielding to the verifier super-logarithmic bits of knowledge. Additional results will be discussed in the talk.
This work is a joint work with Gabor Tardos.