International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

Authors:
A. De Santis
G. Di Crescenzo
O. Goldreich
G. Persiano.
Download:
URL: http://eprint.iacr.org/1998/002
Search ePrint
Search Google
Abstract: The input to the Graph Clustering Problem consists of a sequence of integers $m_1,...,m_t$ and a sequence of $\sum_{i=1}^{t}m_i$ graphs. The question is whether the equivalence classes, under the graph isomorphism relation, of the input graphs have sizes which match the input sequence of integers. In this note we show that this problem has a (perfect) zero-knowledge interactive proof system. This result improves over <a href="http:../1996/96-14.html">record 96-14</a>, where a parametrized (by the sequence of integers) version of the problem was studied.
BibTeX
@misc{eprint-1998-11299,
  title={The Graph Clustering Problem has a Perfect Zero-Knowledge Proof},
  booktitle={IACR Eprint archive},
  keywords={Graph Isomorphism, Zero-Knowledge Interactive Proofs.},
  url={http://eprint.iacr.org/1998/002},
  note={Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. oded@theory.lcs.mit.edu 10500 received January 27th, 1998.},
  author={A. De Santis and G. Di Crescenzo and O. Goldreich and G. Persiano.},
  year=1998
}