

Regular Papers Some Results on Secret Key Agreement Using Correlated SourcesAbstractThis paper introduces some results related to secret key agreement. We consider the situation in which legitimate users Alice and Bob and an eavesdropper Eve each has access to a correlated source. To transmit messages securely, Alice and Bob must agree on a secret key. Secret key agreement is the procedure for agreeing on a secret key by exchanging messages over a public channel.
1. IntroductionWhen two users want to exchange messages securely, they can use encryption as long as both of them know the secret key. We consider the situation in which legitimate users Alice and Bob and an eavesdropper Eve each has access to a correlated source. To transmit messages securely, Alice and Bob must agree on a secret key. Secret key agreement, which is introduced in [1], is the procedure for agreeing on a secret key by exchanging messages over a public channel (see Fig. 1). The colored arrows indicate information disclosure.The above situation can be achieved by introducing the scenario presented in [1] (see Fig. 2). In this scenario, a satellite broadcasts messages U that are unknown to Alice, Bob, and Eve. They have antennas that enable them to receive the messages. Inevitably, there is noise between the satellite and each antenna: these noises are independent. Thus, Alice, Bob, and Eve have access to correlated sources (X, Y, Z), which are the respective outputs of mutually independent channels with the input corresponding to the broadcast message. It should be noted that there is another scenario related to quantum cryptography [2]. By using a quantum channel, Alice and Bob can share a correlated sequence, while Eve can also acquire a sequence that is correlated with that of Alice and Bob by wiretapping the quantum channel (see Fig. 3).
To understand how secret key agreement is performed, we present an example of correlated sources that was introduced in [3]. Assume that there are only four cards {♠K, ♠Q, ♥K, ♥Q}. A trusted dealer shuffles these four cards and deals them to Alice, Bob, and Eve. Alice and Bob execute the following key agreement protocol at each deal.
In Fig. 4(a), let us assume that we are Bob. Bob has ♥K and knows that Alice also has ♥. Therefore, we can conclude that Alice must have ♥Q and we can agree on the key ‘1’. In Fig. 4(b), let us assume that we are Eve. Eve knows that both Alice and Bob have ♥, but she cannot know that who has ♥K or who has ♥Q, even when she has the other two cards. This implies that Alice and Bob can agree on 1 bit for a secret key. In Fig. 4(c), let us again assume that we are Bob. Bob has ♥K and knows that Alice has ♠, but not whether it is ♠K or ♠Q. In this case, Alice and Bob give up trying to achieve key agreement for this deal because neither of them can determine the partner’s card. The following are important goals in the study of secret key agreement.
It should be noted that the secret key capacity estimation is necessary in order to design a secure system. This paper deals with the following topics. In section 2, we review the formal definition of the secret key agreement protocol and the secret key capacity introduced by Maurer [1]. Section 3 describes a scheme for secret key agreement using correlated sources. We obtain the result that there is a pair of sparse matrices, known as lowdensity parity check (LDPC) matrices, that yields secret key agreement using correlated sources. Algorithms using sparse matrices are known to have practically efficient decoding algorithms such as the Belief Propagation (BP) algorithm [4] and Linear Codes Linear Program (LCLP) algorithm [5]. By using LDPC matrices with one of the practical decoding algorithms, our construction is computationally efficient. However, it should be noted that information reconciliation is performed only approximately. In section 4, we introduce the advantage distillation capacity, which provides a naive information theoretical expression for the secret key capacity introduced in [6], which is the least upper bound of the key generation rate of the secret key agreement. In section 5, we investigate the capacity for secret key agreement under a sampling attack. We analyze the supremum of the normalized secret key capacity defined as the supremum of the secret key capacity divided by the description length of the alphabet*, where the supremum is taken over some class of correlated sources. In particular, we consider symmetric sources and derive inequalities that show the scaling of the secret key capacity.
2. Definition of secret key agreement protocol and secret key capacityThe secret key capacity, which is the least upper bound of the key generation rate in the secret key agreement, was first introduced by Maurer [1]. Before defining it, we define the protocol that describes the procedure of Alice and Bob. Let X, Y, and Z be three sources available to Alice Bob, and Eve, respectively. Let X^{n} ≡(X_{1}, X_{2}, …, X_{n}), Y^{n}≡ (Y_{1}, Y_{2}, …, Y_{n}), and Z^{n}≡ (Z_{1}, Z_{2}, …, Z_{n}). The entropy of a random variable V, conditional entropy of random variable V with given random variable W, and mutual information between random variables V and W are denoted by H (V), H (V  W), and I (V ; W), respectively. Let C_{i}^{j} ≡ (C_{i}, …, C_{j}) for i ≤ j; here, the symbol C_{i}^{j} is ignored when i > j. Definition 1: A protocol (C_{1}^{t}, ˆX, ˆY ) for (X, Y, Z) with t steps is composed of the following procedure:
Formally, random variables (X^{n}, Y^{n}, Z^{n}, C_{1}^{t},ˆX,ˆY ) satisfy the following conditions: Y^{n} Z^{n} C^{t}_{i+1} ˆXˆY ↔ X^{n} C_{1}^{i1}↔ C_{i} if i is odd X^{n} Z^{n} C^{t}_{i+1}ˆX ˆY↔Y^{n} C_{1}^{i1}↔ C_{i} if i is even Y^{n} Z^{n}ˆY↔ X^{n}C_{1}^{t} ↔ ˆX X^{n} Z^{n}ˆX↔ Y^{n}C_{1 }^{t}↔ ˆY, where U ↔ V ↔ W denotes the Markov chain satisfying pUVW (u, v, w) = pUV (u, v) pWV (wv) for all (u, v, w). Definition 2: We call the protocol (C_{1}^{t}, ˆX, ˆY ) given in Definition 1 a secret key agreement protocol for (X, Y, Z) with rate R ≥ 0 if (C_{1}^{t}, ˆX, ˆY ) satisfies
for all ŠĆ > 0 and all sufficiently large n. The secret key capacity S(X;YZ) of the sources is defined as the least upper bound of such R for all possible key agreement protocols. Condition (1) means that we can perform a secret key agreement with an arbitrarily small error probability. Condition (2) means that the secret key and Eve’s information are mutually independent and she cannot obtain any information about the secret key. It should be noted that we consider (unconditional) information theoretical security [7], which is different from computational security [8] such as public key cryptography. An open problem has been to give the explicit information theoretical expression for the secret key capacity for general correlated sources. The upper and lower bounds of S(X;YZ) are given in [1], [9]. 3. Construction of secret key agreement protocol using LDPC matricesIn this section, we assume that I(X; Y) > I(X; Z) and that feedback is not allowed in the secret key agreement; that is, t=1. Let μXYZ be the joint distribution of (X^{n}, Y^{n}, Z^{n}). We assume that codes for correlated sources (X^{n}, Y^{n}, Z^{n}) satisfy
for any ε > 0 and all sufficiently large n, where (x, y, z) is the output of (X^{n}, Y^{n}, Z^{n}). Such codes can be constructed by using the LDPC matrices proposed in [10]. Let X be a finite field and x∈X^{n} be represented by a column vector. Let P and K be nR_{P} × n and nR_{K} × n LDPC matrices, respectively. We next define φ_{ P } and φ_{K} by We define φ_{Y} and φ_{Z} by A secret key agreement protocol is constructed below.
The error probability of the secret key agreement is expressed by = μXY ({(x, y): φ_{K} (ψ_{y}(φ_{P}(x), y)) ≠ φ_{K}(x)}). We have the following theorem. The proof is given in [10]. Theorem 1: Assume that μXYZ satisfies Eqs. (4) and (5). There are LDPC matrices K and P such that the above secret key agreement protocol (C_{1}, ˆX, ˆY ) satisfies for all δ> 0 and all sufficiently large n. 4. Secret key capacity and advantage distillation capacityIn this section, we introduce the advantage distillation capacity. According to [11], there are three phases in a secret key agreement. Advantage distillation: When the correlation between X and Y is weaker than or equal to those between X and Z and between Y and Z, i.e., I(X; Y) ≤ I(X; Z) and I(X; Y) ≤ I(Y; Z), the aim of this protocol (C_{1}^{t} , ˆX, ˆY ) is to provide Alice and Bob with an advantage over Eve; that is, I(ˆX; ˆY ) > I(ˆX; Z^{n}, C_{1}^{t} ) or I(ˆX; ˆY ) > I(ˆY; Z^{n}, C_{1}^{t} ). An example of this technique is presented in [1]. Information reconciliation: This technique allows Alice and Bob to obtain an identical random sequence from the output of (X, Y) by using this protocol while minimizing the amount of information leaked to Eve. Privacy amplification: This is a technique for obtaining a secret key sequence from the above identical random sequence. In section 3, the construction of a combined information reconciliation and privacy amplification protocol was provided by assuming that I(X; Y) > I(X; Z). In the following, we focus on an advantage distillation protocol and investigate the difference [I(ˆX; ˆY ) – I(ˆX; Z^{n}, C_{1}^{t} )]/n of a protocol (C_{1}^{t} , ˆX, ˆY ). Let us define the advantage distillation capacity. Definition 3: We call the protocol (C_{1}^{t} , ˆX, ˆY ) given in Definition 1 an advantage distillation protocol for (X, Y, Z) with rate R ≥ 0 if the difference [I(ˆX; ˆY ) – I(ˆX; Z^{n}, C_{1}^{t} )]/n is equal to R; that is, The advantage distillation capacity D(X;YZ) of the sources is defined as the least upper bound of such R for all possible advantage distillation protocols; that is, where the supremum is taken over n, t, and random variables (C_{1}^{t} , ˆX, ˆY ) generated by a protocol with step t. It should be noted that conditions (1) and (2) are not required for the advantage distillation protocol and that condition (3) is replaced by (6). These points are the differences from the definition of secret key capacity. We obtain the following theorem in relation to secret key capacity and advantage distillation capacity. Proof of this theorem is given in [6]. Theorem 2: Let X, Y, and Z be three sources available to Alice, Bob, and Eve, respectively. Then, S(X; YZ) = D(X; YZ). This theorem implies that we can construct an optimum secret key agreement protocol by using an advantage distillation protocol achieving advantage distillation capacity and a combined information reconciliation and privacy amplification protocol with rate [I(ˆX; ˆY ) – I(ˆX; Z^{n}, C_{1}^{t} )]/n for distilled sources (ˆX, ˆY, (Z^{n}, C_{1}^{t} )). The function D(X; YZ) provides information theoretical expressions of secret key capacity. It should be noted here that this expression is not a singleletter characterization and that the alphabets of random variables and the number of steps of a protocol are not bounded in the supremum. The singleletter characterization of the secret key capacity is presented in [9] for some particular source examples. 5. Secret key capacity for optimally correlated sources under a sampling attackIn the following, we investigate the satellite scenario introduced in [1], where three sources (X, Y, Z) have a common latent random variable U, and X, Y, and Z are the respective outputs of mutually independent channels for input U. Let U be the finite alphabet of U. Then, the joint probability distribution μXYZ of (X, Y, Z) is given by where PXU, PYU, and PZU are the conditional probability distributions of the respective channels and pU is a probability distribution corresponding to U. Then, we have for any random variable (X, Y, Z) with a common latent variable U, where the left inequality is given in [1]. Inequality (7) implies that the secret key capacity of the satellite scenario is zero if Eve has access to the latent variable. Next, we consider the situation where Eve obtains m samples z^{m}∈Z^{m}. Then, the joint probability corresponding to (X, Y, Z^{m}) is expressed by Furthermore, we assume that pZ_{i}U does not depend on i and we denote it by pZU. Then, from Eq. (7) and the result presented in [12], there exists α ≥ 0 such that where • denotes the cardinality of a set. This inequality implies that it becomes easier for Eve to predict the latent parameter U by a sampling attack and that the secret key capacity decreases exponentially as the number of Eve’s samples increases when α > 0. In the following, we assume that the statistical properties of the correlated source can be adjusted for a given number of Eve’s sources in order to optimize the secret key capacity. It should be noted here that it may be possible to increase the secret key capacity by increasing the size of the alphabet. In fact, the upper bound of Eq. (8) can be relaxed by increasing the alphabet size. On the other hand, it is natural to consider the cost of receiving one random symbol. For this reason, we define normalized secret key capacity by S(X; YZ^{m})/log_{2}A, where A is an alphabet of random variables X, Y, Z_{1} …, Z^{m}. We investigate the supremum of the normalized secret key capacity under a sampling attack defined in the following. Definition 4: For a given number m of Eve’s samples, we define the supremum of normalized secret key capacity ¯S (Sm) of the set of sources S by We introduce the following scenario for the definition of symmetric sources. A trusted server broadcasts message U, which is unknown to any users. Each terminal receives the message via mutually independent noisy channels. Thus, the correlated sources (A_{1}, …, A_{k}) are the respective outputs of mutually independent noisy channels with input U. We assume that channels have identical characteristics. We call a correlated source (A_{1}, …, A_{k}) symmetric if there are U, pU, and pAU such that where U is the alphabet of U. The following theorem states that the supremum of the normalized secret key capacity for the class of all symmetric sources is close to O(1/m). Theorem 3: The supremum of the normalized secret key capacity for symmetric sources S_{sym} under a sampling attack is bounded by The proof is given in [3]. 6. ConclusionWe studied the secret key agreement introduced in [1], which is a procedure for agreeing on a secret key by using correlated source outputs and exchanging messages over a public channel. First, we presented a practical secret key agreement protocol that uses LDPC matrices. Next, we analyzed the advantage distillation capacity, which provides a naïve information theoretical expression of the secret key capacity. Finally, we analyzed the secret key agreement under a sampling attack. We observed that the secret key capacity decreases exponentially as the number of Eve’s samples increases when the distribution of a channel is fixed. Then, we analyzed the supremum of normalized secret key capacity defined as the supremum of the secret key capacity for all possible sources. It is O(1/m) for symmetric sources. References
