You are looking at a specific version 20020506:231802 of this paper. See the latest version.

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

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
Zero-KnowledgeConcurrent Zero-KnowledgeConcurrency
Contact author(s)
mp @ cs princeton edu
History
2002-05-06: received
Short URL
https://ia.cr/2002/055
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.