Welcome to the resource topic for
**1998/002**

**Title:**

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

**Authors:**
A. De Santis, G. Di Crescenzo, O. Goldreich, G. Persiano.

**Abstract:**

The input to the Graph Clustering Problem

consists of a sequence of integers m_1,...,m_t

and a sequence of \sum_{i=1}^{t}m_i graphs.

The question is whether the equivalence classes,

under the graph isomorphism relation,

of the input graphs have sizes which match the input sequence of integers.

In this note we show that this problem has a (perfect) zero-knowledge

interactive proof system.

This result improves over record 96-14,

where a parametrized (by the sequence of integers)

version of the problem was studied.

**ePrint:**
https://eprint.iacr.org/1998/002

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .