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.

Time and Place

6 May 2008 (Tuesday) at 1630 hrs
Gates 4B (opposite 490)