Cryptology ePrint Archive: Report 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).

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)

Short URL: ia.cr/2007/265

Discussion forum: Show discussion | Start new discussion