Concurrent zero knowledge with logarithmic round-complexity

We show that every language in NP has a (black-box) concurrent zero-knowledge proof system using Õ(logn) rounds of interaction. The number of rounds in our protocol is optimal, in the sense that any language outside BPP re-quires at least Ω̃(logn) rounds of interaction in order to be proved in black-box concurrent zero-knowledge. The zero-knowledge property of our main protocol is proved under the assumption that there exists a collection of claw-free functions. Assuming only the existence of one-way func-tions, we show the existence of Õ(log n)-round concurrent zero-knowledge arguments for all languages in NP.