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

DSpace/Manakin Repository

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

Citable link to this page

. . . . . .

Title: Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK
Author: Goldreich, Oded; Vadhan, Salil P.

Note: Order does not necessarily reflect citation order of authors.

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.
Full Text & Related Files:
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.
Published Version: http://dx.doi.org/10.1109/CCC.1999.766262
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:4728399

Show full Dublin Core record

This item appears in the following Collection(s)

  • FAS Scholarly Articles [7594]
    Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
 
 

Search DASH


Advanced Search
 
 

Submitters