# Tight Security Proofs for the Bounded-Storage Model

## Stefan Dziembowski and Ueli Maurer

```
```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\gg|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 give the first fully satisfactory security proof 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. This solves the main open problem of both Maurer's 1992 paper
which introduced the bounded-storage model and of the recent paper by
Aumann, Ding, and Rabin. In fact, we prove that $s/t$ can be arbitrarily
close to $1$ and hence the storage bound is essentially optimal.