# Protocols for Secret Key Agreement by Public Discussion Based on Common Information

## Ueli Maurer

```
```Consider the following scenario: Alice and Bob, two parties who
share no secret key initially but whose goal it is to generate a (large amount of)
information-theoretically secure (or unconditionally secure) shared secret key,
are connected only by an insecure public channel to which an eavesdropper Eve
has perfect (read) access. Moreover, there exists a satelite broadcasting
random bits at a very low signal power. Alice and Bob can receive these bits
with certain bit error probabilities $\epsilon_A$ and $\epsilon_B$,
respectively (e.g. $\epsilon_A = \epsilon_B = 30to receive the same bits much more reliably with bit error probability
$\epsilon_E \llt \epsilon_A, \epsilon_B$ (e.g. $\epsilon_E = 1errors on the three channels are assumed to occur at least partially
independently. Practical protocols are discussed by which Alice and Bob
can generate a secret key despite the facts that Eve possesses more
information than both of them and is assumed to have unlimited computational
resources as well as complete knowledge of the protocols.

The described scenario is a special case of a much more general setup in
which Alice, Bob and Eve are assumed to know random variables $X$, $Y$ and
$Z$ jointly distributed according to some probability distribution
$P_{XYZ}$, respectively. 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 of the involved communication channels.