Secret key agreement by public discussion from common information

The problem of generating a shared secret key S by two parties knowing dependent 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(sub XYZ), can also receive all messages exchanged by the two parties over a public channel. The goal of a protocol is that the enemy obtains at most a negligible amount of information about S. Upper bounds on H(S) as a function of P(sub XYZ) are presented. Lower bounds on the rate H(S)/N (as N approaches Infinity) are derived for the case where X = (X(sub 1), ..., X(sub N)), Y = (Y(sub 1), ..., Y(sub N)) and Z = (Z(sub 1), ..., Z(sub N)) result from N independent executions of a random experiment generating X(sub i), Y(sub i) and Z(sub i) for i = 1,..., N. In particular, it is shown that such secret key agreement is possible for a scenario where all three parties receive the output of a binary symmetric source over independent binary symmetric channels, even when the enemy's channel is superior to the other two channels. The results suggest how to build cryptographic systems that are probably secure against enemies with unlimited computing power under realistic assumptions about the partial independence of the noise on the involved communication channels.