Interactive Hashing Simplifies Zero-Knowledge Protocol Design

Often the core difficulty in designing zero-knowledge protocols arises from having to consider every possible cheating verifier trying to extract additional information. We here consider a compiler which transforms protocols proven secure only with respect to the honest verifier into protocols which are secure against any (even cheating) verifier. Such a compiler, which preserves the zero-knowledge property of a statistically or computationally secure protocol was first proposed in [BMO] based on Discrte Logarithm problem. In this paper, we show how such a compiler could be constructed based on any one-way permutation using the recent method of interactive hashing [OVY-91]. This applies to both statistically and computationally secure protocols, preserving their respective security. Our result allows us to utilize DES-like permutations for such a compiler. University of California at Berkeley Computer Science Division, and International Computer Science Institute at Berkeley. E-mail:..