Which Languages Have 4-Round Zero-Knowledge Proofs?

Jonathan Katz

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: 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},
      url = {https://eprint.iacr.org/2007/265}
}