Paper 2000/013

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.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
zero-knowledge
Contact author(s)
erez @ cs technion ac il
History
2000-05-28: revised
2000-04-24: received
See all versions
Short URL
https://ia.cr/2000/013
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2000/013,
      author = {Joe Kilian and Erez Petrank},
      title = {Concurrent Zero-Knowledge in Poly-logarithmic Rounds},
      howpublished = {Cryptology ePrint Archive, Paper 2000/013},
      year = {2000},
      note = {\url{https://eprint.iacr.org/2000/013}},
      url = {https://eprint.iacr.org/2000/013}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.