@conference {634258,
	title = {Differential privacy with imperfect randomness},
	booktitle = {Ran Canetti and Rei Safavi-Naini, editors, Proceedings of the 32nd International Cryptology Conference (CRYPTO {\textquoteleft}12), Lecture Notes on Computer Science},
	volume = {7417},
	year = {2012},
	pages = {497-516},
	publisher = {Springer-Verlag},
	organization = {Springer-Verlag},
	abstract = {
	In this work we revisit the question of basing cryptography on imperfect randomness. Bosley and Dodis (TCC{\textquoteright}07) showed that if a source of randomness\&nbsp;\(\mathcal{R}\)\&nbsp;is {\textquotedblleft}good enough{\textquotedblright} to generate a secret key capable of encrypting\&nbsp;\(k\)\&nbsp;bits, then one can deterministically extract nearly\&nbsp;\(k\)\&nbsp;almost uniform bits from\&nbsp;\(\mathcal{R}\), suggesting that traditional privacy notions (namely, indistinguishability of encryption) requires an {\textquotedblleft}extractable{\textquotedblright} source of randomness. Other, even stronger impossibility results are known for achieving privacy under specific {\textquotedblleft}non-extractable{\textquotedblright} sources of randomness, such as the\&nbsp;\(\gamma\)-Santha-Vazirani (SV) source, where each next bit has fresh entropy, but is allowed to have a small bias\&nbsp;\(\gamma \&lt; 1\) (possibly depending on prior bits).



	We ask whether similar negative results also hold for a more recent notion of privacy called\&nbsp;differential privacy\&nbsp;(Dwork et al., TCC{\textquoteright}06), concentrating, in particular, on achieving differential privacy with the Santha-Vazirani source. We show that the answer is\&nbsp;no. Specifically, we give a differentially private mechanism for approximating arbitrary {\textquotedblleft}low sensitivity{\textquotedblright} functions that works even with randomness coming from a \(\gamma\)-Santha-Vazirani source, for any\&nbsp;\(\gamma \&lt; 1\). This provides a somewhat surprising {\textquotedblleft}separation{\textquotedblright} between traditional privacy and differential privacy with respect to imperfect randomness.



	Interestingly, the design of our mechanism is quite different from the traditional {\textquotedblleft}additive-noise{\textquotedblright} mechanisms (e.g., Laplace mechanism) successfully utilized to achieve differential privacy with perfect randomness. Indeed, we show that\&nbsp;any\&nbsp;(non-trivial) {\textquotedblleft}SV-robust{\textquotedblright} mechanism for our problem requires a demanding property called\&nbsp;consistent sampling, which is strictly stronger than differential privacy, and cannot be satisfied by any additive-noise mechanism.

},
	url = {https://link.springer.com/chapter/10.1007/978-3-642-32009-5_29},
	author = {Yevgeniy Dodis and Adriana L{\'o}pez-Alt and Ilya Mironov and Salil Vadhan}
}
