International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Oded Goldreich
Salil P. Vadhan
Download:
URL: http://eprint.iacr.org/1998/026
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-1998-11322,
  title={Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK},
  booktitle={IACR Eprint archive},
  keywords={Zero-Knowledge, Universal Hashing},
  url={http://eprint.iacr.org/1998/026},
  note={Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. salil@theory.lcs.mit.edu 10500 received Dec 24th, 1998.},
  author={Oded Goldreich and Salil P. Vadhan},
  year=1998
}