We completely resolve this question for the case of (information-theoretic) private-key encryption, where parties wish to encrypt a b-bit value using a 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. Further, the restriction that b>log n is nearly tight: there exist sources S allowing one to perfectly encrypt (log n - loglog n) bits, but not to deterministically extract even a single slightly unbiased bit.
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.
Category / Keywords: foundations / encryption, extraction, imperfect random sources, inherency of true randomness for cryptography Publication Info: TCC 2007 Date: received 19 Aug 2006, last revised 28 Nov 2006 Contact author: dodis at cs nyu edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20061128:185729 (All versions of this report) Discussion forum: Show discussion | Start new discussion