Differential Privacy with
Imperfect Randomness
Yevgeniy Dodis (NYU)
Adriana
Lopez-Alt (NYU)
Ilya Mironov (Microsoft Research)
Salil Vadhan (
Abstract:
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 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 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 gamma-Santha-Vazirani (SV) source, where each
next bit has fresh entropy, but is allowed to have a small bias gamma< 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 gamma-Santha-Vazirani
source, for any gamma<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.,