Hashing Functions can Simplify Zero-Knowledge Protocol Design (too)

Ivan Damgård
Oded Goldreich
Avi Wigderson

November 1994


In Crypto93, Damgård showed that any constant-round protocol in which the verifier sends only independent, random bits and which is zero-knowledge against the honest verifier can be transformed into a protocol (for the same problem) that is zero-knowledge in general. His transformation was based on the interactive hashing technique of Naor, Ostrovsky, Venkatesan and Yung, and thus the resulting protocol had very large round-complexity.

We adopt Damgård's methods, using ordinary hashing functions, instead of the abovementioned interactive hashing technique. Typically, the protocols we derive have much lower round-complexity than those derived by Damgård's transformation. As in Damgård's transformation, our transformation preserves statistical/perfect zero-knowledge and does not rely on any computational assumptions. However, unlike Damgård's transformation, the new transformation is not applicable to argument systems or to proofs of knowledge.

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.