International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Concurrent Zero Knowledge Proofs with Logarithmic Round-Complexity

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