Paper 2002/090
Efficient and Concurrent ZeroKnowledge from any public coin HVZK protocol
Daniele Micciancio and Erez Petrank
Abstract
We show how to efficiently transform any public coin honest verifier zero knowledge proof system into a proof system that is concurrent zeroknowledge 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 DiffieHellman (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 publiccoin computational zeroknowledge proof into a (public coin) computational zeroknowledge 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.
Metadata
 Available format(s)
 PDF PS
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 concurrent zero knowledgecommitment schemesDDH assumption
 Contact author(s)
 daniele @ cs ucsd edu
 History
 20020708: received
 Short URL
 https://ia.cr/2002/090
 License

CC BY
BibTeX
@misc{cryptoeprint:2002/090, author = {Daniele Micciancio and Erez Petrank}, title = {Efficient and Concurrent ZeroKnowledge from any public coin {HVZK} protocol}, howpublished = {Cryptology {ePrint} Archive, Paper 2002/090}, year = {2002}, url = {https://eprint.iacr.org/2002/090} }