__
TR98-063 | 4th November 1998 00:00
__

#### Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK

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