# On Generating the Initial Key in the Bounded-Storage Model

## Stefan Dziembowski and Ueli Maurer

```
```In the bounded-storage model (BSM) for information-theoretically secure
encryption and key-agreement one uses a random string $R$ whose length
$t$ is greater than the assumed bound $s$ on the adversary Eve's storage
capacity. The legitimate parties Alice and Bob share a short initial
secret key $K$ which they use to select and combine certain bits of $R$
to obtain a derived key $X$ which is much longer than $K$. Eve can be
proved to obtain essentially no information about $X$ even if she has
infinite computing power and even if she learns $K$ after having performed
the storage operation and lost access to $R$.

This paper addresses the problem of generating the initial key $K$ and
makes two contributions. First, we prove that without such a key,
secret key agreement in the BSM is impossible unless Alice and Bob
have themselves very high storage capacity, thus proving the
optimality of a scheme proposed by Cachin and Maurer. Second, we
investigate the hybrid model where $K$ is generated by a
computationally secure key agreement protocol. The motivation for the
hybrid model is to achieve provable security under the sole assumption
that Eve cannot break the key agreement scheme * during*} the
storage phase, even if afterwards she may gain infinite computing
power (or at least be able to break the key agreement scheme). In
earlier work on the BSM, it was suggested such a hybrid scheme is
secure because if Eve has no information about $K$ during the storage
phase, then she has missed any opportunity to know anything about $X$,
even when later learning $K$. We show that this very intuitive and
apparently correct reasoning is false by giving an example of a secure
(according to the standard definition) computational key-agreement
scheme for which the BSM-scheme is nevertheless completely insecure.
One of the surprising consequences of this example is that existing
definitions for the computational security of key-agreement and
encryption are still too weak and therefore new, stronger definitions
are needed.