**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.

**Category / Keywords: **cryptographic protocols / Zero-Knowledge, Concurrent Zero-Knowledge, Concurrency

**Date: **received 6 May 2002

**Contact author: **mp at cs princeton edu

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20020506:231802 (All versions of this report)

**Short URL: **ia.cr/2002/055

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]