Papers on Knowledge-Complexity by Oded Goldreich

Knowledge complexity is intended to measure the computational advantage gained by interaction. Hence, something that can be obtained without interaction is not considered knowledge. The latter phrase is somewhat qualitative and supplies the intuition underlying the definition of zero-knowledge (i.e., knowledge complexity zero). Quantifying the amount of knowledge gained by interaction, in case it is not zero, is more problematic. We stress that the definition of zero-knowledge does not depend on the formulation of the amount of knowledge gained since this definition addresses the case in which no knowledge is gained. Various formulations of knowledge-complexity are given and investiagted in [Goldreich and Petrank (1991)].

The following papers can be obtained in PostScript (papers are ordered by the full author-list):

See also web-page on Zero-Knowledge.
Back to Oded Goldreich's homepage or to the full list of papers.