International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

Authors:
Oded Goldreich
Download:
URL: http://eprint.iacr.org/1996/014
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-1996-11280,
  title={The Graph Clustering Problem has a Perfect Zero-Knowledge Proof},
  booktitle={IACR Eprint archive},
  keywords={},
  url={http://eprint.iacr.org/1996/014},
  note={Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. oded@theory.lcs.mit.edu 10500 received November 3rd, 1996.},
  author={Oded Goldreich},
  year=1996
}