Optimal randomizer efficiency in the bounded-storage model

In the bounded-storage model for information-theoretically secure encryption and key-agreement one can prove the security of a cipher based on the sole assumption that the adversary's storage capacity is bounded, say by s bits, even if her computational power is unlimited. Assume that a random t-bit string R is either publicly available (e.g., the signal of a deep-space radio source) or broadcast by one of the legitimate parties. If s < t, the adversary can store only partial information about R. The legitimate sender Alice and receiver Bob, sharing a short secret key K initially, can therefore potentially generate a very long n-bit one-time pad X with n ≫ |K| about which the adversary has essentially no information. All previous results in the bounded-storage model were partial or far from optimal, for one of the following reasons: either the secret key K had to be longer than the derived one-time pad (n < |K|),or t had to be extremely large (t > ns), or the adversary was assumed to be able to store only s actual bits of R rather than arbitrary s bits of information about R, or the adversary received a non-negligible amount of information about X. In this paper we prove the first non-restricted security result in the bounded-storage model: K is short, X is very long, and t needs to be only moderately larger than s + n. In fact, s/t can be arbitrarily close to 1 and hence the storage bound is essentially optimal. The security can be proved also if R is not uniformly random, provided that the min-entropy of R is sufficiently greater than s.