Cryptology ePrint Archive: Report 1996/014

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