## CryptoDB

### Paper: Which Languages Have 4-Round Zero-Knowledge Proofs?

Authors: Jonathan Katz URL: http://eprint.iacr.org/2007/265 Search ePrint Search Google 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
}