# «Abstract. One of the basic problems in cryptography is the generation of a common secret key between two parties, for instance in order to com- ...»

**Information-Theoretic Key Agreement:**

From Weak to Strong Secrecy for Free

Ueli Maurer1 and Stefan Wolf1

Computer Science Department, Swiss Federal Institute of Technology (ETH Zurich),

CH-8092 Zurich, Switzerland

{maurer,wolf}@inf.ethz.ch

Abstract. One of the basic problems in cryptography is the generation

of a common secret key between two parties, for instance in order to com-

municate privately. In this paper we consider information-theoretically

secure key agreement. Wyner and subsequently Csisz´r and K¨rner de- a o scribed and analyzed settings for secret-key agreement based on noisy communication channels. Maurer as well as Ahlswede and Csisz´r gen-a eralized these models to a scenario based on correlated randomness and public discussion. In all these settings, the secrecy capacity and the secret-key rate, respectively, have been deﬁned as the maximal achiev- able rates at which a highly-secret key can be generated by the legitimate partners. However, the privacy requirements were too weak in all these deﬁnitions, requiring only the ratio between the adversary’s information and the length of the key to be negligible, but hence tolerating her to ob- tain a possibly substantial amount of information about the resulting key in an absolute sense. We give natural stronger deﬁnitions of secrecy ca- pacity and secret-key rate, requiring that the adversary obtains virtually no information about the entire key. We show that not only secret-key agreement satisfying the strong secrecy condition is possible, but even that the achievable key-generation rates are equal to the previous weak notions of secrecy capacity and secret-key rate. Hence the unsatisfactory old deﬁnitions can be completely replaced by the new ones. We prove these results by a generic reduction of strong to weak key agreement.

The reduction makes use of extractors, which allow to keep the required amount of communication negligible as compared to the length of the resulting key.

1 Introduction and Preliminaries

1.1 Models of Information-Theoretic Secret-Key Agreement This paper is concerned with information-theoretic security in cryptography.

Unlike computationally-secure cryptosystems, the security of which is based on the assumed yet unproven hardness of a certain problem such as integer factoring, a proof without any computational assumption, based on information theory rather than complexity theory, can be given for the security of an information- theoretically (or unconditionally) secure system.

From Weak to Strong Information-Theoretic Key Agreement 357 A fundamental problem is the generation of a mutual key about which an adversary has virtually no information. Wyner [18] and later Csisz´r anda K¨rner [10] considered the natural message-transmission scenarios in which the o legitimate partners Alice and Bob, as well as the adversary Eve, are connected by noisy channels. In Csisz´r and K¨rner’s setting, Alice sends information (given by a o the random variable X) to Bob (receiving Y ) and to the opponent Eve (who obtains Z) over a noisy broadcast channel characterized by the conditional distribution PY Z|X. Wyner’s model corresponds to the special case where X → Y → Z is a Markov chain.

The secrecy capacity CS (PY Z|X ) of the channel PY Z|X has been deﬁned as the maximal rate at which Alice can transmit a secret string to Bob by using only the given noisy (one-way) broadcast channel such that the rate at which the eavesdropper receives information about the string can be made arbitrarily small.

More precisely, the secrecy capacity is the maximal asymptotically-achievable ratio between the number of generated key bits and the number of applications of the noisy broadcast channel such that Eve’s per-letter information about the key is small.

As a natural generalization of these settings, Maurer [13] and subsequently Ahlswede and Csisz´r [1] have considered the model of secret-key agreement by a public discussion from correlated randomness. Here, two parties Alice and Bob, having access to speciﬁc dependent information, use authentic public communication to agree on a secret key about which an adversary, who also knows some related side information, obtains only a small fraction of the total information.

More precisely, it is assumed in this model that Alice and Bob and the adversary Eve have access to repeated independent realizations of random variables X, Y, and Z, respectively. A special example is the situation where all the parties receive noisy versions of the outcomes of some random source, e.g., random bits broadcast by a satellite at low signal power.

The secret-key rate S(X; Y ||Z) has, in analogy to the secrecy capacity, been deﬁned in [13] as the maximal rate at which Alice and Bob can generate a secret key by communication over the noiseless and authentic but otherwise insecure channel in such a way that the opponent obtains information about this key only at an arbitrarily small rate.

Note that Maurer’s model is a generalization of the earlier settings in the sense that only the correlated information, but not the insecure communication is regarded as a resource. In particular, the communication can be interactive instead of only one-way, and the required amount of communication has no inuence on the resulting secret-key rate. These apparently innocent modiﬁcations have dramatic consequences for the possibility of secret-key agreement.

initial advantage in terms of PY Z|X, whereas interactive secret-key generation can be possible in settings that are initially much less favorable for the legitimate partners.

It was shown [10] that CS (PY Z|X ) ≥ maxPX (I(X; Y ) − I(X; Z)), where the maximum is taken over all possible distributions PX on the range X of X, and that equality holds whenever I(X; Y ) − I(X; Z) is non-negative for all distributions PX. On the other hand, it is clear from the above bound that if U → X → Y Z is a Markov chain, then CS (PY Z|X ) ≥ I(U ; Y ) − I(U ; Z) is also

**true. If the maximization is extended in this way, then equality always holds:**

CS (PY Z|X ) = max (I(U ; Y ) − I(U ; Z)) (1) PU X : U →X→Y Z is the main result of [10]. It is a consequence of equality (1) that Alice and Bob can generate a secret key by noisy one-way communication exactly in scenarios that provide an advantage of the legitimate partners over the opponent in terms of the broadcast channel’s conditional distribution PY Z|X.

The secret-key rate S(X; Y ||Z), as a function of PXY Z, has been studied intensively. Lower and upper bounds on this quantity were derived, as well as necessary and suﬃcient criteria for the possibility of secret-key agreement [13], [15]. The lower bound

** S(X; Y ||Z) ≥ max [I(X; Y ) − I(X; Z), I(Y ; X) − I(Y ; Z) ] (2)**

follows from equality (1) [13]. The important diﬀerence to the previous settings however is that secret-key agreement can even be possible when the right-hand side of inequality (2) is zero or negative. A special protocol phase, called advantage distillation, requiring feedback instead of only one-way communication, must be used in this case. On the other hand, it was shown in [15] that S(X; Y ||Z) ≤ I(X; Y ↓Z) := min [I(X; Y |Z)] PZ|Z holds, where I(X; Y ↓ Z) is called the intrinsic conditional information between X and Y, given Z. It has been conjectured in [15], based on some evidence, that S(X; Y ||Z) = I(X; Y ↓ Z) holds for all PXY Z, or at least that I(X; Y ↓ Z) 0 implies S(X; Y ||Z) 0. Most recent results suggest that the latter is true if |X | + |Y| ≤ 5, but false in general [11].

1.3 Contributions of this Paper and Related Work In all the mentioned scenarios, the conditions on the resulting secret key were too weak originally. As it is often done in information theory, all the involved quantities, including the information about the key the adversary is tolerated to obtain, were measured in terms of an information rate, which is deﬁned as the ratio between the information quantity of interest and the number of independent repetitions of the underlying random experiment. Unfortunately, the total information the adversary gains about the resulting secret key is then, although From Weak to Strong Information-Theoretic Key Agreement 359 arbitrarily small in terms of the rate, not necessarily bounded, let alone negligibly small. The reason is that for a given (small) ratio 0, key agreement with respect to the security parameter is required to work only for strings of length N exceeding some bound N0 ( ) which can depend on. In particular, N0 ( ) · → ∞ for → 0 is possible. Clearly, this is typically unacceptable in a cryptographic scenario. For instance, the generated key cannot be used for a one-time-pad encryption if all parts of the message must be protected.

Motivated by these considerations, stronger deﬁnitions of the rates at which a secret key can be generated are given for the diﬀerent scenarios. More speciﬁcally, it is required that the information the adversary obtains about the entire key be negligibly small in an absolute sense, not only in terms of a rate. In the setting of secret-key agreement by noiseless public discussion from common information it is additionally required that the resulting secret key, which must be equal for Alice and Bob with overwhelming probability, is perfectly-uniformly distributed.

The main result of this paper is a generic reduction from strong to weak key agreement with low communication complexity. As consequences of this, Theorems 1 and 2 state that both for the secrecy capacity and for the secretkey rate, strengthening the security requirements does not reduce the achievable key-generation rates. This is particularly interesting for the case of the secrecy capacity because in this model, all the communication must be carried out over the noisy channel. Recent advances in the theory of extractors allow for closing the gap between weak and strong security in this case.

An important consequence is that all previous results on CS (PY Z|X ) and on S(X; Y ||Z), brieﬂy described in Section 1.2, immediately carry over to the strong notions although they were only proved for the weaker deﬁnitions. The previous deﬁnitions were hence unnecessarily weak and can be entirely replaced by the new notions.

A basic technique used for proving the mentioned reduction is privacy ampliﬁcation, introduced in [3], where we use both universal hashing and, as a new method in this context, extractors. A particular problem to be dealt with is to switch between (conditional) Shannon-, R´nyi-, and min-entropy of random e variables or, more precisely, of blocks of independent repetitions of random variables, and the corresponding probability distributions. A powerful tool for doing this are typical-sequences techniques.

Similar deﬁnitions of strong secrecy in key agreement have been proposed already by Maurer [14] (for the secret-key rate) and by Csisz´r [9] (for the a secrecy capacity). The authors have learned about the existence of the paper [9] (in Russian) only a few days before submitting this ﬁnal version. In [14], the lower bound (3) on a slightly weaker variant of the strong secret-key rate than the one studied in this paper was proven. We present a substantially simpliﬁed proof here. In [9], a result similar to Theorem 2 was shown, using methods diﬀerent from ours. More precisely, it was proved that the technique of [10] actually leads to a stronger secrecy than stated. In contrast to this, we propose a generic procedure for amplifying the secrecy of any information-theoretic key 360 Ueli Maurer and Stefan Wolf agreement, requiring an amount of communication which is negligible compared to the length of the resulting key.

1.4 Entropy Measures and Variational Distance

2 Secret-Key Agreement from Correlated Randomness In this section we deﬁne a stronger variant of the secret-key rate of a distribution PXY Z and show that this new quantity is equal to the previous, weak secretkey rate as deﬁned in [13]. The protocol for strong key agreement consists of the following steps. First, weak key agreement is repeated many times. Then, so-called information reconciliation (error correction) and privacy ampliﬁcation are carried out. These steps are described in Section 2.2. Of central importance for all the arguments made are typical-sequences techniques (Section 2.3). The main result of this section, the equality of the secret-key rates, is then proven in Section 2.4.

2.1 Deﬁnition of Weak and Strong Secret-Key Rates

As pointed out in Section 1.3, the given deﬁnition of the secret-key rate is unsatisfactorily and, as shown later, unnecessarily weak. We give a strong deﬁnition which bounds the information leaked to the adversary in an absolute sense and additionally requires the resulting key to be perfectly-uniformly distributed.

1 All the logarithms in this paper are to the base 2, unless otherwise stated.

From Weak to Strong Information-Theoretic Key Agreement 361 Deﬁnition 2 The strong secret-key rate of X and Y with respect to Z, denoted by S(X; Y ||Z), is deﬁned in the same way as S(X; Y ||Z) with the modiﬁcations that Alice and Bob compute strings SA and SB which are with probability at least 1 − both equal to a string S with the properties

Obviously, S(X; Y ||Z) ≤ S(X; Y ||Z) holds. It is the goal of this section to show equality of the rates for every distribution PXY Z. Thus the attention can be totally restricted to the strong notion of secret-key rate.

2.2 Information Reconciliation and Privacy Ampliﬁcation In this section we analyze the two steps, called information reconciliation and privacy ampliﬁcation, of a protocol allowing strong secret-key agreement whenever I(X; Y ) − I(X; Z) 0 or I(Y ; X) − I(Y ; Z) 0 holds. More precisely, we show

** S(X; Y ||Z) ≥ max { I(X; Y ) − I(X; Z), I(Y ; X) − I(Y ; Z) }. (3)**