**The Graph Clustering Problem has a Perfect Zero-Knowledge Proof**

*A. De Santis, G. Di Crescenzo, O. Goldreich, and 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 <a href="http:../1996/96-14.html">record 96-14</a>, where a parametrized (by the sequence of integers) version of the problem was studied.

**Category / Keywords: **Graph Isomorphism, Zero-Knowledge Interactive Proofs.

**Publication Info: **Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.

**Date: **received January 27th, 1998.

**Contact author: **oded at theory lcs mit edu

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]