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 gamma-Santha-Vazirani source, for any gamma<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 (accurate and private) "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.
Category / Keywords: Publication Info: An extended abstract of this work appears in the proceedings of CRYPTO 2012. This is the full version. Date: received 31 Jul 2012 Contact author: lopez at cs nyu edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20120805:174903 (All versions of this report) Short URL: ia.cr/2012/435