Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK
MetadataShow full item record
CitationGoldreich, 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.
AbstractWe 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.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:4728399
- FAS Scholarly Articles