TR02-045 Authors: Daniele Micciancio, Erez Petrank

Publication: 16th July 2002 13:47

Downloads: 3002

Keywords:

We show how to efficiently transform any public coin honest verifier

zero knowledge proof system into a proof system that is concurrent

zero-knowledge with respect to any (possibly cheating) verifier via

black box simulation. By efficient we mean that our transformation

incurs only an additive overhead, both in terms of the number of

rounds and the computational and communication complexity of each

round, independently of the complexity of the original protocol.

Moreover, the transformation preserves (up to negligible additive

terms) the soundness and completeness error probabilities. The new

proof system is proved secure based on the Decisional Diffie-Hellman

(DDH) assumption, in the standard model of computation, i.e., no

random oracles, shared random strings, or public key infrastructure

is assumed. In addition to the introduction of a practical protocol,

this construction provides yet another example if ideas

in plausibility results that turn into ideas in the construction of

practical protocols.

We prove our main result by developing a mechanism for simulatable

commitments that may be of independent interest. In particular, it

allows a weaker result that is interesting as well. We present

an efficient transformation of any honest verifier public-coin

computational zero-knowledge proof into a (public coin) computational

zero-knowledge proof secure against any verifier. The overhead of this

second transformation is minimal: we only increase the number of rounds

by 3, and increase the computational cost by 2 public key operations for

each round of the original protocol. The cost of the more general

transformation leading to concurrent zero knowledge is also close

to optimal (for black box simulation), requiring only omega(log n)

additional rounds (where n is a security parameter and omega(log n) can

be any superlogarithmic function of n (e.g., log(n)log^*(n)), and

omega(log n) additional public key operations for each round of the

original protocol.