Loading...
Please wait, while we are loading the content...
Similar Documents
Differential privacy with imperfect randomness (2012).
| Content Provider | CiteSeerX |
|---|---|
| Author | Dodis, Yevgeniy López-Alt, Adriana Vadhan, Salil Mironov, Ilya |
| Abstract | In this work we revisit the question of basing cryptography 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 |
| File Format | |
| Publisher Date | 2012-01-01 |
| Access Restriction | Open |
| Subject Keyword | Differential Privacy Imperfect Randomness Santha-vazirani Source Traditional Privacy Notion Extractable Source Next Bit Specific Non-extractable Source Small Bias Prior Bit Impossibility Result Private Mechanism Fresh Entropy Recent Notion Similar Negative Result Uniform Bit Secret Key Traditional Privacy Arbitrary Low Sensitivity Function Surprising Separation |
| Content Type | Text |
