**Concurrent Zero-Knowledge in Poly-logarithmic Rounds**

*Joe Kilian and Erez Petrank*

**Abstract: **A proof is concurrent zero-knowledge if it remains zero-knowledge when run in an asynchronous environment, such as
the Internet. It is known that zero-knowledge is not necessarily preserved in such an environment; Kilian, Petrank and Rackoff have
shown that any {\bf 4} rounds zero-knowledge interactive proof (for a non-trivial language) is not concurrent zero-knowledge. On the
other hand, Richardson and Kilian have shown that there exists a concurrent zero-knowledge argument for all languages in NP, but it
requires a {\bf polynomial} number of rounds. In this paper, we present a concurrent zero-knowledge proof for all languages in NP
with a drastically improved complexity: our proof requires only a poly-logarithmic, specifically, $\omega(\log^2 k)$ number of rounds.
Thus, we narrow the huge gap between the known upper and lower bounds on the number of rounds required for a zero-knowledge
proof that is robust for asynchronous composition.

**Category / Keywords: **foundations / zero-knowledge

**Date: **received 24 Apr 2000, revised 28 May 2000

**Contact author: **erez at cs technion ac il

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20000528:112402 (All versions of this report)

**Short URL: **ia.cr/2000/013

[ Cryptology ePrint archive ]