Academic Commons


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.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-264-87
Published Here
November 28, 2011