Perfect Zero-Knowledge in Constant Rounds.
Mihir Bellare, Silvio Micali, Rafail Ostrovsky.
Abstract: Interactive proofs and especially zero-knowledge ones have found many applications, most notably in the field of secure and distributed protocols. In this paper, we concentrate on the information-theoretic zero-knowledge proofs which are of special interest in both practical setting (for example, they are used to achieve absolute security of a task) and in theoretical setting (for example, our best way to prove that a language L is not NP-complete is to show the existence of such a zero-knowledge proof for it.) In all such proofs, interaction is the crucial resource, as prover and verifier exchange messages in rounds. The fundamental problem here is whether the number of rounds induces a hierarchy. That is, can we prove more languages in zero knowledge given more rounds? Quadratic residuosity and graph isomorphism are classic problems and the canonical examples of zero-knowledge languages. However, despite much research effort, all previous zero-knowledge proofs for them required either unproven complexity assumptions or an unbounded number of rounds of message exchange. For both (and similar) languages, we exhibit zero-knowledge proofs that require only five rounds of interaction and no unproven assumptions.
comment: Appeared in Proceedings of 22nd annual ACM Symposium on Theory of Computing (STOC-90)
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |