Paper 1998/002 Original: eprint.iacr.org/1998/002 ↗
The Graph Clustering Problem has a Perfect Zero-Knowledge Proof
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)
PDF- Publication info
- Preprint.
- History
- 1998-01-27: last updated
- 1998-01-27: published
- Short URL
- https://ia.cr/1998/002
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/1998/002}
}