Show simple item record

dc.contributor.authorDodis, Yevgeniy
dc.contributor.authorLópez-Alt, Adriana
dc.contributor.authorMironov, Ilya
dc.contributor.authorVadhan, Salil P.
dc.date.accessioned2014-02-11T13:05:49Z
dc.date.issued2012
dc.identifier.citationDodis, Yevgeniy, Adriana López-Alt, Ilya Mironov, and Salil Vadhan. 2012. "Differential Privacy with Imperfect Randomness." Lecture Notes in Computer Science 7417: 497-516. Presented at the 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Also appears in Advances in Cryptology – CRYPTO 2012. Springer-Verlag. doi:10.1007/978-3-642-32009-5_29. http://dx.doi.org/10.1007/978-3-642-32009-5_29.en_US
dc.identifier.isbn978-3-642-32009-5en_US
dc.identifier.isbn978-3-642-32008-8en_US
dc.identifier.issn0302-9743en_US
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:11688791
dc.description.abstractIn this work we revisit the question of basing cryptogra- phy on imperfect randomness. Bosley and Dodis (TCC’07) showed that if a source of randomness R is “good enough” to generate a secret key capable of encrypting k bits, then one can deterministically extract nearly k almost uniform bits from R, suggesting that traditional privacy notions (namely, indistinguishability of encryption) requires an “extractable” source of randomness. Other, even stronger impossibility results are known for achieving privacy under specific “non-extractable” sources of randomness, such as the γ-Santha-Vazirani (SV) source, where each next bit has fresh entropy, but is allowed to have a small bias γ < 1 (possibly depending on prior bits). We ask whether similar negative results also hold for a more recent notion of privacy called differential privacy (Dwork et al., TCC’06), concentrating, in particular, on achieving differential privacy with the Santha-Vazirani source. We show that the answer is no. Specifically, we give a differentially private mechanism for approximating arbitrary “low sensitivity” functions that works even with randomness coming from a γ-Santha-Vazirani source, for any γ < 1. This provides a somewhat surprising “separation” between traditional privacy and differential privacy with respect to imperfect randomness. Interestingly, the design of our mechanism is quite different from the traditional “additive-noise” mechanisms (e.g., Laplace mechanism) successfully utilized to achieve differential privacy with perfect randomness. Indeed, we show that any (non-trivial) “SV-robust” mechanism for our problem requires a demanding property called consistent sampling, which is strictly stronger than differential privacy, and cannot be satisfied by any additive-noise mechanism.en_US
dc.description.sponsorshipEngineering and Applied Sciencesen_US
dc.language.isoen_USen_US
dc.publisherSpringer Verlagen_US
dc.relation.isversionofdoi:10.1007/978-3-642-32009-5_29en_US
dash.licenseOAP
dc.titleDifferential Privacy with Imperfect Randomnessen_US
dc.typeConference Paperen_US
dc.description.versionAccepted Manuscripten_US
dc.relation.journalLecture Notes in Computer Scienceen_US
dash.depositing.authorVadhan, Salil P.
dc.date.available2014-02-11T13:05:49Z
dc.relation.bookAdvances in Cryptology – CRYPTO 2012en_US
dc.identifier.doi10.1007/978-3-642-32009-5_29*
workflow.legacycommentsFAR (metadata complicated)en_US
dash.contributor.affiliatedVadhan, Salil


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record