Differential Privacy with Imperfect Randomness
Source: New York University
Most cryptographic algorithms require randomness (for example, to generate their keys, probabilistically encrypt messages, etc.). Usually, one assumes that perfect randomness is available, but in many situations this assumption is problematic, and one has to deal with more realistic, "Imperfect" sources of randomness R. In this paper, the authors 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.