The problem of generating a shared secret key S by two parties knowing
dependent random variables X and Y, respectively, hut not sharing a s
ecret key initially, is considered. An enemy who knows the random vari
able Z, jointly distributed with X and Y according to some probability
distribution P(XYZ), can also receive all messages exchanged by the t
wo parties over a public channel. The goal of a protocol is that the e
nemy obtains at most 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 --> infinity) are derived for the case where X
= [X1,..., X(N)], Y = [Y1,...,Y(N)] and Z = [Z1,..., Z(N)] result from
N independent executions of a random experiment generating X(i), Y(i)
and Z(i) for i = 1,..., N. In particular, it is shown that such secre
t key agreement is possible for a scenario where all three parties rec
eive the output of a binary symmetric source over independent binary s
ymmetric channels, even when the enemy's channel is superior to the ot
her two channels. The results suggest how to build cryptographic syste
ms that are provably secure against enemies with unlimited computing p
ower under realistic assumptions about the partial independence of the
noise on the involved communication channels.