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 rounds where is the security parameter. Till now the best known upper bound on the number of rounds for NP languages was , due to Kilian, Petrank and Richardson. We establish an upper bound of on the number of rounds for NP languages, thereby closing the gap between the upper and lower bounds, up to a 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

BibTeX

@misc{cryptoeprint:2002/055,
      author = {Manoj Prabhakaran and Amit Sahai},
      title = {Concurrent Zero Knowledge Proofs with Logarithmic Round-Complexity},
      howpublished = {Cryptology {ePrint} Archive, Paper 2002/055},
      year = {2002},
      url = {https://eprint.iacr.org/2002/055}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.