# Secret Key Agreement by Public Discussion

## Ueli Maurer

```
```The problem of generating a shared secret key $S$ by two parties
knowing random variables $X$ and $Y$, respectively, but not sharing a
secret key initially, is considered. An enemy who knows the random
variable $Z$, jointly distributed with $X$ and $Y$ according to some
probability distribution $P_{XYZ}$, and who receives all messages
exchanged by the two parties over a public channel, must not obtain
more than a negligible amount of information about $S$. Upper bounds on
$H(S)$ as a function of $P_{XYZ}$ are presented. Lower bounds on the
rate $H(S)/N$ (as $N\rightarrow\infty$) are derived for the case where
$X=[X_1\pp X_N]$, $Y=[Y_1\pp Y_N]$ and $Z=[Z_1\pp Z_N]$ result from $N$
independent executions of a random experiment generating $X_i,Y_i$ and
$Z_i$, for $i=1\pp N$. The results of this paper suggest to build
cryptographic systems that are provably secure against enemies with
unlimited computing power under realistic assumptions about the partial
independence of the noise on the involved communication channels.