ECCC-Report TR98-063https://eccc.weizmann.ac.il/report/1998/063Comments and Revisions published for TR98-063en-usThu, 05 Nov 1998 09:18:36 +0200
Paper TR98-063
| Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK |
Oded Goldreich,
Salil Vadhan
https://eccc.weizmann.ac.il/report/1998/063
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.
Thu, 05 Nov 1998 09:18:36 +0200https://eccc.weizmann.ac.il/report/1998/063