The knowledge complexity of interactive proof systems.

*(English)*Zbl 0677.68062The authors note that usually the proof of a theorem uses more knowledge than the statement of the theorem alone. This is important in cryptography where one wants to avoid giving the other party more information than what is stated explicitly and is looking for a protocol that will not allow the other party to extract more knowledge by cheating on the protocol. The authors define zero-knowledge probabilistic interactive protocols of several kinds, all depending on the length of binary codes, which they compare to prior definitions and show that the definitions are not void by providing a zero-knowledge proof, given two integers \(x, y\), for \(y\) to be or not to be a quadratic residue of \(x\) so that any additional knowledge about \(y\) (as e.g., the knowledge of any factor of \(y\)) is strictly more expensive in computer time than the verification of the given statement.

Reviewer: Heinrich Guggenheimer