IACR paper details
Title  The Graph Clustering Problem has a Perfect ZeroKnowledge Proof 

Booktitle  IACR Eprint archive 

Pages  

Year  1998 

URL  http://eprint.iacr.org/1998/002 

Author  A. De Santis 

Author  G. Di Crescenzo 

Author  O. Goldreich 

Author  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) zeroknowledge
interactive proof system.
This result improves over record 9614,
where a parametrized (by the sequence of integers)
version of the problem was studied.


Search for the paper
@misc{eprint199811299,
title={The Graph Clustering Problem has a Perfect ZeroKnowledge Proof},
booktitle={IACR Eprint archive},
keywords={Graph Isomorphism, ZeroKnowledge 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
}
Download a complete BibTeX file.