Information Security and Cryptography Research Group

Optimal Randomizer Efficiency in the Bounded-Storage Model

Stefan Dziembowski and Ueli Maurer

Journal of Cryptology, vol. 17, no. 1, pp. 5–26, Jan 2004, Conference version appeared in Proc. of STOC 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\gg|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$.

BibTeX Citation

    author       = {Stefan Dziembowski and Ueli Maurer},
    title        = {Optimal Randomizer Efficiency in the Bounded-Storage Model},
    journal      = {Journal of Cryptology},
    pages        = {5--26},
    number       = {1},
    volume       = {17},
    year         = {2004},
    month        = {1},
    note         = {Conference version appeared in Proc.~of STOC 2002.},

Files and Links