Show simple item record

dc.contributor.authorSahai, Amit
dc.contributor.authorVadhan, Salil P.
dc.date.accessioned2011-02-18T19:54:04Z
dc.date.issued2003
dc.identifier.citationSahai, Amit, and Salil Vadhan. 2003. A complete problem for statistical zero knowledge. Journal of the Association for Computing Machinery 50, no. 2: 196-249en_US
dc.identifier.issn0004-5411en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:4728406
dc.description.abstractWe present the first complete problem for SZK, the class of (promise) problems possessing statistical zero-knowledge proofs (against an honest verifier). The problem, called STATISTICAL DIFFERENCE, is to decide whether two efficiently samplable distributions are either statistically close or far apart. This gives a new characterization of SZK that makes no reference to interaction or zero knowledge. We propose the use of complete problems to unify and extend the study of statistical zero knowledge. To this end, we examine several consequences of our Completeness Theorem and its proof, such as: * A way to make every (honest-verifier) statistical zero-knowledge proof very communication efficient, with the prover sending only one bit to the verifier (to achieve soundness error 1/2). * Simpler proofs of many of the previously known results about statistical zero knowledge, such as the Fortnow and Aiello--Håstad upper bounds on the complexity of SZK and Okamoto's result that SZK is closed under complement. * Strong closure properties of SZK which amount to constructing statistical zero-knowledge proofs for complex assertions built out of simpler assertions already shown to be in SZK. * New results about the various measures of "knowledge complexity," including a collapse in the hierarchy corresponding to knowledge complexity in the "hint" sense. * Algorithms for manipulating the statistical difference between efficiently samplable distributions, including transformations which "polarize" and "reverse" the statistical relationship between a pair of distributions.en_US
dc.description.sponsorshipEngineering and Applied Sciencesen_US
dc.language.isoen_USen_US
dc.publisherAssociation for Computing Machineryen_US
dc.relation.isversionofhttp://doi.acm.org/10.1145/636865.636868en_US
dash.licenseLAA
dc.titleA Complete Problem for Statistical Zero Knowledgeen_US
dc.typeJournal Articleen_US
dc.description.versionAccepted Manuscripten_US
dc.relation.journalJournal of the Association for Computing Machineryen_US
dash.depositing.authorVadhan, Salil P.
dc.date.available2011-02-18T19:54:04Z
dc.identifier.doi10.1145/636865.636868*
dash.contributor.affiliatedVadhan, Salil


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record