# The Bare Bounded-storage Model: The Tight Bound on the Storage Requirement for Key Agreement

## Stefan Dziembowski and Ueli Maurer

```
```In the bounded-storage model (BSM) for information-theo\-retically
secure encryption and key-agreement one makes use of 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, execute a protocol, over an authenticated channel accessible to
Eve, to generate a secret key $K$ about which Eve has essentially no
information even if she has infinite computing power. The string $R$
is either assumed to be accessible to all parties or communicated
publicly from Alice to Bob. While in the BSM one often assumes that
Alice and Bob initially share a short secret key, and the goal of
the protocol is to generate a much longer key, we consider in this
paper the * bare*} BSM without any initially shared secret key. It
is proved that in the bare BSM, secret key agreement is impossible
unless Alice and Bob have themselves very high storage capacity,
namely $O(\sqrt{t})$. This proves the optimality of a scheme
proposed by Cachin and Maurer.