Differential Privacy with Imperfect Randomness

In this work we revisit the question of basing cryptography on imperfect randomness. Bosley and Dodis (TCC’07) showed that if a source of randomness

$\mathcal{R}$

is “good enough” to generate a secret key capable of encrypting

k

bits, then one can deterministically extract nearly

k

almost uniform bits from

$\mathcal{R}$

, suggesting that traditional privacy notions (namely, indistinguishability of encryption) requires an “extractable” source of randomness. Other, even stronger impossibility results are known for achieving privacy under specific “non-extractable” sources of randomness, such as the

γ

-Santha-Vazirani (SV) source, where each next bit has fresh entropy, but is allowed to have a small bias

γ

 < 1 (possibly depending on prior bits).

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

γ

-Santha-Vazirani source, for any

γ

 < 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

(non-trivial) “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.