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

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

**Category / Keywords: **

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

**Date: **received November 3rd, 1996.

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

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

**Short URL: **ia.cr/1996/014

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

[ Cryptology ePrint archive ]