Tight Security Proofs for the Bounded-Storage Model

Stefan Dziembowski and Ueli Maurer

Proc. 34th ACM Symposium on Theory of Computing — STOC 2002, ACM, pp. 341–350, May 2002.

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, 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 > n s$ ), 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.

BibTeX Citation

@inproceedings{DziMau02,
    author       = {Stefan Dziembowski and Ueli Maurer},
    title        = {Tight Security Proofs for the Bounded-Storage Model},
    booktitle    = {Proc.~34th ACM Symposium on Theory of Computing --- STOC 2002},
    pages        = {341--350},
    year         = {2002},
    month        = {5},
    publisher    = {ACM},
}