Cryptology ePrint Archive: Report 2007/265
Which Languages Have 4-Round Zero-Knowledge Proofs?
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).
Category / Keywords: foundations / zero knowledge
Date: received 8 Jul 2007, last revised 6 Dec 2007
Contact author: jkatz at cs umd edu
Available format(s): PDF | BibTeX Citation
Version: 20071207:023148 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]