Technical Report CS0615

TR#:CS0615
Class:CS
Title: PROOFS THAT YIELD ~OTHING BUT THEIR VALIDITY or ALL LANGUAGES IN NP HAVE ZERO-KNOWLEDGE PROOF SYSTEMS (Revised Version oŁ TR~ 498 & 544)
Authors: o. Goldreich, S. Micali, and A. Wigderson
PDFCS0615.pdf
Abstract: In this paper we demonstrate the generality and wide applicability of zero-knowledge proofs, a notion introduced by Goldwasser, Micali and 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 NPrlCoNP. Under the assumption that secure encryption functions exist or by using "physical means for hiding infonnation", we show that all languages in NP have zero-knowledge proofs. Loosely speaking, it is possible to demonstrate that a CNF fonnula is satisfiable without revealing any other property of the fonnula. In particular, without yielding neither a satisfying assignment nor properties such as whether there is a satisfying assignment in which xl=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 7..ero-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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1990/CS/CS0615), 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 1990
To the main CS technical reports page

Computer science department, Technion
admin