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.
Keywords: Perfect Zero-Knowledge Interactive Proofs, Graph Isomorphism.
comment: received November 3rd, 1996. See improvement in record 98-02.
contact author: oded@theory.lcs.mit.edu
Fetch PostScript file of the full paper.