The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

Oded Goldreich

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

Metadata

Available format(s): PS
Publication info: Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Contact author(s): oded @ theory lcs mit edu
History: 1996-11-03: received
Short URL: https://ia.cr/1996/014
License: CC BY

BibTeX

@misc{cryptoeprint:1996/014,
      author = {Oded Goldreich},
      title = {The Graph Clustering Problem has a Perfect Zero-Knowledge Proof},
      howpublished = {Cryptology {ePrint} Archive, Paper 1996/014},
      year = {1996},
      url = {https://eprint.iacr.org/1996/014}
}