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

Oded Goldreich; Salil Vadhan

Paper 1998/026 Original: eprint.iacr.org/1998/026 ↗

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

Oded Goldreich

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.

Metadata

Available format(s): PDF
Publication info: Preprint.
History: 1998-12-24: last updated; 1998-12-24: published
Short URL: https://ia.cr/1998/026
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:1998/026,
      author = {Oded Goldreich and Salil Vadhan},
      title = {Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK},
      howpublished = {Cryptology {ePrint} Archive, Paper 1998/026},
      year = {1998},
      url = {https://eprint.iacr.org/1998/026}
}