Information Security and Cryptography Research Group

Towards Characterizing when Information-Theoretic Key Agreement Is Possible

Ueli Maurer and Stefan Wolf

Advances in Cryptology — ASIACRYPT '96, Lecture Notes in Computer Science, Springer-Verlag, vol. 1163, pp. 196–209, Nov 1996.

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.

BibTeX Citation

@inproceedings{MauWol96a,
    author       = {Ueli Maurer and Stefan Wolf},
    title        = {Towards Characterizing when Information-Theoretic Key Agreement Is Possible},
    booktitle    = {Advances in Cryptology --- ASIACRYPT~'96},
    pages        = 196--209,
    series       = {Lecture Notes in Computer Science},
    volume       = 1163,
    year         = 1996,
    month        = 11,
    publisher    = {Springer-Verlag},
}

Files and Links