## Does Privacy Require True Randomness?

### Yevgeniy Dodis, New York University and Harvard University

**Abstract:**
All known techniques for achieving privacy seem to fundamentally
require (nearly) perfect randomness. We ask the question whether
this is just a coincidence, or, perhaps, privacy inherently
requires true randomness?

We resolve this question for the case of (information-theoretic) private-key encryption, where parties wish to encrypt a b-bit value using an n-bit shared secret key sampled from some imperfect source of randomness S. Our main result shows that if such n-bit source S allows for a secure encryption of b bits, where b > log n, then one can deterministically extract nearly b almost perfect random bits from S. Moreover, the restriction that b > log n is nearly tight.

Hence, to a large extent, true randomness is inherent for
encryption: either the key length must be exponential in the
message length b, or one can deterministically extract nearly b
almost unbiased random bits from the key. In particular, **the
one-time pad scheme is essentially "universal"**.

Our technique also extends to related **computational**
primitives which are "perfectly-binding", such as
perfectly-binding commitment and computationally secure private-
or public-key encryption, showing the necessity to
**efficiently** extract almost b **pseudorandom** bits.

Joint work with Carl Bosley.

http://people.csail.mit.edu/dodis/ps/enc-ext.ps