Honest Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge
Oded Goldreich
,
Amit
Sahai , and Salil Vadhan
Abstract
We show how to transform any interactive proof system which is statistical
zero-knowledge with respect to the honest-verifier, into a proof system
which is statistical zero-knowledge with respect to any verifier. This
is done by limiting the behavior of potentially cheating verifiers, without
using computational assumptions or even referring to the complexity of
such verifier strategies. (Previous transformations have either relied
on computational assumptions or were applicable only to constant-round
public-coin proof systems.)
Our transformation also applies to public-coin (aka Arthur-Merlin) computational
zero-knowledge proofs: We transform any Arthur-Merlin proof system which
is computational zero-knowledge with respect to the honest-verifier, into
an Arthur-Merlin proof system which is computational zero-knowledge with
respect to any probabilistic polynomial-time verifier.
A crucial ingredient in our analysis is a new lemma regarding 2-universal
hashing functions.
Versions
[ back to
Salil Vadhan's research interests ]