Publication: Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK
Open/View Files
Date
1999
Authors
Published Version
Journal Title
Journal ISSN
Volume Title
Publisher
IEEE Computer Society Press
The Harvard community has made this article openly available. Please share how this access benefits you.
Citation
Goldreich, Oded, and Salil Vadhan. 1999. Comparing entropies in statistical zero knowledge with applications to the structure of SZK. In Proceedings of the 14th annual IEEE Conference on Computational Complexity (CCC '99), May 4-6, 1999, Atlanta, GA, 54-73. Washington, DC: IEEE Computer Society Press.
Research Data
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.
Description
Other Available Sources
Keywords
Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material (LAA), as set forth at Terms of Service