Paper 2002/055
Concurrent Zero Knowledge Proofs with Logarithmic Round-Complexity
Manoj Prabhakaran and Amit Sahai
Abstract
We consider the problem of constructing Concurrent Zero Knowledge Proofs, in which the fascinating and useful ``zero knowledge'' property is guaranteed even in situations where multiple concurrent proof sessions are executed with many colluding dishonest verifiers. Canetti et al. show that black-box concurrent zero knowledge proofs for non-trivial languages require $\tilde\Omega(\log k)$ rounds where $k$ is the security parameter. Till now the best known upper bound on the number of rounds for NP languages was $\omega(\log^2 k)$, due to Kilian, Petrank and Richardson. We establish an upper bound of $\omega(\log k)$ on the number of rounds for NP languages, thereby closing the gap between the upper and lower bounds, up to a $\omega(\log\log k)$ factor.
Metadata
- Available format(s)
-
PDF
PS
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- Zero-KnowledgeConcurrent Zero-KnowledgeConcurrency
- Contact author(s)
- mp @ cs princeton edu
- History
- 2002-05-06: received
- Short URL
- https://ia.cr/2002/055
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2002/055,
author = {Manoj Prabhakaran and Amit Sahai},
title = {Concurrent Zero Knowledge Proofs with Logarithmic Round-Complexity},
howpublished = {Cryptology {ePrint} Archive, Paper 2002/055},
year = {2002},
url = {https://eprint.iacr.org/2002/055}
}
