Key agreement is a fundamental cryptographic primitive. It has been proved that key agreement protocols with security against computationally unbounded adversaries cannot exist in a setting where Alice and Bob do not have dependent variables and communication between them is fully public, or fully controlled by the adversary. In this paper we consider this problem when the adversary can "partially" control the channel. We motivate these adversaries by considering adversarial corruptions at the physical layer of communication, give a definition of adversaries that can "partially" eavesdrop and "partially" corrupt the communication. We formalize security and reliability of key agreement protocols, derive bounds on the rate of key agreement, and give constructions that achieve the bound. Our results show that it is possible to have secret key agreement as long as some of the communicated symbols remain private and unchanged by the adversary. We relate our results to the previous known results, and discuss future work.
Key agreement is a fundamental cryptographic primitive. It has been proved that key agreement protocols with security against computationally unbounded adversaries cannot exist in a setting where Alice and Bob do not have dependent variables and communication between them is fully public, or fully controlled by the adversary. In this paper we consider this problem when the adversary can "partially" control the channel. We motivate these adversaries by considering adversarial corruptions at the physical layer of communication, give a definition of adversaries that can "partially" eavesdrop and "partially" corrupt the communication. We formalize security and reliability of key agreement protocols, derive bounds on the rate of key agreement, and give constructions that achieve the bound. Our results show that it is possible to have secret key agreement as long as some of the communicated symbols remain private and unchanged by the adversary. We relate our results to the previous known results, and discuss future work.
Key agreement (KA) is a fundamental cryptographic primitive. Assuming that Alice and Bob do not have any prior shared correlation, it has been proved that key agreement with security against a computationally unbounded adversary is impossible if communication is either over a fully public channel, or the channel is fully controlled by the adversary. In this paper we consider a setting where communication is over a partially corrupted channel, and there is no prior shared correlation. We formalize security and reliability of key agreement protocols in this setting, derive bounds on the rate of secret key agreement, and give constructions that achieve the respective bounds. Our results show that secret key agreement, and hence secret message transmission, is possible, as long as a small fraction of the transmitted symbols in each round remain untouched by the adversary. Our results can be extended to key agreement between nodes in a network, when the two nodes are connected by a set of disjoint paths, and in each round a subset of paths is eavesdropped and another subset (possibly with overlap) is tampered with. We relate our results to previous works, and discuss future directions.
We study the question of basing symmetric key cryptography on weak secrets. In this setting, Alice and Bob share an n-bit secret W, which might not be uniformly random, but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Since standard symmetric-key primitives require uniformly random secret keys, we would like to construct an authenticated key agreement protocol in which Alice and Bob use W to agree on a nearly uniform key R, by communicating over a public channel controlled by an active adversary Eve. We study this question in the information theoretic setting where the attacker is computationally unbounded. We show that single-round (i.e. one message) protocols do not work when k ≤ n/2, and require poor parameters even when n/2<k<<n.
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.
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.
Information-theoretic secret-key agreement between two parties Alice and Bob is a well-studied problem that is provably impossible in a plain model with public (authenticated) communication, but is known to be possible in a model where the parties also have access to some correlated randomness. One particular type of such correlated randomness is the so-called satellite setting, where uniform random bits (e.g., sent by a satellite) are received by the parties and the adversary Eve over inherently noisy channels. The antenna size determines the error probability, and the antenna is the adversary’s limiting resource much as computing power is the limiting resource in traditional complexity-based security. The natural assumption about the adversary is that her antenna is at most Q times larger than both Alice’s and Bob’s antenna, where, to be realistic, Q can be very large.
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