The common interpretation of these negative results is that traditional privacy is impossible even with "very structured" imperfect sources. Somewhat surprisingly, Dodis et al. [DLMV12] put a slight dent in this belief, by showing that non-trivial *differential* privacy is possible with SV sources. This suggested a qualitative gap between traditional and differential privacy, and left open the question if differential privacy is possible with more realistic (i.e., less structured) sources than the SV sources.
Motivated by solving this question, we introduce a new, modular framework for showing strong impossibility results for (either traditional or differential) privacy under a *general* imperfect source R. In particular, we introduce natural and easy-to-understand concepts of expressiveness and separability of a given imperfect source R, and show the following results:
(1) Low levels of expressiveness generically imply strong impossibility results for both traditional and *differential* privacy. (2) Separability implies expressiveness; NON-separability is equivalent to ``weak bit extraction''. (3) While the separability of some concrete (e.g., SV) sources R was implicitly known, we show new separability results for several important sources, including general "block sources".
As direct corollaries of these general results, we get the following corollaries:
(1) Existing, but quantitatively improved, impossibility results for traditional privacy, but under a wider variety of sources R. (2) First impossibility results for differential privacy. Although, unsurprisingly, these results (barely) miss the highly structured SV sources, they come back *extremely quickly* once the source becomes slightly more realistic (e.g., a realistic "block source"). (3) Any imperfect source allowing (either traditional or differential) privacy admits a certain type of deterministic bit extraction. (This result is incomparable to the result of [BD07].)
Overall, we believe our results provide an intuitive, modular and unified picture elucidating the (im)possibility of privacy with general imperfect sources.Category / Keywords: imperfect randomness, entropy sources, Santha-Vazirani sources, block sources, Bias-Control Limited sources, randomness extraction, privacy, differential privacy Date: received 13 Aug 2014, last revised 6 Feb 2015 Contact author: dodis at cs nyu edu, yaoyanqing1984@gmail com Available format(s): PDF | BibTeX Citation Version: 20150207:065436 (All versions of this report) Short URL: ia.cr/2014/623 Discussion forum: Show discussion | Start new discussion