Paper 1996/014 Original: eprint.iacr.org/1996/014 ↗
The Graph Clustering Problem has a Perfect Zero-Knowledge Proof
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.
Metadata
- Available format(s)
PDF- Publication info
- Preprint.
- History
- 1996-11-03: last updated
- 1996-11-03: published
- Short URL
- https://ia.cr/1996/014
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:1996/014,
author = {Oded Goldreich},
title = {The Graph Clustering Problem has a Perfect Zero-Knowledge Proof},
howpublished = {Cryptology {ePrint} Archive, Paper 1996/014},
year = {1996},
url = {https://eprint.iacr.org/1996/014}
}