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.
Category / Keywords: cryptographic protocols / concurrent zero knowledge, commitment schemes, DDH assumption Date: received 8 Jul 2002 Contact author: daniele at cs ucsd edu Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20020708:211711 (All versions of this report) Discussion forum: Show discussion | Start new discussion