Black-Box Concurrent Zero-Knowledge Requires $\tilde\Omega(\log n)$ Rounds

Ran Canetti; Joe Kilian; Erez Petrank; Alon Rosen

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2001/051

Black-Box Concurrent Zero-Knowledge Requires $\tilde\Omega(\log n)$ Rounds

Ran Canetti, Joe Kilian, Erez Petrank, and Alon Rosen

Abstract

We show that any concurrent zero-knowledge protocol for a non-trivial language (i.e., for a language outside $\BPP$), whose security is proven via black-box simulation, must use at least $\tilde\Omega(\log n)$ rounds of interaction. This result achieves a substantial improvement over previous lower bounds, and is the first bound to rule out the possibility of constant-round concurrent zero-knowledge when proven via black-box simulation. Furthermore, the bound is polynomially related to the number of rounds in the best known concurrent zero-knowledge protocol for languages in $\NP$.

Metadata

Available format(s): PS
Category: Cryptographic protocols
Publication info: Published elsewhere. An extended abstract to appear in STOC01
Keywords: zero-knowledge
Contact author(s): alon @ wisdom weizmann ac il
History: 2001-06-24: received
Short URL: https://ia.cr/2001/051
License: CC BY

BibTeX

@misc{cryptoeprint:2001/051,
      author = {Ran Canetti and Joe Kilian and Erez Petrank and Alon Rosen},
      title = {Black-Box Concurrent Zero-Knowledge Requires $\tilde\Omega(\log n)$ Rounds},
      howpublished = {Cryptology ePrint Archive, Paper 2001/051},
      year = {2001},
      note = {\url{https://eprint.iacr.org/2001/051}},
      url = {https://eprint.iacr.org/2001/051}
}