Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ZERO-KNOWLEDGE INTERACTIVE PROOFS:
Reports tagged with Zero-Knowledge Interactive Proofs:
TR96-054 | 2nd November 1996
Oded Goldreich

#### The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

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 ... more >>>

TR98-006 | 27th January 1998
Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano

#### The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

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 ... more >>>

TR14-097 | 31st July 2014
Oded Goldreich, Liav Teichner

#### Super-Perfect Zero-Knowledge Proofs

Revisions: 1

We initiate a study of super-perfect zero-knowledge proof systems.
Loosely speaking, these are proof systems for which the interaction can be perfectly simulated in strict probabilistic polynomial-time.
In contrast, the standard definition of perfect zero-knowledge only requires that the interaction can be perfectly simulated
by a strict probabilistic polynomial-time that ... more >>>

ISSN 1433-8092 | Imprint