Technical Report CS0544

Title: Proofs That Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proofs
Authors: O. Goidreich, S. Micali and A. Wigderson
Abstract: In this paper we demonstrate the generality and wide applicability of zero-knowledge proofs, a notion introduced by Goldwasser, Micali an,d Rackoff. These are probabilistic and interactive proofs that, for the members of a language, efficiently demonstrate membership in the language without conveying any additional knowledge. All previously known zero-knowledge proofs were only for number-theoretic languages-in NP-intersect-CoNP.

Under the assumption that secure encryption functions exist or by using "physical means for hiding information", we show that all languages in NP have zero-knowledge-proofs. Loosely speaking, it is possible to demonstrate that a CNF formula is satisfiable without revealing any other property of the formula. In particular, without yielding neither a satisfying assignment nor properties such as whether there is a satisfying assignmenrin which x1=x3 etc.

We also demonstrate that zero-knowledge proofs exist "outside the domain of cryptography and number theory". Using no assumptions, we show that both graph isomorphism and graph non-isomorphism have zero-knowledge interactive proofs. The mere existence of an interactive proof for graph non-isomorphism is interesting, since graph non-isomorphism is not known to be in NP and hence no efficient proofs were known before for demonstrating that two graphs are not isomorphic.

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 1989
To the main CS technical reports page

Computer science department, Technion