Adriana Lopez-Alt

Adriana will begin by briefly describing the result of Dodis et al.
(DOPS'04 - FOCS 2004), who showed that Santha-Vazirani (SV) sources
(where each next bit has fresh entropy, but is allowed to have a small
bias \gamma< 1 possibly depending on prior bits) are not sufficient
for building computationally secure encryption (even of a single bit),
and, if fact, essentially any other cryptographic task involving
"privacy" (e.g.,  commitment, zero-knowledge, secret
sharing, etc.). She will then describe recent results from her paper
in CRYPTO 2012. 


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-SV source.

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., Laplace
mechanism) successfully utilized to achieve differential privacy with
perfect randomness. Indeed, we show that any (accurate and private)
"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

Joint work with Yevgeniy Dodis, Ilya Mironov, and Salil Vadhan. 

Full version can be found at:  http://eprint.iacr.org/2012/435