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.
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.
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.
For pt. II see ibid., vol.49, no.4, p.832-38 (2003). Here, we consider the special case where the legitimate partners already share a mutual string which might, however, be partially known to the adversary. The problem of generating a secret key in this case has been well studied in the passive-adversary model - for instance, in the context of quantum key agreement - under the name of privacy amplification. We consider the same problem with respect to an active adversary and propose two protocols, one based on universal hashing and one based on extractors, allowing for privacy amplification secure against an adversary whose knowledge about the initial partially secret string is limited to one third of the length of this string. Our results are based on novel techniques for authentication secure even against adversaries knowing a substantial amount of the "secret" key.
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.>
This is the second part of a two-part paper on information-theoretically secure secret key agreement. This part covers the secret key capacity under the channel model. In this model, multiple terminals wish to create a shared secret key that is secure from an eavesdropper with unlimited computational resources. The terminals are all connected to a noiseless and authenticated but insecure channel, called the “public channel.” Furthermore, the terminals have access to a secure but noisy discrete memoryless broadcast channel (DMBC). The first terminal can choose a sequence of inputs to the DMBC, which has outputs at the other terminals and at the eavesdropper. After each channel use, the terminals can engage in arbitrarily many rounds of interactive authenticated communication over the public channel. At the end, each legitimate terminal should be able to generate the secret key. In this paper, we derive new lower and upper bounds on the secrecy capacity. In each case, an example is provided to show that the new bound represents a strict improvement over the previously best known bound. This part of the paper is not standalone, and is written under the assumption that the reader has access to Part I, which is published in the same issue.
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...
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, multiple terminals wish to create a shared secret key that is secure from a passive eavesdropper. The terminals have access to a noiseless public communication channel and an additional resource that depends on the model. In the source model, the resource is an external source that repeatedly beams correlated randomness to the terminals; whereas in the channel model, the resource is a secure but noisy discrete memoryless broadcast channel. We derive new lower and upper bounds on the secret key capacity under both the source model and the channel model. The technique used for deriving our bound for the source model is to find certain properties of functions of joint probability distributions which, applied to the joint distribution of the source, will imply that they dominate the secret key capacity, and then prove the bound by a verification argument. A similar technique is used for the channel model. Finally, we also define a problem of communication for omniscience by a neutral observer and establish the equivalence between this new problem and the problem of secret key agreement. This generalizes an earlier result of Csiszár and Narayan.