You are looking at a specific version 20010624:193949 of this paper.
See the latest version.
Paper 2001/051
Black-Box Concurrent Zero-Knowledge Requires $\tilde\Omega(\log n)$ Rounds
Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen
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 $\tilde\Omega(\log n)$ rounds of interaction. This result achieves a substantial improvement over previous lower bounds, and is the first bound to rule out the possibility of constant-round concurrent zero-knowledge when proven via black-box simulation. Furthermore, the bound is polynomially related to the number of rounds in the best known concurrent zero-knowledge protocol for languages in $\NP$.
Metadata
- Available format(s)
- PS
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. An extended abstract to appear in STOC01
- Keywords
- zero-knowledge
- Contact author(s)
- alon @ wisdom weizmann ac il
- History
- 2001-06-24: received
- Short URL
- https://ia.cr/2001/051
- License
-
CC BY