Paper 2007/265

Which Languages Have 4-Round Zero-Knowledge Proofs?

Jonathan Katz

Abstract

We show, unconditionally, that if a language $L$ has a 4-round, black-box, computational zero-knowledge proof system with negligible soundness error, then $\bar L \in MA$. Assuming the polynomial hierarchy does not collapse, this means, in particular, that $NP$-complete languages do not have 4-round zero-knowledge proofs (at least with respect to black-box simulation).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
zero knowledge
Contact author(s)
jkatz @ cs umd edu
History
2007-12-07: last of 4 revisions
2007-07-09: received
See all versions
Short URL
https://ia.cr/2007/265
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/265,
      author = {Jonathan Katz},
      title = {Which Languages Have 4-Round Zero-Knowledge Proofs?},
      howpublished = {Cryptology ePrint Archive, Paper 2007/265},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/265}},
      url = {https://eprint.iacr.org/2007/265}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.