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