IEEE Transactions on Information Theory

Secret key agreement by public discussion from common information

Ueli M. Maurer

Published May 1, 1993• 2,005 citations

Abstract

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 to infinity ) are derived for the case in which 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. It is shown that such a secret key agreement is possible for a scenario in which 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.>

DOI: 10.1109/18.256484

Related papers

On the secret-key rate of binary random variables

Martin J. Gander, Ueli M. Maurer

Consider a scenario in which two parties Alice and Bob as well as an opponent Eve receive the output of a binary symmetric source (e,g. installed in a satellite) over individual, not necessarily independent binary symmetric channels. Alice and Bob share no secret key initially and can only communicate over a public channel completely accessible to Eve. The authors derive a lower bound on the rate at which Alice and Bob can generate secret-key bits about which Eve has arbitrarily little information, This lower bound is strictly positive as long as Eve's binary symmetric channel is not perfect, even if Alice's and Bob's channels are by orders of magnitude less reliable than Eve's channel.>

IEEE International Symposium on Information Theory (ISIT)Dec 17, 200229 citations

New bounds on the information-theoretic key agreement of multiple terminals

Amin Gohari, Venkat Anantharam

We study the problem of information-theoretically secure secret key agreement under the well-known source model and channel model. In both of these models the parties wish to create a shared secret key that is secure from an eavesdropper with unlimited computational resources. In the channel model, the first party can choose a sequence of inputs to a discrete memoryless channel, which has outputs at the other parties and at the eavesdropper. After each channel use, the parties can engage in arbitrarily many rounds of interactive authenticated communication over a public channel. At the end, each party should be able to generate the key. In the source model, the parties wishing to generate a secret key (as well as the eavesdropper) receive a certain number of independent identically distributed copies of jointly distributed random variables after which the parties are allowed interactive authenticated public communication, at the end of which each party should be able to generate the key. We derive new lower and upper bounds on the secret key rate under the source model and the channel model, and introduce a technique for proving that a given expression bounds the secrecy rate from above in the channel model. Our lower bounds strictly improve what is essentially the best known lower bound in both the source model and the channel model. Our upper bound in the channel model strictly improves the current state of art upper bound. We do not know whether our new upper bound in the source model represents an strict improvement but it includes the current best known bound as a special case.

IEEE International Symposium on Information Theory (ISIT)Jul 1, 200814 citations

Secret-key agreement over unauthenticated public channels-part I: definitions and a completeness result

Ueli M. Maurer, Stefan Wolf

This is the first part of a three-part paper on secret-key agreement secure against active adversaries. In all three parts, we address the question whether two parties, knowing some correlated pieces of information X and Y, respectively, can generate a string S about which an adversary, knowing some information Z and having read and write access to the communication channel used by the legitimate partners, is almost completely ignorant. Whether such key agreement is possible, and if yes at which rate, is an inherent property of the joint probability distribution P/sub XYZ/. In this part, we first prove a number of general impossibility results. We then consider the important special case where the legitimate partners as well as the adversary have access to the outcomes of many independent repetitions of a fixed tripartite random experiment. In this case, the result characterizing the possibility of secret-key agreement secure against active adversaries is of all-or-nothing nature: either a secret key can be generated at the same rate as in the (well-studied) passive-adversary case, or such secret-key agreement is completely impossible. The exact condition characterizing the two cases is presented.

IEEE Transactions on Information TheoryApr 1, 2003159 citations

Unconditionally secure key agreement and the intrinsic conditional information

Ueli M. Maurer, Stefan Wolf

This paper is concerned with secret-key agreement by public discussion. Assume that two parties Alice and Bob and an adversary Eve have access to independent realizations of random variables X, Y, and Z, respectively, with joint distribution P/sub XYZ/. The secret-key rate S(X;Y/spl par/Z) has been defined as the maximal rate at which Alice and Bob can generate a secret key by communication over an insecure, but authenticated channel such that Eve's information about this key is arbitrarily small. We define a new conditional mutual information measure, the intrinsic conditional mutual information between S and Y when given Z, denoted by I(X;Y/spl darr/Z), which is an upper bound on S(X;Y/spl par/Z). The special scenarios are analyzed where X, Y, and Z are generated by sending a binary random variable R, for example a signal broadcast by a satellite, over independent channels, or two scenarios in which Z is generated by sending X and Y over erasure channels. In the first two scenarios it can be shown that the secret-key rate is strictly positive if and only if I(X;Y/spl darr/Z) is strictly positive. For the third scenario, a new protocol is presented which allows secret-key agreement even when all the previously known protocols fail.

IEEE Transactions on Information TheoryMar 1, 1999274 citations

Unconditionally secure secret key agreement and the intrinsic conditional mutual information

Ueli M. Maurer, Stefan Wolf

This paper is concerned with secret-key agreement by public discussion: two parties Alice and Bob and an adversary Eve have access to independent realizations of random variables X , Y , and Z, respectively, with joint distribution PXY Z . The secret key rate S(X ; Y jjZ) has been defined as the maximal rate at which Alice and Bob can generate a secret key by communication over an insecure, but authenticated channel such that Eve's information about this key is arbitrarily small. We define a new conditional mutual information measure, the intrinsic conditional mutual information between X and Y when given Z, denoted by I(X ; Y#Z), which is an upper bound on S(X ; Y jjZ). The special scenarios where X , Y , and Z are generated by sending a binary random variable R, for example a signal broadcast by a satellite, over independent channels, or where Z is generated by sending X and Y over erasure channels, are analyzed. In the first scenario it can be shown that the secret key rate is str...

May 1, 19971 citation

Secret-key agreement over unauthenticated public channels-part II: the simulatability condition

Ueli M. Maurer, Stefan Wolf

For pt.I see ibid., vol.49, no.4, p.822-31(2003). In the first part, we showed that when two parties, willing to generate a secret key, but connected only by a completely insecure communication channel, have access to independent repetitions of some random experiment, then the possibility of secret-key agreement depends on a certain property, called simulatability, of the probability distribution modeling the parties' initial knowledge. More generally, the simulatability condition is important in the context of identification and authentication among parties sharing some correlated but not necessarily identical partially secret keys. Unfortunately, this condition is a priori not very useful since it is not clear how to decide efficiently whether it is satisfied or not for a given distribution P/sub XYZ/. We introduce a new formalism, based on a mechanical model for representing the involved quantities, that allows for dealing with discrete joint distributions of random variables and their manipulations by noisy channels. We show that this representation leads to a simple and efficient characterization of the possibility of secret-key agreement secure against active adversaries.

IEEE Transactions on Information TheoryApr 1, 200399 citations