|
Abstract : |
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 \Gamma input zero-knowledge and blackbox \Gamma simulation zero-knowledge. We explain why auxiliary-input zero-knowledge is a definition more suitable for cryptographic applications than the original [GMR1] definition. In particular, we show that any protocol solely composed of subprotocols which are auxiliaryinput zero-knowledge is itself auxiliary-input zero-knowledge. We show that blackboxsimulation zero-knowledge implies auxiliary-input zero-knowledge (which in turn implies the [GMR1] definition). We argue that all known zero-knowledge proofs are in fact blackbox-simulation zero-knowledge (i.e., were proved zero-knowledge using blackboxsimulation 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 zeroknowledge 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. Preliminary versions of this work have appeared in [O1, O2]. WARNING: The current text was automatiocally translated from old troff files. Such translations may introduce errors. Furthermore, I'm not sure whether the source troff files I've found are actually the onesw corresponding to the final version. Errors may be due to this fact too. The final version has appeared in Journal of Cryptology, Vol. 7, No. 1 (1994), pp. 1--32. 1. INTRODUCTION The, |
