Linking Information Reconciliation and Privacy Amplification^{⋆}

Christian Cachin and Ueli M. Maurer

Institute for Theoretical Computer Science ETH Zürich CH-8092 Zürich, Switzerland

                   E-mail: {cachin,maurer}@inf.ethz.ch

To appear in Journal of Cryptology.

Abstract. Information reconciliation and privacy amplification are important tools in cryptography and information theory. Reconciliation allows two parties knowing correlated random variables, such as a noisy version of the partner’s random bit string, to agree on a shared string. Privacy amplification allows two parties sharing a partially secret string, about which an opponent has some partial information, to distill a shorter but almost completely secret key by communicating only over an insecure channel, as long as an upper bound on the opponent’s knowledge about the string is known. The relation between these two techniques has not been well understood. In particular, it is important to understand the effect of side-information, obtained by the opponent through an initial reconciliation step, on the size of the secret key that can be distilled safely by subsequent privacy amplification. The purpose of this paper is to provide the missing link between these techniques by presenting bounds on the reduction of the collision entropy of a random variable induced by side-information. The results have applications in unconditionally secure key agreement protocols and in quantum cryptography.

1 Introduction

One of the fundamental problems in cryptography is the generation of a shared secret key by two parties, Alice and Bob, not sharing a secret key initially, in the presence of an enemy Eve. One generally assumes that Eve can eavesdrop on the communication between Alice and Bob who are connected only by a public channel. It is easy to see that if this public channel is not assumed to be authentic, then such key agreement is impossible. We therefore assume that any modification or insertion of messages can be detected by Alice and Bob.

This problem can be solved by applying public-key cryptography [8], where one assumes that Eve’s computing power is limited. In the recent years, key agreement protocols have been developed that are secure against adversaries with unlimited computing power [1, 10]. The motivation for investigating such protocols is two-fold: First, one avoids having to worry about the generality of a particular computational model, which is of some concern in view of the potential realizability of quantum computers (e.g. [4, 9, 12]). Secondly, and more importantly, no strong rigorous results on the difficulty of breaking a cryptosystem have been proved, and this problem continues to be among the most difficult ones in complexity theory.

Unconditionally secure secret-key agreement [10, 11] takes place in a scenario where Alice, Bob and Eve know the correlated random variables X, Y and Z, respectively, distributed according to some joint probability distribution that may be under partial control of Eve (like for

⋆ This research was supported by the Swiss National Science Foundation. A preliminary version of this paper was presented at Eurocrypt ’94, May 9–12, Perugia, Italy.

instance in quantum cryptography [1]). One possible scenario considered by Maurer [10] is that X, Y and Z result from a binary random string broadcast by a satellite and received by Alice, Bob and Eve over noisy channels. Secret-key agreement is possible even when Eve’s channel is much more reliable than Alice’s and Bob’s channels.

A key agreement protocol for such a scenario generally consists of three phases:

Advantage Distillation: The purpose of the first phase is to create a random variable W about which either Alice or Bob has more information than Eve. Advantage distillation is only needed when such a W is not immediately available from X and Y, for instance, when Eve’s channel is superior in the above satellite scenario. Alice and Bob create W by exchanging messages, summarized as the random variable C, over the public channel.

Information Reconciliation [1, 6]: To agree on a string T with very high probability, Alice and Bob exchange redundant error-correction information U, such as a sequence of parity checks. After this phase, Eve’s (incomplete) information about T consists of Z, C and U.

Privacy Amplification [2, 3]: In the final phase, Alice and Bob agree publicly on a compression function G to distill from T a shorter string S about which Eve has only a negligible amount of information. Therefore, S can subsequently be used as a secret key.

Information reconciliation and privacy amplification are fundamental for unconditionally secure key agreement and quantum key distribution. Advantage distillation has not yet been used in quantum cryptography because the considered scenarios assume that Alice and Bob have an advantage compared to Eve.

If after the first phase Alice knows a string about which Bob has more information than Eve, Alice and Bob can choose W to be this string. In other words, using information-theoretic terms, W is a random variable such that H(W |XC) = 0 and H(W |Y C) < H(W |ZC). In such a case, Bob tries to determine W from Y and the reconciliation string U, which could simply be an error-correction string sent by Alice or could result from an interactive communication with Alice. (Note that H(U) ≥ H(W |Y C) is a necessary condition.) Hence reconciliation serves to establish H(W |Y CU) ≈ 0 while Eve still has a substantial amount of uncertainty about W: H(W |ZCU) > 0. After privacy amplification, H(S) should be as large as possible, and Eve’s information about S should be arbitrarily close to zero: I(S; ZCUG) = H(S) − H(S|ZCUG) ≈ 0. Note that Alice and Bob can both compute S, i.e., H(S|W G) = 0.

In the following, let V = [Z, C] summarize Eve’s total knowledge about W before reconciliation. For deriving lower bounds on Eve’s final information about the secret key S one can either consider a particular value V = v that Eve knows or one can average over all possible values of V. Note that results for a particular V = v, which will be considered in this paper, are stronger than averaging results because they are known to hold for the very instance of the protocol execution. In other words, Eve’s information about W is modeled by the probability distribution P_{W |V =v} about which Alice and Bob have some incomplete knowledge. In particular, they know a lower bound on the collision entropy (see below) of the distribution P_{W |V =v} but they do not know v.

It is known [2] that the collision entropy after reconciliation with U = u (i.e., of the distribution P_{W |V =v,U=u}) is a lower bound on the size of the secret key that can be distilled safely by privacy amplification. This paper is concerned with understanding the reduction of the collision entropy induced by the side information U, either for a particular value U = u, or averaged over all values of U. Although this question is fundamental for any proof in the area of key-agreement protocols, it has previously not been well understood because the behavior of collision entropy is different from that of Shannon entropy with respect to side-information. Existing proofs such as the ingenious Big-Brother argument of [1] work only for particular probability distributions and reconciliation protocols.

The paper is organized as follows. Section 2 reviews privacy amplification and the definition of collision entropy. Section 3 presents upper bounds on the reduction of collision entropy due to side-information for arbitrary probability distributions. Non-interactive reconciliation protocols with uniform and close-to-uniform probability distributions are investigated in Section 4. These results are applied in Section 5 to analyze the important class of scenarios in which a given random experiment is repeated many times independently.

2 Review of Privacy Amplification and Collision Entropy

We assume that the reader is familiar with the notion of entropy and the basic concepts of information theory [5]. In privacy amplification, a different and non-standard entropy measure, collision entropy, is of central importance [2]. Collision entropy is also known as Rényi entropy of order 2. To distinguish collision entropy from entropy in the sense of Shannon, we will always refer to the latter as Shannon entropy. All logarithms in this paper are to the base 2, and entropies are thus measured in bits.

Privacy amplification was introduced by Bennett, Brassard and Robert [3] and investigated further in [2], and can be described as follows. Assume Alice and Bob share an n–bit string W about which an eavesdropper Eve has incomplete information characterized by a probability distribution P_{W |V =v} over the n–bit strings, where v denotes the particular value taken on by the random variable V summarizing her side-information. For instance, Eve might have received some bits or parities of bits of W, she might have eavesdropped on some of the bits of W through a binary symmetric channel, or have some more complicated type of information about W. Alice and Bob have some knowledge of the distribution P_{W |V =v}, but they do not know exactly what is compromised about their string. Using a public channel, which is totally susceptible to eavesdropping, they wish to agree on a function g : {0, 1}^{n} → {0, 1}^{r} such that Eve, despite her partial knowledge about W and complete knowledge of g, almost certainly knows nearly nothing about g(W). This process transforms a partially secret n–bit string W into a highly secret but shorter r–bit string g(W) which can be used as a secret key.

The method for selecting the function g proposed in [3] is to choose it at random from a publicly-known universal class of hash functions mapping n-bit strings to r-bit strings. Universal hash functions were introduced by Carter and Wegman [7]. A class G of functions A → B is called universal if, for any distinct x_{1} and x_{2} in A, the probability that g(x_{1}) = g(x_{2}) is at most 1/|B| when g is chosen at random with uniform distribution from G.

Bennett, Brassard, Crépeau and Maurer [2] showed that the collision entropy (defined below) of Eve’s distribution about W provides a lower bound on the size r of the secret key distillable from W by privacy amplification with a universal hash function.

Definition 1 [2]. Let X be a random variable with alphabet X and distribution P_{X}. The collision probability P_{c}(X) of X is defined as the probability that X takes on the same value twice in two independent experiments, i.e.,

P_{c}(X) = ∑_{x∈X} P_{X}(x)^{2}.

The collision entropy of X is defined as the negative logarithm of its collision probability:

H_{c}(X) = − log P_{c}(X).

For an event E, the collision entropy of X conditioned on E, H_{c}(X|E), is defined naturally as the collision entropy of the conditional distribution P_{X|E}. The collision entropy conditioned on a random variable, H_{c}(X|Y), is defined as the expected value of the conditional collision entropy:

H_{c}(X|Y) = ∑_{y} P_{Y} (y) H_{c}(X|Y = y).

Equivalently, H_{c}(X) can be expressed as H_{c}(X) = − log E[P_{X}(X)], where E[·] denotes the expected value. Shannon entropy H(X) can be expressed similarly as H(X) = −E[log P_{X}(X)]. It follows from Jensen’s inequality (see [5], p. 428) that collision entropy is upper bounded by the Shannon entropy:

H_{c}(X) ≤ H(X),

with equality if and only if P_{X} is the uniform distribution over X or a subset of X. Similarly, we have H(X|Y) ≥ H_{c}(X|Y). Note that collision entropy (like Shannon entropy) is always positive.

The following theorem is the main result of [2]:

Theorem 2. Let X be a random variable on alphabet X with probability distribution P_{X} and collision entropy H_{c}(X). Further, let G be the random variable corresponding to the random choice (with uniform distribution) of a member of a universal class of hash functions from X → {0, 1}^{r}. Then

H(G(X)|G) ≥ H_{c}(G(X)|G) ≥ r − \frac{2^{r−H_{c}(X)}}{ln 2} .

Note that G is a random variable and that the quantity H(G(X)|G) is an average over all choices of the function g. It is possible that H(g(X)|g) = H(g(X)) differs from r by a non-negligible amount for some g, but such a g can occur only with negligible probability.

This theorem clearly applies also to conditional probability distributions such as P_{W |V =v} discussed above. If Eve’s collision entropy H_{c}(W |V = v) is known to be at least t and Alice and Bob choose S = G(W) as their secret key, then

H_{c}(S|G, V = v) = H_{c}(G(W)|G, V = v) ≥ r − 2^{r−t}/ ln 2.

The key S is indeed virtually secret because H(S|G, V = v) ≥ H_{c}(S|G, V = v) and hence H(S|G, V = v) is arbitrarily close to maximal. More precisely, if r < t, then Eve’s total information about S decreases exponentially in the excess compression t − r.

It should be pointed out that Theorem 2 cannot be generalized to collision entropy conditioned on a random variable, i.e., H_{c}(G(W)|GV) ≥ r − 2^{r−H_{c}(W |V)}/ ln 2 is false in general.

3 The Effect of Side Information on Collision Entropy

As described above, the reconciliation step consists of Alice and Bob exchanging suitable errorcorrection information U over the public channel. This information decreases Eve’s (Shannon and collision) entropy about W. For non-interactive reconciliation, Alice chooses an appropriate error-correction function f and sends U = f(W) to Bob who can then reconstruct W from U and his prior knowledge Y C.

The results of this paper will be derived for an arbitrary random variable X with probability distribution P_{X} and a side-information random variable U jointly distributed with X according to P_{XU}. However, they can just as well be applied to conditional distributions; our intended application is the key agreement scenario mentioned in the introduction, i.e., when P_{X} and P_{X|U} are replaced by P_{W |V =v} and P_{W |V =v,U}, respectively.

In general, giving side-information implies a reduction of entropy. Our goal is to derive upper bounds on the size of this reduction. Giving as side-information the fact that U takes on a particular value u, it is possible for both, Shannon and collision entropies, that the entropy increases or decreases. Moreover, the size of a reduction can be arbitrarily large.

However, the expected reduction (for all values of U) of the Shannon entropy of X by giving U, called the mutual information between X and U, is bounded by H(U):

H(X) − H(X|U) = I(X; U) ≤ H(U)  (1)

which follows from the symmetry of I(X; U) and the fact that Shannon entropy (conditional or not) is always positive.

Example 1 below illustrates two facts. First, the reduction of collision entropy implied by giving side-information U = u can exceed the reduction of Shannon entropy, i.e.,

H_{c}(X) − H_{c}(X|U = u) > H(X) − H(X|U = u)

is possible. Second, it shows that the natural generalization of (1) to collision entropy, namely H_{c}(X) − H_{c}(X|U) ≤ H_{c}(U), is not true in general. However, Theorem 3 demonstrates that the weaker inequality H_{c}(X) − H_{c}(X|U) ≤ H(U) is always satisfied.

Example 1. Let X be a random variable with alphabet X = {a_{1}, …, a_{10}, b_{1}, …, b_{10}}, distributed according to P_{X}(a_{i}) = 0.01 and P_{X}(b_{i}) = 0.09 for i = 1, …, 10. We have H(X) ≈ 3.79 and H_{c}(X) ≈ 3.61. Let f : X → {0, 1} be defined as

f(x) = \{ \begin{matrix}0 & if x ∈ \{a_{1}, …, a_{9}, b_{10}\} \\ 1 & if x ∈ \{a_{10}, b_{1}, …, b_{9}\} \end{matrix}

and let U = f(X). Then H(X|U = 0) ≈ 2.58 and H_{c}(X|U = 0) ≈ 1.85. The reduction of collision entropy when given U = 0 exceeds the reduction of Shannon entropy, i.e., H_{c}(X) − H_{c}(X|U = 0) ≈ 1.76 whereas H(X) − H(X|U = 0) ≈ 1.21.

The expected entropy reductions are H(X) − H(X|U) ≈ 0.69 (in fact H(X) − H(X|U) = H(U) because f is deterministic) and H_{c}(X) − H_{c}(X|U) ≈ 0.65. Note that H_{c}(U) ≈ 0.50 and H_{c}(X) − H_{c}(X|U) is indeed greater than H_{c}(U) but less than H(U).

H(U) is not only the maximal expected decrease of Shannon entropy, but H(U) is also an upper bound on the expected decrease of collision entropy, as the following theorem demonstrates.

Theorem 3. Let X and U be two random variables with alphabets X and U, respectively. The expected reduction of the collision entropy of X, when given U, does not exceed the Shannon entropy of U, i.e.,

H_{c}(X) − H_{c}(X|U) ≤ H(U),

with equality if and only if U is defined uniquely for each x ∈ X and P_{U} is the uniform distribution over U or a subset of U.

Proof. The collision probability of X can be written as

P_{c}(X) = ∑_{x∈X} P_{X}(x)^{2}

= ∑_{x∈X} (∑_{u∈U} P_{XU}(x, u))^{2}
≥ ∑_{x∈X} ∑_{u∈U} P_{XU}(x, u)^{2}
= ∑_{u∈U} P_{U}(u)^{2} ∑_{x∈X} P_{X|U}(x, u)^{2}
= ∑_{u∈U} P_{U}(u)^{2}P_{c}(X|U = u),  (2)

where the inequality follows from (∑_{i=1}^{n} p_{i})^{2} ≥ ∑_{i=1}^{n} p_{i}^{2} for nonnegative p_{i} (1 ≤ i ≤ n) with ∑_{i=1}^{n} p_{i} ≤ 1, and equality holds if and only if p_{i} = 0 for all i except for one. Inserting (2) into the definition of collision entropy gives

H_{c}(X) = − log P_{c}(X)
≤ − log (∑_{u∈U} P_{U}(u)^{2}P_{c}(X|U = u))

= − log (∑_{u∈U} P_{U}(u) [P_{U}(u)P_{c}(X|U = u)])
≤ − ∑_{u∈U} P_{U}(u) log [P_{U}(u)P_{c}(X|U = u)]
= − ∑_{u∈U} P_{U}(u) [log P_{U}(u) + log P_{c}(X|U = u)]
= − ∑_{u∈U} P_{U}(u) log P_{U}(u) − ∑_{u∈U} P_{U}(u) log P_{c}(X|U = u)
= H(U) + ∑_{u∈U} P_{U}(u) H_{c}(X|U = u)
= H(U) + H_{c}(X|U),

where the second inequality follows from Jensen’s inequality [5]. ⊓ ⊔

In contrast to Shannon entropy, the expected collision entropy can increase when side information is revealed, i.e., H_{c}(X) < H_{c}(X|U) is possible. This property is used in [2, 11] to prove that a larger key than suggested by Theorem 2 can be obtained by privacy amplification. The proof makes use of a conceptual oracle who is assumed to provide special side information U to Eve, called spoiling knowledge, which increases her collision entropy. Of course, this extra information cannot help her because she could always discard it.

For example, if Eve has received V = v over a binary symmetric channel, her collision entropy of the distribution P_{W |V =v} is considerably lower than her Shannon entropy. But the oracle can increase her collision entropy almost to the Shannon entropy by telling her the number d of bits in v that she received incorrectly. Then, all strings in distance d of v are equally likely and Eve’s collision entropy increases to the Shannon entropy.

For a positive-valued random variable X, E[X] ≤ t implies that P [X ≥ kt] ≤ 1/k. Hence, according to Theorem 3, the probability that the leaking information U = u decreases collision entropy by more than kH(U) is at most 1/k, i.e., P [H_{c}(X) − H_{c}(X|U = u) ≥ kH(U)] ≤ 1/k. However, such a high probability of partially exposing the string W is unacceptable in a keyagreement scenario. The following theorem provides a much stronger result by showing that the above probability decreases in fact exponentially in k if H(U) is replaced by an expression roughly twice as large.

Theorem 4. Let X and U be random variables with alphabets X and U, respectively, and let s > 0 be an arbitrary security parameter. With probability at least 1 − 2^{−s}, U takes on a value u for which

H_{c}(X) − H_{c}(X|U = u) ≤ 2 log |U| + 2s.

Remark. The statement of the theorem is equivalent to

∑_{u: H_{c}(X)−H_{c}(X|U=u) ≤ 2 log |U|+2s} P_{U}(u) ≥ 1 − 2^{−s}.

Equivalently, but less intuitively, we can write

P [H_{c}(X) − H_{c}(X|U = u) ≤ 2 log |U| + 2s] ≥ 1 − 2^{−s},

if we view H_{c}(X|U = u) as a function of u. (Note that this probability is defined although u could be a function of x, and that H_{c}(X) is a constant that does not depend on x or u.)

Proof. Let E be the event that U ∈ {u|P_{U}(u) ≥ p_{min}} for some given p_{min} > 0. There are |U| possible values u, and therefore we have P [\overline{E}] = 1 − P [E] ≤ |U| · p_{min}. For all u in this set we have

P_{c}(X|U = u) = ∑_{x∈X} P_{X|U}(x, u)^{2}

= ∑_{x∈X} (\frac{P_{XU}(x, u)}{P_{U}(u)})^{2}

≤ ∑_{x∈X} \frac{P_{X}(x)^{2}}{P_{U}(u)^{2}}

≤ ∑_{x∈X} \frac{P_{X}(x)^{2}}{p_{min}^{2}}
= \frac{P_{c}(X)}{p_{min}^{2}},

where we have made use of the fact that P_{XU}(x, u) = P_{X}(x)P_{U|X}(u, x) ≤ P_{X}(x). If we set p_{min} = 2^{−s}/|U|, then P_{U}(u) > p_{min} with probability at least P [E] ≥ 1 − 2^{−s}. The theorem now follows by taking logarithms on both sides of

P_{c}(X|U = u) ≤ |U|^{2} 2^{2s} P_{c}(X). ⊓ ⊔

Because of its importance we restate Theorem 4 for the key-generation scenario, replacing P_{X} by P_{W |V =v}, with the side-information consisting of k bits, for instance k parity checks of W when W is an n-bit string.

Corollary 5. Let W be a random variable with alphabet W, let v and u be particular values of the random variables V and U, correlated with W, and let s > 0 be a given security parameter. Then, with probability at least 1 − 2^{−s}, U takes on a value u such that the decrease in collision entropy by giving u,

H_{c}(W |V = v) − H_{c}(W |V = v, U = u),

is at most 2k + 2s.

4 Almost Uniform Distributions

As shown above, giving side information of the form U = u can reduce the collision entropy by an arbitrary amount, although the probability that this happens is bounded by Theorem 4. In this section and the next we derive better bounds on the reduction for non-interactive reconciliation and special probability distributions. It is easy to see that for uniform distributions and deterministic side-information U = f(W), the reduction of collision entropy depends only on the size of the preimage of u = f(x):

Lemma 6 [2]. Let X be a random variable with alphabet X, let f : X → U be an arbitrary function taking on values in a given set U, let U be defined as U = f(X), and set X_{u} = {x ∈ X : f(x) = u}. If X is distributed uniformly over X, then

H_{c}(X) − H_{c}(X|U = u) = log \frac{|X |}{|X_{u}|}.

In particular, if f is symmetric (i.e., |X_{u}| is the same for all u ∈ U), knowledge of U = u reduces the collision entropy by log |U|.

Theorems 7 and 8 state bounds on the reduction of collision entropy for almost uniform distributions. These results are applied in the next section to the analysis of the important class of scenarios where a given random experiment is repeated many times independently.

Theorem 7. For given α > 1 and β > 1, let X be a random variable with alphabet X and probability distribution P_{X} such that \frac{1}{α |X |} ≤ P_{X}(x) ≤ \frac{β}{|X |} for all x ∈ X. Define f, U and X_{u} as in Lemma 6. Then

H_{c}(X) − H_{c}(X|U = u) ≤ log \frac{|X |}{|X_{u}|} + 4 log α + 2 log β.

In particular, if f is symmetric, then H_{c}(X) − H_{c}(X|U = u) ≤ log |U| + 4 log α + 2 log β.

Proof. We can bound P_{c}(X) as follows:

P_{c}(X) = ∑_{x∈X} P_{X}(x)^{2} ≥ |X | \frac{1}{(α |X |)^{2}} = \frac{1}{α^{2} |X |}.  (3)

Using P_{U}(u) ≥ |X_{u}|\frac{1}{α|X |} we get a similar upper bound for P_{c}(X|U = u):

P_{c}(X|U = u) = ∑_{x∈X_{u}} P_{X|U}(x, u)^{2}
= \frac{1}{P_{U}(u)^{2}} ∑_{x∈X_{u}} P_{X}(x)^{2}

≤ (\frac{α |X |}{|X_{u}|})^{2} |X_{u}| (\frac{β}{|X |})^{2} = \frac{α^{2}β^{2}}{|X_{u}|} .  (4)

Combining (3) and (4) gives

\frac{P_{c}(X|U = u)}{P_{c}(X)} ≤ \frac{|X |}{|X_{u}|}α^{4}β^{2},

and the theorem follows. ⊓ ⊔

The following theorem provides a tighter bound for distributions that are very close to uniform.

Theorem 8. For given γ < \frac{1}{2}, let X be a random variable with alphabet X and probability distribution P_{X} such that \frac{1−γ}{|X |} ≤ P_{X}(x) ≤ \frac{1+γ}{|X |} for all x ∈ X. Define f, U and X_{u} as in Lemma 6. Then

H_{c}(X) − H_{c}(X|U = u) ≤ log \frac{|X |}{|X_{u}|} + log \frac{(1 + γ)^{2}}{1 − 2γ} .

Proof. For each x, define δ_{x} as the deviation of P_{X}(x) from the uniform distribution: P_{X}(x) = \frac{1}{|X |} + δ_{x}. Hence we have |δ_{x}| ≤ γ/|X |, and P_{c}(X|U = u) can be expressed as follows:

P_{c}(X|U = u) = ∑_{x∈X_{u}} P_{X|U}(x, u)^{2}
= ∑_{x∈X_{u}} (\frac{P_{XU} (x,u)}{P_{U} (u)})^{2}

= \frac{∑_{x∈X_{u}} P_{X}(x)^{2}}{P_{U}(u)^{2}}
= \frac{∑_{x∈X_{u}} P_{X}(x)^{2}}{(∑_{x∈X_{u}} P_{X}(x))^{2}}

= \frac{∑_{x∈X_{u}}(\frac{1}{|X |} + δ_{x})^{2}}{(∑_{x∈X_{u}} \frac{1}{|X |} + ∑_{x∈X_{u}} δ_{x})^{2}}

= \frac{\frac{|X_{u}|}{|X |^{2}} + \frac{2}{|X |} ∑_{x∈X_{u}} δ_{x} + ∑_{x∈X_{u}} δ_{x}^{2}}{\frac{|X_{u}|^{2}}{|X |^{2}} + 2\frac{|X_{u}|}{|X |} ∑_{x∈X_{u}} δ_{x} + (∑_{x∈X_{u}} δ_{x})^{2}}

≤ \frac{\frac{|X_{u}|}{|X |^{2}} + \frac{2}{|X |}|X_{u}|\frac{γ}{|X |} + |X_{u}|\frac{γ^{2}}{|X |^{2}}}{\frac{|X_{u}|^{2}}{|X |^{2}} − 2\frac{|X_{u}|}{|X |}|X_{u}|\frac{γ}{|X |}}

= \frac{1 + 2γ + γ^{2}}{|X_{u}| − 2γ|X_{u}|}.

In the third step we have made use of the fact that U is a deterministic function of X and thus P_{XU}(x, u) = P_{X}(x). Using P_{c}(X) ≥ 1/|X |, we get

\frac{P_{c}(X|U = u)}{P_{c}(X)} ≤ \frac{|X |}{|X_{u}|} · \frac{(1 + γ)^{2}}{1 − 2γ} ,

from which the theorem follows. ⊓ ⊔

5 Independent Repetition of a Random Experiment

In many practical scenarios, a certain random experiment is repeated independently a large number of times. For example, W could be the result of receiving independently generated bits over a memoryless channel, as in the satellite scenario mentioned earlier. A fundamental theorem of information theory states that in such a scenario all occurring sequences can be divided into a typical set and a non-typical set, where the probability that a randomly selected sequence of length n lies in the typical set approaches 1 for all sufficiently large n. Furthermore, all sequences in the typical set are almost equally probable. This allows us to bound the decrease of collision entropy by the results of the last section.

In the following, we will make use of strongly typical sequences [5]. Consider a probability distribution P_{X} over some finite set X where we assume P_{X}(x) > 0 for all x ∈ X. Let x^{n} = [x_{1}, …, x_{n}] be a sequence of n digits of X and define N_{a}(x^{n}) to be the number of occurrences of the symbol a ∈ X in the sequence x^{n}. A sequence x^{n} ∈ X^{n} is called ϵ-strongly typical if and only if

(1 − ϵ)P_{X}(a) ≤ \frac{N_{a}(x^{n})}{n} ≤ (1 + ϵ)P_{X}(a)

for all a ∈ X. Let S^{n}(ϵ) be the set of all ϵ-strongly typical sequences of length n and define X^{n} to be a sequence of n independent and identically distributed random variables X_{i} with P_{X_{i}} = P_{X} for 1 ≤ i ≤ n. In other words, we have P_{X^{n}}(x^{n}) = ∏_{i=1}^{n} P_{X}(x_{i}). Let o(n) be any function of n such that lim_{n→∞} o(n) = 0. The following lemma asserts that, for sufficiently large n, the probability that X^{n} ∈ S^{n}(ϵ) approaches 1 and that the cardinality of S^{n}(ϵ) is close to 2^{nH(X)}.

Lemma 9 [5]. Let X^{n} be a sequence of i.i.d. random variables distributed according to P_{X}. Then

1. For every δ > 0, P [X^{n} ∈ S^{n}(ϵ)] ≥ 1 − δ/n, for sufficiently large n.

2. For all x^{n} ∈ S^{n}(ϵ): P_{X^{n}}(x^{n}) = 2^{−nH(X)+o(n)}.

3. |S^{n}(ϵ)| = 2^{nH(X)+o(n)}.

Because all sequences in S^{n}(ϵ) are almost equally probable for sufficiently large n, the reduction of collision entropy is similar to the case of the uniform probability distribution where collision entropy behaves like Shannon entropy. This observation is stated as the next theorem.

Theorem 10. Let X^{n} be a sequence of i.i.d. random variables distributed according to P_{X}, let f : X^{n} → U be an arbitrary function taking on values in a given set U, and define S_{u}^{n}(ϵ) = {x^{n} ∈ S^{n}(ϵ) : f(x^{n}) = u} and U = f(X^{n}). For any δ > 0 and sufficiently large n, the following holds with probability at least 1 − δ/n: X^{n} lies in S^{n}(ϵ) and the reduction of collision entropy by giving U = u is upper bounded by

H_{c}(X^{n}) − H_{c}(X^{n}|U = u) ≤ nH(X) − log |S_{u}^{n}(ϵ)| + o(n).

In particular, if f is a symmetric function from X^{n} → {0, 1}^{k}, then knowledge of U = u reduces the collision entropy by at most k + o(n).

Proof. By Lemma 9, P_{X^{n}}(x^{n}) = 2^{−nH(X)+o(n)} for all x^{n} ∈ S^{n}(ϵ), and |S^{n}(ϵ)| = 2^{nH(X)+o(n)}. Application of Theorem 7 with α = 2^{o(n)} and β = 2^{o(n)} gives

H_{c}(X^{n}) − H_{c}(X^{n}|U = u) ≤ log \frac{|S^{n}(ϵ)|}{|S_{u}^{n}(ϵ)|} + o(n)
= nH(X) − log |S_{u}^{n}(ϵ)| + o(n). ⊓ ⊔

It should be noted that Theorem 10 can replace the spoiling knowledge argument in Maurer’s proof [11] that the known results on secret key rate [10] hold also for a much stronger notion of secrecy.

6 Conclusions

The described link between information reconciliation and privacy amplification for unconditionally-secure secret-key agreement can be summarized as follows. Assume that Alice knows a random variable W and that Bob and Eve have partial knowledge about W, characterized by the random variables W′ and V, respectively. These random variables could for instance result from the described satellite scenario with W and W′ being functions of [X, C] and [Y, C], respectively, and with V = [Z, C]. In order to state the results in the strongest possible form we consider a particular value V = v held by Eve rather than the average over all values of V.

When V gives less information than W′ about W, i.e., H(W |V) > H(W |W′), and a lower bound t > 0 on the collision entropy of Eve’s probability distribution of W is known, i.e., H_{c}(W |V = v) ≥ t, then Alice and Bob can generate a shared secret key S as follows. Alice and Bob exchange error-correcting information U consisting of k > H(W |W′) bits over the public channel such that Bob can reconstruct W, i.e., H(W |W′U) ≈ 0. Eve gains additional knowledge about W by seeing U = u. However, Corollary 5 shows that with probability at least 1 − 2^{−s} (over all values of U) where the security parameter s can be chosen arbitrarily, her collision entropy is bounded from below by H_{c}(W |V = v, U = u) ≥ t − 2k − 2s. Using privacy amplification, Alice and Bob can now generate an r-bit secret key S, where r has to be chosen smaller than t − 2k − 2s and Eve’s total information about S is exponentially small in t − 2k − 2s − r, namely less than 2^{r−(t−2k−2s)}/ ln 2 bits.

The main advantage of Theorem 4 is that it applies to any distribution and any reconciliation protocol whereas previously obtained results held only for particular distributions and protocols. However, as was demonstrated in Sections 4 and 5, a larger secret key than suggested by Theorem 4 can be obtained by Alice and Bob for special distributions. For instance, when Eve’s information V consists of a long sequence of independent random variables with identical distribution, then the term 2k + 2s above can be replaced simply by an expression on the order of k when non-interactive reconciliation is used. It is conceivable that the bound of Theorem 4 can be tightened for other special distributions than those treated in Sections 4 and 5, and possibly even for general distributions.

Acknowledgement

It is a pleasure to thank Charles Bennett, Gilles Brassard, Claude Crépeau, and Martin Gander for interesting discussions.

References

1. C. H. Bennett, F. Bessette, G. Brassard, L. Salvail, and J. Smolin, “Experimental quantum cryptography,” Journal of Cryptology, vol. 5, no. 1, pp. 3–28, 1992.

2. C. H. Bennett, G. Brassard, C. Crépeau, and U. M. Maurer, “Generalized privacy amplification.” Preprint, 1994.

3. C. H. Bennett, G. Brassard, and J.-M. Robert, “Privacy amplification by public discussion,” SIAM Journal on Computing, vol. 17, pp. 210–229, Apr. 1988.

4. E. Bernstein and U. Vazirani, “Quantum complexity theory,” in Proc. 25th Annual ACM Symposium on Theory of Computing (STOC), pp. 11–20, 1993.

5. R. E. Blahut, Principles and Practice of Information Theory. Reading, MA: Addison-Wesley, 1987.

6. G. Brassard and L. Salvail, “Secret-key reconciliation by public discussion,” in Advances in Cryptology — EUROCRYPT ’93 (T. Helleseth, ed.), vol. 765 of Lecture Notes in Computer Science, pp. 410–423, Springer-Verlag, 1994.

7. J. L. Carter and M. N. Wegman, “Universal classes of hash functions,” Journal of Computer and System Sciences, vol. 18, pp. 143–154, 1979.

8. W. Diffie and M. E. Hellman, “New directions in cryptography,” IEEE Transactions on Information Theory, vol. 22, pp. 644–654, Nov. 1976.

9. S. Lloyd, “A potentially realizable quantum computer,” Science, vol. 261, pp. 1569–1571, 1993.

10. U. M. Maurer, “Secret key agreement by public discussion from common information,” IEEE Transactions on Information Theory, vol. 39, pp. 733–742, May 1993.

11. U. M. Maurer, “The strong secret key rate of discrete random triples,” in Communications and Cryptography: Two Sides of One Tapestry (R. E. Blahut et al., eds.), Kluwer, 1994.

12. P. W. Shor, “Algorithms for quantum computation.” FOCS’94, 1994.