Paper 2006/283
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 (informationtheoretic) privatekey encryption, where parties wish to encrypt a bbit value using a shared secret key sampled from some imperfect source of randomness S. Our main result shows that if such nbit 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 *onetime pad scheme is essentially universal*. Our technique also extends to related *computational* primitives which are perfectlybinding, such as perfectlybinding commitment and computationally secure private or publickey encryption, showing the necessity to efficiently extract almost b *pseudorandom* bits.
Metadata
 Available format(s)
 PDF PS
 Category
 Foundations
 Publication info
 Published elsewhere. TCC 2007
 Keywords
 encryptionextractionimperfect random sources
 Contact author(s)
 dodis @ cs nyu edu
 History
 20061128: last of 2 revisions
 20060820: received
 See all versions
 Short URL
 https://ia.cr/2006/283
 License

CC BY
BibTeX
@misc{cryptoeprint:2006/283, author = {Carl Bosley and Yevgeniy Dodis}, title = {Does Privacy Require True Randomness?}, howpublished = {Cryptology ePrint Archive, Paper 2006/283}, year = {2006}, note = {\url{https://eprint.iacr.org/2006/283}}, url = {https://eprint.iacr.org/2006/283} }