## CryptoDB

### Paper: Concurrent Zero Knowledge Proofs with Logarithmic Round-Complexity

Authors: Manoj Prabhakaran Amit Sahai URL: http://eprint.iacr.org/2002/055 Search ePrint Search Google 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
}