Paper 1998/002

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

A. De Santis, G. Di Crescenzo, O. Goldreich, and G. Persiano.

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.

Metadata
Available format(s)
PS
Publication info
Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Keywords
Graph IsomorphismZero-Knowledge Interactive Proofs.
Contact author(s)
oded @ theory lcs mit edu
History
1998-01-27: received
Short URL
https://ia.cr/1998/002
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:1998/002,
      author = {A.  De Santis and G.  Di Crescenzo and O.  Goldreich and G.  Persiano.},
      title = {The Graph Clustering Problem has a Perfect Zero-Knowledge Proof},
      howpublished = {Cryptology ePrint Archive, Paper 1998/002},
      year = {1998},
      note = {\url{https://eprint.iacr.org/1998/002}},
      url = {https://eprint.iacr.org/1998/002}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.