[Resource Topic] 2001/051: Black-Box Concurrent Zero-Knowledge Requires $\tilde\Omega(\log n)$ Rounds

Welcome to the resource topic for 2001/051

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

Authors: Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen


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.

ePrint: https://eprint.iacr.org/2001/051

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .