CryptoDB
Concurrent Zero Knowledge Proofs with Logarithmic Round-Complexity
Authors: | |
---|---|
Download: | |
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. |
BibTeX
@misc{eprint-2002-11579, title={Concurrent Zero Knowledge Proofs with Logarithmic Round-Complexity}, booktitle={IACR Eprint archive}, keywords={cryptographic protocols / Zero-Knowledge, Concurrent Zero-Knowledge, Concurrency}, url={http://eprint.iacr.org/2002/055}, note={ mp@cs.princeton.edu 11813 received 6 May 2002}, author={Manoj Prabhakaran and Amit Sahai}, year=2002 }