International Association
for Cryptologic Research

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. The SV source outputs a sequence of bits r_1,r_2,..., where each r_i has almost 1 full bit of fresh entropy conditioned on the previous bits r_1,...,r_{i-1}. 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 abstract and generalize prior techniques for showing impossibility results for achieving privacy with various imperfect sources of randomness. In particular, we introduce the concepts of separability and expressivity of a given imperfect source as a measure of its \"imperfectness\", and show the

following results:

(1) Separability implies expressivity;

(2) Low levels of expressivity (and, thus, separability) generically imply strong impossibility results for both traditional and *differential* privacy;

(3) Existing (and quantitatively improved!) impossibility results for traditional privacy with respect to known imperfect sources easily follow as corollaries of our unified framework; New results follow equally easily.

(4) Although, unsurprisingly, our new impossibility results for differential privacy (barely) miss the highly structured SV sources, they come back *extremely quickly* once the source becomes slightly more realistic. E.g., if a small number of bits r_i can be fully determined by the previous bits;

(5) 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, our results unify and strengthen the belief that, for the most part, privacy with imperfect randomness is impossible, unless the source is (almost) deterministically extractable.