CryptoDB
The Graph Clustering Problem has a Perfect Zero-Knowledge Proof
Authors: | |
---|---|
Download: | |
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 }