**Authors:** Daniele Micciancio and Erez Petrank

Advances in Cryptology - Eurocrypt 2003. Warsaw, Poland, May 2004. LNCS
2656, Springer, pp. 614-629.

**Abstract:** 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 of 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.

**Preliminary version**: [IACR ePrint 2002-090] or [ECCC
TR 02-045]