1987 Reports

The Theory of Minimum-Knowledge Protocols

Haber, Stuart

This paper explores the complexity-theoretic approach to the transmission of knowledge that was introduced by Goldwasser, Micali. and Rackoff, and further studied by a number of authors. Roughly speaking, a protocol designed to solve a given computational problem is said to be minimum-knowledge if its outputs give no more information than an oracle for the problem would give to a user whose computational resources are polynomially bounded. This notion has important consequences for the design of cryptographic protocols. A few slightly different definitions have been given in the literature: some of the results included here have been published previously without proofs. This paper proposes a uniform definition. collects the known results and proves them, and describes the problems that are still not understood.