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   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.
bounded-storage model min-entropy unconditional security one-time pad information theory