Paper 2014/623

Privacy with Imperfect Randomness

Yevgeniy Dodis and Yanqing Yao


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.

Available format(s)
Publication info
Preprint. MINOR revision.
imperfect randomnessentropy sourcesSantha-Vazirani sourcesblock sourcesBias-Control Limited sourcesrandomness extractionprivacydifferential privacy
Contact author(s)
dodis @ cs nyu edu
yaoyanqing1984 @ gmail com
2015-02-07: last of 2 revisions
2014-08-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yevgeniy Dodis and Yanqing Yao},
      title = {Privacy with Imperfect Randomness},
      howpublished = {Cryptology ePrint Archive, Paper 2014/623},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.