Welcome to the resource topic for 2001/051
Title:
Black-Box Concurrent Zero-Knowledge Requires \tilde\Omega(\log n) Rounds
Authors: Ran Canetti, Joe Kilian, Erez Petrank, 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.
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 .