Comparing Entropies in Statistical Zero-Knowledge 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 (honest-verifier) statistical
zero-knowledge proof is Karp-reducible to ED. On the other hand, we present
a public-coin (honest-verifier) statistical zero-knowledge proof for ED.
Thus, we obtain an alternative proof of Okamoto's result by which HVSZK
(i.e., Honest-Verifier Statistical Zero-Knowledge) equals public-coin 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 zero-knowledge to the standard one.
Versions
-
Cryptology ePrint Archive, Record 1998/026.
-
Electronic Colloquium on Computational Complexity TR98-063.
-
In Proceedings of the 14th Annual IEEE Conference on Computational Complexity,
pp. 54-73, Atlanta, GA, May 1999. [postscript][compressed
postscript]
[back
to Salil Vadhan's research interests]