Which Languages Have 4-Round Zero-Knowledge Proofs?

Jonathan Katz

Paper 2007/265 Original: eprint.iacr.org/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: Preprint.
History: 2007-12-07: last updated; 2007-07-09: published
Short URL: https://ia.cr/2007/265
License: https://creativecommons.org/licenses/by/4.0/

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}
}