ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

Towards Characterizing when Information-Theoretic Key Agreement Is Possible

Ueli Maurer and Stefan Wolf

This paper is concerned with information-theoretically secure secret key agreement in the general scenario where three parties, Alice, Bob, and Eve, know random variables X, Y, and Z, respectively, with joint distribution P_XYZ, for instance resulting from receiving a sequence of random bits broadcast by a satellite. We consider the problem of determining for a given distribution P_{XYZ} whether Alice and Bob can in principle, by communicating over an insecure channel accessible to Eve, generate a secret key about which Eve's information is arbitrarily small. When X, Y, and Z are random variables that result from a binary random variable being sent through three arbitrary independent channels, it is shown that secret key agreement is possible if and only if I(X;Y|Z)>0, i.e., under the sole condition that X and Y have some (arbitrarily weak) statistical dependence when given Z.