Dissertation/Thesis Abstract

On the randomness requirements for privacy
by Bosley, Carl, Ph.D., New York University, 2010, 63; 3428033
Abstract (Summary)

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 [special characters omitted].

Our main result shows that if such n-bit source [special characters omitted] allows for a secure encryption of b bits, where b > log n, then one can deterministically extract nearly b almost perfect random bits from [special characters omitted]. Further, the restriction that b > log n is nearly tight: there exist sources [special characters omitted] 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 primitives which are sufficiently binding and hiding, including computationally secure commitments and public-key encryption.

Indexing (document details)
Advisor: Dodis, Yevgeniy
Commitee: Fazio, Nelly, Nicolosi, Antonio, Shasha, Dennis, Shoup, Victor
School: New York University
Department: Computer Science
School Location: United States -- New York
Source: DAI-B 72/01, Dissertation Abstracts International
Source Type: DISSERTATION
Subjects: Computer science
Keywords: Private key encryption, Randomness
Publication Number: 3428033
ISBN: 9781124332734