zbMATH — the first resource for mathematics

The knowledge complexity of interactive proof systems. (English) Zbl 0677.68062
The 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.

68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
03F07 Structure of proofs
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
94A60 Cryptography
Full Text: DOI