dc.contributor.author | Goldreich, Oded | |
dc.contributor.author | Vadhan, Salil P. | |
dc.date.accessioned | 2011-02-18T19:52:27Z | |
dc.date.issued | 1999 | |
dc.identifier.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. | en_US |
dc.identifier.isbn | 0-7695-0075-7 | en_US |
dc.identifier.uri | http://nrs.harvard.edu/urn-3:HUL.InstRepos:4728399 | |
dc.description.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. | en_US |
dc.description.sponsorship | Engineering and Applied Sciences | en_US |
dc.language.iso | en_US | en_US |
dc.publisher | IEEE Computer Society Press | en_US |
dc.relation.isversionof | http://dx.doi.org/10.1109/CCC.1999.766262 | en_US |
dash.license | LAA | |
dc.title | Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK | en_US |
dc.type | Conference Paper | en_US |
dc.description.version | Author's Original | en_US |
dash.depositing.author | Vadhan, Salil P. | |
dc.date.available | 2011-02-18T19:52:27Z | |
dc.identifier.doi | 10.1109/CCC.1999.766262 | * |
dash.contributor.affiliated | Vadhan, Salil | |