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)
PDF 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/1996/014}},
      url = {https://eprint.iacr.org/1996/014}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.