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.
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.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 third part of a three-part paper on se- cret-key agreement secure against active adversaries. Here, we con- sider 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 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 ac- tive adversary and propose two protocols, one based on universal hashing and one based on extractors, allowing for privacy ampli- fication secure against an adversary whose knowledge about the initial partially string is limited to one third of the length of this string. Our results are based on novel techniques for au- thentication secure even against adversaries knowing a substantial amount of the secret key. information about . From Eve's point of view, the length of can in this case be roughly equal to the Renyi entropy of . In this paper, we investigate the same problem under the as- sumption that the communication between Alice and Bob is not authenticated. Note that, in contrast to the model where many independent repetitions of the involved random variables are given (15), the same piece of information must be used here both for authentication and as the input for privacy amplifica- tion. Two problems that arise in this context are authentication with an only partially key, and the fact that this authenti- cation leaks information about , hence potentially also about , to the adversary. We show that for our purpose, a new, inter- active, authentication method is better than one-way authentica- tion by strongly universal hashing, and that so-called extractors, requiring fewer random bits (i.e., shorter messages to be com- municated), are a better technique for privacy amplification than
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.>
In this paper, the problem of key generation over an unauthenticated public channel in a network setup is considered. The considered model consists of four terminals: two legitimate terminals who need to share a key, a helper and an active adversary. The legitimate terminals and the helper are allowed to exchange messages over a public noiseless channel, to which the adversary has full access and may modify messages exchanged through this public channel. We investigate two types of keys: secret key (secure from the adversary only) and private key (secure from both the helper and the adversary). We characterize the relationship between the key rates in our model and the existing models with a passive adversary. We characterize conditions under which the generated key rates in this model are non-zero, and further provide an authentication scheme to show that key capacities, if are non-zero, are the same as those for the scenario with a passive adversary.
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...