**Does Privacy Require True Randomness?**

*Carl Bosley and Yevgeniy Dodis*

**Abstract: **Most cryptographic primitives require randomness (for example, to
generate their secret keys). Usually, one assumes that perfect
randomness is available, but, conceivably, such primitives might be
built under weaker, more realistic assumptions. This is known to be
true for many authentication applications, when entropy alone is
typically sufficient. In contrast, 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 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

[ Cryptology ePrint archive ]