(MATH) 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 $xi; 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, thus at first glance apparently contradicting Shannon's bound on the key size of a perfect cipher.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 in fact to be longer than the derived one-time pad, or  t  had to be extremely large ( t ρ ns ), or the adversary was assumed to be able to store only actual bits of  R  rather than arbitrary  s  bits of information about  R , or the adversary could obtain a non-negligible amount of information about  X .In this paper we prove the first non-restricted security result in the bounded-storage model, exploiting the full potential of the model:  K  is short,  X  is very long (e.g. gigabytes),  t  needs to be only moderately larger than  s , and the security proof is optimally strong. In fact, we prove that  s/t  can be arbitrarily close to  1  and hence the storage bound is essentially optimal.
['Stefan Dziembowski', 'Ueli Maurer']
Tight security proofs for the bounded-storage model