Information Security and Cryptography Research Group

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

Ueli Maurer

Advances in Cryptology — CRYPTO '92, Lecture Notes in Computer Science, Springer-Verlag, vol. 740, pp. 461–470, Aug 1993, Final version: [Maurer93a].

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 = 30$ to receive the same bits much more reliably with bit error probability $\epsilon_E \ll \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.

BibTeX Citation

@inproceedings{Maurer92g,
author       = {Ueli Maurer},
title        = {Protocols for Secret Key Agreement by Public Discussion Based on Common Information},
booktitle    = {Advances in Cryptology --- CRYPTO~'92},
pages        = 461--470,
series       = {Lecture Notes in Computer Science},
volume       = 740,
year         = 1993,
month        = 8,
note         = {Final version: \cite{Maurer93a}},
publisher    = {Springer-Verlag},
}