**
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 |