ECCC-Report TR98-006https://eccc.weizmann.ac.il/report/1998/006Comments and Revisions published for TR98-006en-usWed, 28 Jan 1998 09:31:03 +0200
Paper TR98-006
| The Graph Clustering Problem has a Perfect Zero-Knowledge Proof |
Alfredo De Santis,
Giovanni Di Crescenzo,
Oded Goldreich,
Giuseppe Persiano
https://eccc.weizmann.ac.il/report/1998/006
The input to the {\em 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 ECCC TR96-054,
where a parametrized (by the sequence of integers)
version of the problem was studied.
Wed, 28 Jan 1998 09:31:03 +0200https://eccc.weizmann.ac.il/report/1998/006