DEFINITIONS AND PROPERTIES OF ZERO-KNOWLEDGE PROOF SYSTEMS

In this paper we investigate some properties of zero-knowledge proofs, a notion introduced by Goldwasser, Micali, and Rackoff. We introduce and classify two definitions of zero-knowledge: auxiliary-input zero-k nowledge and blackbox-simulation zero-knowledge. We explain why auxili ary-input zero-knowledge is a definition more suitable for cryptograph ic applications than the original [GMR1] definition. In particular, we show that any protocol solely composed of subprotocols which are auxi liary-input zero-knowledge is itself auxiliary-input zero-knowledge. W e show that blackbox-simulation zero-knowledge implies auxiliary-input zero-knowledge (which in tum implies the [GMR1] definition). We argue that all known zero-knowledge proofs are in fact blackbox-simulation zero-knowledge (i.e., we proved zero-knowledge using blackbox-simulati on of the verifier). As a result, all known zero-knowledge proof syste ms 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 z ero-knowledge proof system necessarily belongs to RP. We show that ran domness of both the verifier and the prover, and nontriviality of the interaction are essential properties of (nontrivial) auxiliary-input z ero-knowledge proofs.