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

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