Technical Report CS0610

Authors: Oded Goldreich and Yair Oren
Abstract: In this paper we investigate some propenies of zero-knowledge proofs, a notion introduced by Goldwasser, Micali and Rackoff. We introduce and classify two definitions of zero-knowledge: auxiliary -input zero-knowledge and blackbox-simulation zero-knowledge. We explain why auxiliary-input zeroknowledge is a definition more suitable for cryptographic applications than the original [GMRI] definition. In particular, we show that any protocol composed of subprotocols which are auxiliary-input zero-knowledge is itself auxiliary-input zero-knowledge. We show that blackbox-simulation zero-knowledge implies auxiliary-input zero-knowledge (which in tum implies the [GMRl] definition). We argue that all known zero-knowledge proofs are in fact blackbox-simulation zero-knowledge (i e., were proved zero-knowledge using blackbox-simulation of the verifier). As a result, all known zero-knowledge proof systems are shown to be auxiliary-input zero-knowledge and can be used for cryptographic applications such as those in [GMW2]. We demonstrate the triviality of certain classes of zero-knowledge proof systems, in the sense that only languages in BPP have zero-knowledge proofs of these classes. In particular, we show that any language having a Las Vegas zero-knowledge proof system necessarily belongs to RP. We show that randomness of both the verifier and the prover, and non-triviality of the interaction are essential properties of (non-trivial) auxiliary-input zero-knowledge proofs.
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 1990
To the main CS technical reports page

Computer science department, Technion