CryptoDB
Which Languages Have 4-Round Zero-Knowledge Proofs?
Authors: | |
---|---|
Download: | |
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 }