Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-065 | 13th July 2007 00:00

Which Languages Have 4-Round Zero-Knowledge Proofs?

RSS-Feed




TR07-065
Authors: Jonathan Katz
Publication: 23rd July 2007 09:32
Downloads: 2121
Keywords: 


Abstract:

We show 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).



ISSN 1433-8092 | Imprint