Black-box concurrent zero-knowledge requires Ω̃(log n) Rounds

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 Ω̃(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.