Paper 2014/623

Privacy with Imperfect Randomness

Yevgeniy Dodis and Yanqing Yao

Abstract

We revisit the impossibility of a variety of cryptographic tasks including privacy and differential privacy with imperfect randomness. For traditional notions of privacy, such as security of encryption, commitment or secret sharing schemes, dramatic impossibility results are known [MP90,DOPS04]. In fact, they are true even if the imperfect source is modeled as a seemingly very "nice and friendly" Santha-Vazirani (SV) source. Moreover, Bosley and Dodis [BD07] gave strong evidence that many traditional privacy tasks (e.g., encryption) inherently require an "extractable" source of randomness. 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.