International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Which Languages Have 4-Round Zero-Knowledge Proofs?

Authors:
Jonathan Katz
Download:
URL: http://eprint.iacr.org/2007/265
Search ePrint
Search Google
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).
BibTeX
@misc{eprint-2007-13546,
  title={Which Languages Have 4-Round Zero-Knowledge Proofs?},
  booktitle={IACR Eprint archive},
  keywords={foundations / zero knowledge},
  url={http://eprint.iacr.org/2007/265},
  note={ jkatz@cs.umd.edu 13854 received 8 Jul 2007, last revised 6 Dec 2007},
  author={Jonathan Katz},
  year=2007
}