Welcome to the resource topic for
**1996/014**

**Title:**

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

**Authors:**
Oded Goldreich

**Abstract:**

The Graph Clustering Problem is parameterized by a sequence

of positive integers, m_1,...,m_t.

The input is a sequence of \sum_{i=1}^{t}m_i graphs,

and the question is whether the equivalence classes

under the graph isomorphism relation have sizes which match

the sequence of parameters.

In this note

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

interactive proof system.

**ePrint:**
https://eprint.iacr.org/1996/014

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 .