Technical Report CS0683

Authors: O. Goldreich, E. Petrank
PDF - RevisedCS0683.revised.pdf
Abstract: One of the many contributions of the seminal paper of Goldwasser, Micali and Rackoff [GMR] is the introduction of the notion of knowledge complexity. Knowledge complexity zero (also known as zero-knowledge) seems to have received most of the attention of the authors and all the attention of their followers. Unfortunately, the formulation of knowledge complexity (greater than zero) as appearing in that pioneering paper seems to be inadequate. In this paper, we present several alternative definitions of knowledge complexity and investigate the relations between them.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1991
To the main CS technical reports page

Computer science department, Technion