Secret Key Agreement by Public Discussion

Ueli Maurer

IEEE Transactions on Information Theory, vol. 39, no. 3, pp. 733–742, May 1993, Preliminary version: [Maurer92g].

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_{X Y Z}$ , 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_{X Y Z}$ are presented. Lower bounds on the rate $H (S) / N$ (as $N \to \infty$ ) are derived for the case where $X = [X_{1}, \dots, X_{N}]$ , $Y = [Y_{1}, \dots, Y_{N}]$ and $Z = [Z_{1}, \dots, Z_{N}]$ result from $N$ independent executions of a random experiment generating $X_{i}, Y_{i}$ and $Z_{i}$ , for $i = 1, \dots, 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.

BibTeX Citation

@article{Maurer93a,
    author       = {Ueli Maurer},
    title        = {Secret Key Agreement by Public Discussion},
    journal      = {IEEE Transactions on Information Theory},
    pages        = {733--742},
    number       = {3},
    volume       = {39},
    year         = {1993},
    month        = {5},
    note         = {Preliminary version: \cite{Maurer92g}},
}