You are looking at a specific version 20071207:023148 of this paper. See the latest version.

Paper 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).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
zero knowledge
Contact author(s)
jkatz @ cs umd edu
History
2007-12-07: last of 4 revisions
2007-07-09: received
See all versions
Short URL
https://ia.cr/2007/265
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.