Black-box concurrent zero-knowledge requires Omega~(log n) rounds

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$.

Authors

• Ran Canetti
• Joe Kilian
• Erez Petrank
• Alon Rosen

Keywords

No keywords are indexed for this paper.