Comparing Entropies in Statistical ZeroKnowledge with Applications to
the Structure of SZK
Oded Goldreich
and Salil Vadhan
Abstract
We consider the following (promise) problem, denoted ED (for Entropy Difference):
The input is a pairs of circuits, and YES instances (resp., NO instances)
are such pairs in which the first (resp., second) circuit generates a distribution
with noticeably higher entropy.
On one hand we show that any language having a (honestverifier) statistical
zeroknowledge proof is Karpreducible to ED. On the other hand, we present
a publiccoin (honestverifier) statistical zeroknowledge proof for ED.
Thus, we obtain an alternative proof of Okamoto's result by which HVSZK
(i.e., HonestVerifier Statistical ZeroKnowledge) equals publiccoin HVSZK.
The new proof is much simpler than the original one. The above also yields
a trivial proof that HVSZK is closed under complementation (since ED easily
reduces to its complement). Among the new results obtained is an equivalence
of a weak notion of statistical zeroknowledge to the standard one.
Versions

Cryptology ePrint Archive, Record 1998/026.

Electronic Colloquium on Computational Complexity TR98063.

In Proceedings of the 14th Annual IEEE Conference on Computational Complexity,
pp. 5473, Atlanta, GA, May 1999. [postscript][compressed
postscript]
[back
to Salil Vadhan's research interests]