On the Randomness Requirements for Privacy

Candidate: Carl Bosley

Advisor: Yevgeniy Dodis

Most cryptographic primitives require randomness (for example, to
generate 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 achievable 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 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 technique also extends to related primitives which
are sufficiently binding and hiding, including computationally secure
commitments and public-key encryption.

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 - log log 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".