Paper 2000/013 Original: eprint.iacr.org/2000/013 ↗
Concurrent Zero-Knowledge in Poly-logarithmic Rounds
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- Category
- Foundations
- Publication info
- Preprint.
- History
- 2000-05-28: last updated
- 2000-04-24: published
- Short URL
- https://ia.cr/2000/013
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2000/013}
}