## Cryptology ePrint Archive: Report 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.

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