Black-box concurrent zero-knowledge requires \tilde {Ω} (log n ) rounds
Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen · 2001
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Ω(log n) rounds of interaction. This result substantially improves over previous lower bounds, and is the first bound to rule out the possibility of constant-round black-box concurrent zero-knowledge. Furthermore, the bound is polynomially related to the number of rounds in the best known concurrent zero-knowledge protocol for languages in ~$\NP$.