9512.net
甜梦文库
当前位置:首页 >> >>

Practical Evaluation of Security for Quantum Key Distribution


Practical Evaluation of Security for Quantum Key Distribution
Masahito Hayashi1, ?
1

EARTO-SORST Quantum Computation and Information Project, JST 5-28-3, Hongo, Bunkyo-ku, Tokyo, 113-0033, Japan Superrobust Computation Project, Information Science and Technology Strategic Core (21st Century COE by MEXT)

arXiv:quant-ph/0602113v5 8 Jul 2006

Graduate School of Information Science and Technology, The University of Tokyo 7-3-1, Hongo, Bunkyo-ku, Tokyo, 113-0033, Japan

Abstract
Many papers proved the security of quantum key distribution (QKD) system, in the asymptotic framework. The degree of the security has not been discussed in the ?nite coding-length framework, su?ciently. However, to guarantee any implemented QKD system requires, it is needed to evaluate a protocol with a ?nite coding-length. For this purpose, we derive a tight upper bound of the eavesdropper’s information. This bound is better than existing bounds. We also obtain the exponential rate of the eavesdropper’s information. Further, we approximate our bound by using the normal distribution.
PACS numbers: 03.67.Dd,03.67.Hk,03.67.-a

?

Electronic address: masahito@qci.jst.go.jp

1

I.

INTRODUCTION

Quantum key distribution (QKD) was proposed by Bennett & Brassard [1] as a protocol (BB84 protocol) sharing secret keys by using quantum communication channel. Their original protocol assumes a noiseless quantum channel, but any quantum channel has noise in the realistic case. Hence, the security of the BB84 protocol in this realistic case had been an open problem for a long time, and has been proved by Mayers [2]. He showed that the protocol becomes secure when the protocol is constructed by combining classical error correction and randomly choosing a code for privacy ampli?cation. In his proof, the secure generation key rate is 1 ? h(2p) ? h(p) where p is the qubit error rate and h(p) is the binary entropy ?p log p ? (1 ? p) log(1 ? p) and the base of the logarithm is 2. He also gave a bound of Eve’s information for a ?nite length code. His discussion was extended to a more realistic framework by Inamori, L¨ utkenhaus & Mayers [3]. After Mayers’ proof, Shor & Preskill [4] proved the security based on the method of Calderbank-Shor-Steane (CSS) codes[5, 6]. Then, they proved the existence of code achieving the secure generation key rate 1 ? 2h(2p) and pointed the possibility of the secure generation key rate 1 ? 2h(p). After their discussion, treating the reliability of CSS codes, Hamada[7] showed the existence of the code attaining the secure generation key rate 1 ? 2h(p). He also derived a bound of Eve’s information for a ?nite length code, which yields the asymptotic secure generation key rate 1 ? 2h(p). However, they did not discuss the complexity of the encoding and decoding[4, 7], while the complexity of privacy ampli?cation is not so large in Mayers proof[2]. Following these researches, Christandl, Renner, & Ekert [8], Renner, Gisin, & Kraus [9], and Koashi [10] showed that the asymptotic secure generation key rate 1 ? 2h(p) is attained when the protocol is constructed by combining classical error correction and randomly choosing. However, they did not give the bound of Eve’s information of the ?nite-length code, explicitly. S. Watanabe, R. Matsumoto & Uyematsu [11] considered Eve’s information for a ?nite length code based on random privacy ampli?cation, which yields the asymptotic secure generation key rate 1 ? 2h(p). On the other hand, Stucki et al. [12] demonstrated quantum key distribution over 67 km between Geneva and Lausanne. Kimura et al. [13] succeeded 150 km QKD transmission with the error rate 8 – 9 %. Also Gobby et al. [14] did 122 km QKD transmission with 2

the error rate 8.9 %. Tanaka et al [15] demonstrated a continuous quantum key distribution over 16.3 km commercial use ?ber with 14 days, and Yuan & Shields [16] did it over 20.3 km installed telecom ?ber with 19 hours. In these experiments, they succeeded in realizing the real system that could become truly secure if the coding system with in?nite coding-length. Hence, there is no implemented system whose security is guaranteed. Thus, it is required to realize the error correcting code and the privacy ampli?cation for guaranteeing the security of the implemented QKD system. However, the required sizes of the error correcting code and the random privacy ampli?cation are not clari?ed for a given quantum bit error rate, e.g., 8 %. Therefore, many QKD experimental researchers want to know a tighter upper bound of Eve’s information for given sizes of the classical error correcting code and the random privacy ampli?cation. In this paper, we derive an upper bound of Eve’s information satisfying the following conditions, ?rst time. 1) The upper bound depends only on the size of random privacy ampli?cation. 2) By using this bound, the key generation rate 1 ? 2h(p) can be attained. In fact, Mayers’ discussion [2] gives the upper bound in the ?nite-length case, but his discussion yields the rate 1 ? h(2p) ? h(p) not the rate 1 ? 2h(p). The discussion by S. Watanabe et al. [11] yields the rate 1 ? h(p), but the bound depends on the error correction. Koashi’s discussion [10] satis?es the conditions 1) and 2), but his discussion does not clearly give the bound in the ?nite-length case. Further, the protocol in his paper [10] and his older paper [17] is slightly di?erent from the simple combination of the classical error correction and the random privacy ampli?cation. Our upper bound is also better than that by S. Watanabe et al. [11]. Moreover, it is shown that our evaluation cannot be further improved in the sense of the exponential rate when the classical error correcting code satis?es a speci?c condition. In this case, the exponential rate of our upper bound of Eve’s information can be attained by a collective attack, which is realized by individual operation to the channel and the collective operation to Eve’s local memory, while our bound is valid even for the coherent attack, which includes any Eve’s attacks allowed by the physical principle. That is, any coherent attack cannot improve the best collective attack in the sense of the exponential rate of Eve’s information. Indeed, Renner et al. [9] proved that it is su?cient to show the security for collective attacks for the treatment of the asymptotic key generation rate since any channel can be approximated by a separable channel by using random permutation. This result 3

can be regarded as the extension of Renner’s result to the exponential framework. Also, this implies that our evaluation gives the optimal (minimum) exponential rate of Eve’s information. There is another type of asymptotic treatment else the exponential treatment. In statistics, when the variable obeys the independent and identical distribution, its distribution can be approximated by the normal distribution. We also succeeded in approximating our upper bound by using the normal distribution. In this approximation, we treat the asymptotic
p× +?(? p× )) behavior when the size of the random privacy ampli?cation is given as the form 2nh(?

for the estimate p ?× of the phase error rate while in the large deviation case (the exponential
p× +? ?(? p× )/ rate case) we treat it when the size is given as the form 2nh(? √ n)

, where ? and ? ? are

functions of p ?× . Here, we should remark that our results cannot be obtained by the combination of existing results. The main technical point is the relation between Eve’s information and the phase error probability, which is given in Lemma 2. Owing to this lemma, Eve’s information can be bounded without any discussion of classical error correcting code for bit error. Further, in association with the error correction of phase error, we obtain an upper bound of the average error probability of a modi?ed random coding when minimum Hamming distance decoding is applied (Lemma 1). Combining these new techniques, we obtain the upper bounds (Theorems 1 and 2) through a long careful derivation. In the following, the organization of this paper is explained. First, we brie?y explain classical error correcting code, and describe our protocol using this knowledge in section II. In section III, we give an upper bound of Eve’s information per one code and that of Eve’s information per one bit. The random privacy ampli?cation corresponds to the random coding concerning the phase error. Hence, we treat the average error of random coding in section IV. Generalized Pauli channel is known as an important class of noisy channels. In quantum key distribution, the noisy channel does not necessarily belong to this class. However, if we use linear codes, we can treat any noisy channel as a generalized Pauli channel. We summarize notations and properties of generalized Pauli channel in section V. In section VI, we prove the main theorem by assuming a upper bound of Eve’s information when Eve’s attack is known. In section VII, we derive a relation between the phase error and Eve’s information. In section VIII, the bound used in section VI is proved by using the properties of generalized Pauli channel, the bound of average error and the relation obtained 4

in section VII. Further, we give the asymptotic behavior in the two asymptotic frameworks in section III. Asymptotic formulas for large deviation and limiting distribution are proved in Appendixes A and B, respectively. Based on this evaluation, we compare our large deviation bound with the bound by S. Watanabe, R. Matsumoto & Uyematsu [11]. Further, in section IX, we prove that the exponential rate of our bound of Eve’s information can be attained by the collective attack under a speci?c condition.

II.

PROTOCOL

In this section, we describe our protocol. Since our protocol employs the method of classical error correcting code, we ?rst explain classical error correcting code for the preparation of description of our protocol.

A.

Classical error correcting code

by a probability distribution {p, 1 ? p}. In this case, when we send a binary string (in Fn 2 ), the noise can be described by a binary string N and is characterized by the distribution P on Fn 2 . Then, when the input signal is described by the random variable X , the output signal is described by the random variable X + N . Error correcting code is a method removing the di?erence N . In an error correcting code with n-bit, we prepare an m-dimensional linear subspace C of Fn 2 , and the sender (Alice) and the receiver (Bob) agree that only elements of C is sent before the communication. This linear subspace is called a code or a [n, m] code. In this case, an encoding is given by a linear map G(C ) from Fm 2 to C . Of course, the map G(C ) is given as an m × n matrix with 0, 1 entries. Hence, when Bob receives an element out of C , he can ?nd that there exists a noise, and choose the most proper element among C based on the obtained binary string. Here, we can correct only one element among each equivalent class [X ] ∈ Fn 2 /C . More precisely, we choose the most likely noise Γ([X ]) among each equivalent class [X ]. This element is often called the representative, and the set of representatives is denoted by Γ. More generally, the decoding process is described by a map
m D : Fn 2 → F2 .

When the noise in a binary signal F2 = {0, 1} is symmetry, the binary channel is described

5

Hence, when Bob receives X + N , he decode it to X + N ? Γ([X + N ]) = X + N ? Γ([N ]). Thus, the decoding error is described by the behavior of the random variable N ? Γ([N ]), and does not depend on the input signal X . When the noise belongs to the set Γ, we can properly correct the error. The error probability is equal to 1 ? P (Γ). Suppose that there exists an eavesdropper (Eve) obtaining some information concerning the original signal X . In this case, we prepare a linear subspace C ′ of C and Alice sends the information as an element of C/C ′ . That is, when he sends an information corresponding to [X ] ∈ C/C ′ , he chooses one element among [X ] with the equal probability, and sends it. This operation is called privacy ampli?cation.

B.

Our protocol

Using this method, we can reduce Eve’s information. However, it is not easy to evaluate how much information Eve has in this case. The purpose of this paper is evaluating Eve’s information. In this case, the probability that Bob recovers the original information correctly we choose each linear subspace C ′ of C with the equal probability and we regard C as Fm 2
′ ′ is equal to P(Γ + C ′ ), where Γ + C ′ := {Γ([X ]) + X ′ |X ∈ Fn 2 , X ∈ C }. In addition, when m?m ? ?m ? is called the universal hashing function. , the function from Fm and C/C ′ as Fm 2 2 to F2

This function is can be constructed as an (m ? m ? ) × m matrix by choosing the elements with the uniform distribution. Using this preparation, we brie?y describe our protocol for quantum key distribution that can be realized by small complexity. After this description, we present it precisely. In our protocol, after quantum communication, Alice and Bob check their basis by using public channel, announce a part of obtained bits, and estimate the bit error rate p+ and phase error rate p× . Here, we denote Alice’s remaining bit string with the + basis and the × basis by ? + and X ?×. X+ and X× , respectively. Similarly, we denote Bob’s remaining bit string by X ?+ These bit strings are called raw keys. Hence, the rates of 1 in the di?erence N+ = X+ ? X ? × are almost equal to p+ and p× , respectively. and the di?erence N× = X× ? X

Using the following process, Alice and Bob remove their errors and share the bit string with almost no error. Alice generates another bit string X ′ and sends the bit string K := ?+ = X ′ + X+ to Bob. Based on the information K , Bob obtains the information X ′′ := K ? X X ′ + N+ . Using this method, we can realize a classical channel with the input X ′ and the 6

output X ′′ . The error rate of this channel is almost equal to p+ . By applying classical error correction to this channel, Alice and Bob can share bit string with almost zero error. In this case, Alice generates an element X ′ ∈ Fm ? = C , and Bob recovers X ′′′ = D (X ′′ ). Then, X ′′′
2

coincides with X ′ in a high probability. Finally, Alice and Bob perform the above mentioned

hashing function for their respective keys. That is, Alice generates the (m ? l) × m matrix A with the rank m ? l randomly, and send this matrix. Then, Alice and Bob obtain their ?nal keys AX ′ and AX ′′′ . Therefore, the rate of ?nal key to the raw key is equal to R =
m?l . n

Roughly speaking, it

is suitable to choose m as an integer a little smaller than (1 ? h(p+ ))n, and m ? as an integer a little larger than h(p× )n. Then, the generation rate R is almost equal to 1 ? h(p+ ) ? h(p× ). In the following, we describe our protocol more precisely. For this purpose, we need some mathematical notations. The quantum system of each quantum signal is the two-dimensional Hilbert space H2 , which is spanned by the {|a }a∈F2 . We need to ?x integers n+ , l+ , m+ , n× , l× , and m× that describe the size of our code. For a classical error correction, we choose an m+ -dimensional classical code C1,+ in F2 + (an m-dimensional linear space C1,+ of F2 + ), and an m× -dimensional classical code C1,× in F2 × . We also ?x the thresholds k + , k + , k × , and k × , and the allowable statistical ?uctuation δk for each count k of error. (i) The sender, Alice, and the receiver, Bob, repeat steps (ii)–(iv) for each i. (ii) Alice chooses a random bit ai and a random bit bi . (iii) Bob chooses a random bit ci . (iv) When bi = 0, Alice sends the quantum state |ai , otherwise, does the state
1 (?1)ai |1 . In the following, {|0 , |1 } is called the + basis, and { √ (| 0 + | 1 2 1 √ (| 0 2 1 ), √ (| 0 2 n n n

+ ?

|1 )} is called the × basis. (v) Alice and Bob announce bi and ci and discard any results for bi = ci . They obtain n+ + l+ bits sequence with bi = ci = 0, and n× + l× bits sequence with bi = ci = 1. (vi) Alice randomly chooses l+ check bits X+,c,1, . . . , X+,c,l+ among n+ + l+ bits with the + basis and l× check bits X×,c,1, . . . , X×,c,l+ among n× + l× bits with the + basis, announces the positions of these bits, and sends their information. They obtain the estimates p ?+ and p ?× with the respective basis. That is, they count the number of error 7

? +,c,i }| and k× = |{i|X×,c,i = X ? ×,c,i }|, where X ? +,c,i and X ? ×,c,i bits k+ = |{i|X+,c,i = X are Bob’s check bits. However, when k+ is greater than the threshold k + , they discard their remaining bits with the × basis. When k× is greater than the threshold k × , they discard their remaining bits with the + basis. Further, when k+ is less than the other threshold k + , they replace k+ by k + . When k× is less than the other threshold k × , they replace k× by k × . In the following, we treat only the bit string of the + basis. We denote Alice’s (Bob’s) ? + ). After this process, they apply the remaining n+ -bit strings with the + basis by X+ (X same procedure to the remaining bit strings with the × basis. (vii) Alice generates Z+ ∈ F2 + randomly, and sends Bob G(C1,+ )Z+ + X+ . ? + ∈ Fn+ . Performing the decoding of the (viii) Bob obtains the signal G(C1,+ )Z+ + X+ ? X 2 m+ m + ?+ ∈ F . code C1,+ ≈ F , he obtains Z
2 2 m

(ix) Alice chooses m ? := n× h(k× /l× + δk× )-dimensional subcode C2,+ (Y+ , k× ) ? F2 + based
m

m

on random variables Y+ such that any element x = 0 ∈ F2 + belongs to C2,+ (Y+ , k× )
2
n+ h(k× /l× +δk ) ×

with the probability

2m+ ?1

?1

.
m

(x) Alice obtains the secret information Z + := [Z+ ]C2,+ (Y+ ,k× ) ∈ F2 + /C2,+ (Y+ , k× ). ?+ (xi) Bob obtains the secret information Z +,B := Z
m C2,+ (Y+ ,k× )

∈ F2 + /C2,+ (Y+ , k× ).

m

For example, s-dimensional code C2 (Y, s) in F2 + is constructed based on k random variables Y := (X1 , · · · , Xs ) in F2 + as C2 (Y, s) := X1 , · · · , Xs , where Y obeys the uniform distribution on the set {Y |X1 , · · · , Xs are linearly independent.}.
C. Extension of our protocol
m

Indeed, in the realistic case, the bottleneck is often the estimation error of the error rate. Hence, in order to decrease the error of the estimation of the phase error rate p× , we propose the following the modi?ed protocol for any integer a. In the modi?ed protocol, we repace steps (v) and (vi) by the following, and add the step (xii). (v) Alice and Bob announce bi and ci and discard any results for bi = ci . They obtain an+ + l+ bits sequence with bi = ci = 0, and an× + l× bits sequence with bi = ci = 1. 8

(vi) Alice randomly chooses n+ bits among remaining an+ bits with + basis and obtain n+ bit string X+ . She also sends the her positions to Bob. Bob obtains the n+ bit ? + . They do the same procedure for the × basis. string X (xii) They repeat steps (vii) – (xi) a times. In the above protocol, the estimation of the phase error p× has the same accuracy as that of the ?rst protocol with al× check bits of the × basis.
III. SECURITY

In this section, we evaluate the security of our protocol. In the following, for simplicity, we abbreviate l× and n+ by l and n, respectively.
A. Finite-length case

The security of this protocol is evaluated by the mutual information I (Z + , ZE ) between Alice’s ?nal key Z + and eavesdropper(Eve)’s information ZE . It is mathematically de?ned by I (Z + , ZE ) := ? +
Z+

P (ZE ) log P (ZE )
ZE

P (Z + )
ZE

P (ZE |Z + ) log P (ZE |Z + ).

In order to evaluate this value, we have to treat the hypergeometric distribution n ( l )(j? k) . This is because the random sampling obeys the hypergeometPhg (k |n, l, j ) := k n+ l (j ) (n+l?j ) ric distribution. It is known that its average is nlj and its variance is (njln . In this +l +l)2 (n+l?1) paper, we focus on the average of Eve’s information Epos× ,k× ,Y+ |pos+ ,k+ ,Y× [I Z + , ZE ] for each n, l, where pos+ and pos× are the random variables indicating the positions of the check bit of × basis and + basis, respectively. Some papers [2, 4, 10, 11, 17] guarantee the security by proving that for any ?1 > 0 and ?2 > 0 there exist integers n and l such that P (I Z + , ZE ≥ ?2 ) ≤ ?1 . Indeed, when Epos× ,k× ,Y+ |pos+ ,k+ ,Y× I Z + , ZE (1)

≤ ?1 ?2 , Markov inequality guarantees the

inequality (1). Hence, we can recover the probabilistic behavior (1) of Eve’s information from 9

the evaluation of the average of Eve’s information. Therefore, in this paper, we concentrate the evaluation of the average of Eve’s information. Theorem 1 When R is the rate of the code C1 and the threshold k is less than n , we have 2 Epos× ,k× ,Y+ |pos+ ,k+ ,Y× I Z + , ZE where ≤ P (δ, n, l, k, k ), (2)

k

k

? P (δ, n, l, k, k) := max h
j k =0 k

Phg (k |n, l, j )f (j ? k, k |n, l, δk ) +

k =k+1

Phg (k |n, l, j )f (j ? k, k |n, l, δk )

+ max
j k =0

Phg (k |n, l, j )f (j ? k, k |n, l, δk )n(R ? h(k/l + δk ))
k

+
k =k+1

Phg (k |n, l, j )f (j ? k, k |n, l, δk )n(R ? h(k/l + δk )) ,

and ? ? h(x) x < 1/2 ? h(x) := ?1 x ≥ 1/2 ? ′ ? min{2n(h( k )?h( k +δ)) n l , 1} if k ′ < n/2 ′ f (k , k |n, l, δ ) := ?1 if k ′ ≥ n/2.

Further, Eve’s information per one bit is evaluated as follows. Theorem 2 When R is the rate of the code C1 , we have Epos× ,k× ,Y+ |pos+ ,k+ ,Y× ? (δ, n, l, k, k ), ≤P where

I Z + , ZE n(R ? h(k× /l× + δk× ))

10

? (δ, n, l, k, k) P 1 ? := max h j n(R ? h(k/l + δk ))
k k k

k =0

Phg (k |n, l, j )f (j ? k, k |n, l, δk ) +
k

k =k+1

Phg (k |n, l, j )f (j ? k, k |n, l, δk )

+ max
j k =0

Phg (k |n, l, j )f (j ? k, k |n, l, δk ) +

k =k+1

Phg (k |n, l, j )f (j ? k, k |n, l, δk ) .

The proofs of these theorems are divided into two parts: (i)The security of known channel (section VIII), (ii)The security of unknown channel, which is given by estimating the channel and employing the part (i) (section VI). For treatment of quantum channel, we prepare the notations of generalized Pauli channel in section V. For the discussion of the part (i), we derive a bound of average error concerning classical error correcting code in Section IV, and a bound of Eve’s information using the phase error in Section VII.

B.

Approximation using normal distribution

In the following, we calculate the above value approximately. For this purpose, we choose
1 , and a continuous function p → ? ?(p). When k = pl, k = pl, two probabilities p < p < 2 n n+l ?(p) ? √ , n+l

= r , δk =

as is shown in Appendix A, we obtain ? (δ, n, l, k, k ) = max Φ ? lim P
p∈[p,p]

n→∞

p(1 ? p)

r (1 ? r )

?(p) , ?

(3)

where the distribution function Φ of the standard Gaussian distribution:
x

Φ(x) :=
?∞
k (1? k ) l l l n n+l n+l

1 ?x2 /2 e dx. 2π

1 ? √n +l

Hence,√ in order to keep the security level ε per one bit, it is suitable to choose δk to be Φ?1 (ε) = ?
n+l nl k (1 l

? (δ, n, l, k, k) can be approximated ?k )Φ?1 (ε) when P l
nl l

by the RHS of (3). That is, our upper bound is almost determined by √ k n+l k δk . Now, we consider the case when we use a low-density-parity-check (LDPC) code as the code C1 [18]. In this case, the case of R = 0.5, and n = 10, 000 is one realistic case. As an realistic case, let us consider the case l = 1, 000, p = 0.075, δk× = 0.01. Then, we
nl nl

(1? l )

have? √ k n+l k δk = ?1.14. The security level Φ ? √ k n+l k δk = 0.126 is not su?cient.
l

(1? l )

l

(1? l )

11

However, it is not easy to increase the size n. Hence, we adopt the modi?ed protocol. In this case, we replace only l by the following values. In the case of l = 20, 000, the security level is almost 0.001. l ?√k
l nl n+l

1,0000 10,000 δk ?1.14 ?2.68

20,000 ?3.10

30,000 ?3.29

40,000 ?4.00

50,000 ?3.47

(1? k ) l
nl

Φ ? √ k n+l k δk
l

(1? l )

0.126 0.00363 0.000968 0.000505 0.000342 0.000264

C.

Large deviation

Next, we focus on the large deviation type evaluation. Choose a function p ∈ [p, p] → ?(p) and de?ne E (?, r, p, p) := min h(p + r (?(p) ? ?′ ))

p∈[p,p],?′ ≥0

? (1 ? r )h(p) ? 2rh(p + ?(p) ? ?′ ) + rh(p + ?(p)) . When k = pl, r =
n , n+l

δk = ?( k ), as is shown in Appendix B, we obtain l E (?, r, p, p) = lim ?r log P (δ, n, l, k, k ). n→∞ n (4)

Further, P (δ, n, l, k, k ) ≤k (n + l + 1)n(R ? h(p + δp ))2 + h(k (n + l + 1)2
?n E (?,r,p,p) r

?n E (?,r,p,p) r

).

(5)

Hence, given a ?xed real number E , it is suitable to choose ?(p) satisfying that h(p + r (?(p) ? ?′ )) ? (1 ? r )h(p) E = min ′
? ≥0

? 2rh(p + ?(p) ? ?′ ) + rh(p + ?(p))

12

for any probability p ∈ [p, p]. Further, when ?(p) is su?ciently small, using the relation ?p ? (p?q )2 d(p q ) := p log p + (1 ? p) log 1 , we have the approximation. q 1?q = p(1?p) ln 2 h(p + r (?(p) ? ?′ )) ? (1 ? r )h(p) ? rh(p + (?(p) ? ?′ )) + rh(p + ?(p)) ? rh(p + (?(p) ? ?′ )) =(1 ? r )d(p p + r (?(p) ? ?′ )) + rd(p + ?(p) p + r (?(p) ? ?′ )) (1 ? r )2 (?(p) ? ?′ )2 r 2 (?(p) ? ?′ )2 ? +r + rh′ (p)?′ . =(1 ? r ) p(1 ? p) p(1 ? p) In this approximation, when ?(p) is small enough, the minimum is attained at ?′ = 0. Hence, h(p + r (?(p) ? ?′ )) ? (1 ? r )h(p) ? rh(p + ?(p) ? ?′ ) min ′
? ≥0

+ r (h(p + ?(p)) ? h(p + (?(p) ? ?′ )))

+ rh(p + ?(p)) ? rh(p + ?(p) ? ?′ ) =h(p + r?(p)) ? (1 ? r )h(p) ? rh(p + ?(p)). (6)

The maximum value of ?(p) satisfying (6) corresponds to the critical rate in the classical channel coding theory. Therefore, when the number ?(p) is su?ciently small for each p ∈ [p, p], we obtain E = h(p + r?(p)) ? (1 ? r )h(p) ? rh(p + ?(p)) ? = r (1 ? r )?(p) , (log 2)(p + r?(p))(1 ? (p + r?(p))) (ln 2)Er (1 ? 2p) 2(r (1 ? r ) + (ln 2)Er 2) + ? =
2

(7)

?p ∈ [p, p].

Hence, in this case, in order to keep the exponential rate E , we choose ?(p) as ?(p) =

p(1 ? p) r (1 ? r )

(ln 2)2 E 2 r 2 + 4p(1 ? p)r (1 ? r )(ln 2)E 2(r (1 ? r ) + (ln 2)Er 2 ) (ln 2)E as E → 0.

Here, we compare our bound with that by S. Watanabe, R. Matsumoto & Uyematsu [11]. Since their protocol is di?erent from our protocol, we compare our protocol with their protocol with the same size of code. This is because the size of the code almost corresponds to the cost of its realization. Then, their case corresponds to our case with p = p = p and l = n. They derived the following upper bound (8) of the security in their protocol when 13

⊥ ⊥ the codes C2 ? C1 satisfy the following conditions: The codes C1 /C2 and C2 /C1 have the

decoding error probability ε when the channel is the binary symmetric channel with the error probability p. Epos× ,k× |pos+ ,k+ I Z + , ZE ?(p)2 n ≤h(2( + 1)2 ε + 4(n + 1)2 e? 4 n ) 2 ?(p)2 n + 4n( + 1)2 ε + 8n(n + 1)2 e? 4 n . 2

(8)

However, even if the error probability ε is zero, our evaluation (5) is better than their evaluation (8). In particular, when ?(p) is su?ciently small, we can use (6). From Pinsker inequality: (ln 2)d(p q ) ≥ (p ? q )2 [19], our exponential rate is evaluated as ln 2 (h(p + r?(p)) ? (1 ? r )h(p) ? rh(p + ?(p))) r ln 2 ((1 ? r )d(p p + r?(p)) + rd(p + ?(p) p + r?(p))) = r ?(p)2 , ≥(1 ? r )?(p)2 = 2 which is greater than their rate
?(p)2 4

even in the case of ?′ = 0. Further, our coe?cient is

smaller than their coe?cient in this case as follows: k (n + l + 1)n(R ? h(p + δp )) ≤pn(n + n + 1)nR < 8n(n + 1)2 , k (n + l + 1) = pn(n + n + 1) < 4(n + 1)2 because p ≤ 1/2. Hence, in order to obtain a tighter bound, it is better to use our formula (2).

IV. A.

ERROR CORRECTING CODE Type method

In this section, we treat classical error correcting code. For this purpose, we review the type method for binary strings. For any element x ∈ Fn 2 , we de?ne |x| := |{i|xi = 1}| and
k Tn := {x ∈ Fn 2 | |x| = k }. Further, the number of elements is evaluated by

1 nh(k/n) k 2 ≤ |Tn |= n+1

n k 14

k ≤ | ∪k′ ≤k Tn | ≤ 2nh(k/n)



(9)

? for k ≤ n/2. For any distribution P on Fn 2 , we de?ne distribution P on {0, . . . , n} and Pk
k on Tn as

Hence, we have

? (k ) := P (T k ) P n ? ? P (x) , if x ∈ T k n ? (k ) P Pk (x) := ?0 otherwise.
n

P (x) =
k =0

? (k )Pk (x). P

B.

Bound for random coding

In this paper, we focus on linear codes, which are de?ned as linear subspaces of Fn 2 . For the preoperation of the following section, we consider the error probability when the noise of classical communication channel is given as a classical channel W (a stochastic transition
n matrix) on Fn 2 . If a channel W is written by a distribution PW on F2 as

W (y |x) = PW (y ? x), it is called an additive channel. For an additive channel W , we de?ne the following distribution: PW (k ) := PW {x||x| = k }. In order to protect our message from the noise, we often restrict our message to be sent in a subset of Fn 2 . This subset is called a code. When the noise is given by an additive channel, a linear subspace C of Fn 2 is suitable for our code because of the symmetry of the noise. Hence, in the following, we call a linear subspace C of Fn 2 a code. Now, for a preoperation of the following section, we consider the error correcting code using a pair of codes C1 ? C2 . In order to send any information [x2 ]1 ∈ C2 /C1 , we send class divided by Ci . In this case, the decoder is described by the map D from Fn 2 to itself. When the channel is given by W , the average error probability is Pe,W (D ) = 1 |C2 /C1 | 1 | C1 | x W (y |x2 + x1 ). x1 + x2 by choosing x1 ∈ C1 with the uniform distribution, where [x]i denotes the equivalent

[x2 ]1 ∈C2 /C1

1 ∈C1 D (y )=[x2 ]

15

However, we often describe our decoder by the coset representative Γ([x]2 ) for each [x]2 ∈
Γ Fn 2 /C2 . That is, when the decoder receives the element y , he decodes it to D (y ) :=

[y ? Γ([y ]2 )]1 . When the channel is given by a additive channel W , the error probability is Pe,W (D Γ ) = 1 ? PW (Γ + C1 ), where Γ := {Γ([x]1 )|[x]1 ∈ Fn 2 /C2 }, and Γ + C1 = {x + x1 |x ∈ Γ, x1 ∈ C1 }. For example, when we choose the minimum Hamming distance decoding DC2 /C1 : DC2 /C1 (y ) := argmin min |y ? (x1 + x2 )|.
[x2 ]1 ∈C2 /C1 x1 ∈C1

By using the map Γ([x]2 ): Γ([x]2 ) = x + argmin |x + x2 |,
x2 ∈C2

it can be written as DC2 /C1 (y ) = [y ? Γ([y ]2 )]1 . In the following, we denote the above Γ by ΓC2 . Now, we consider the average error when we choose the larger code C2 randomly. Lemma 1 Let C1 be a arbitrary [n,t] code (C1 ? Fn 2 ). We randomly choose the t + l2l+t ?2t . 2n ?2t

dimensional code C2 (X ) ? C1 such that any element x ∈ Fn 2 \ C1 belongs to C2 (X ) with the probability Then, any additive channel W satis?es EX [Pe,W (D ΓC2 (X ) )] = EX [1 ? PW (ΓC2 (X ) + C1 )]
n

≤ where

k =0

?W (k )g (2l+t?n |n, k ), P

Proof:

n Let Tk be the set {x ∈ Fn 2 ||x| = k }. Then, P (x) = n ? (k )Pk (ΓC (X ) + C1 ). P (ΓC2 (X ) + C1 ) = k=0 P 2

? ? min{2nh(k/n) x, 1} k ≤ ?n/2? g (x|n, k ) := ?1 k > ?n/2?.

n ? k =0 P (k )Pk (x).

Hence,

n Indeed, if y ∈ Tk ? Fn 2 does not belong to ΓC2 (X ) + C1 , there exists an element x ∈

C2 (X ) \ C1 such that |y ? x| ≤ k . Hence, the probability that at least one element belongs 16

?2 for k ≤ n/2 because |{x||x ? y | ≤ k }| = to the set {x||x ? y | ≤ k } is less than 2nh(k/n) 22n ? 2t

l+t

t

|{z ||z | ≤ k }| ≤ 2nh(k/n) . (See (9).) Therefore,

EX [1 ? Pk (ΓC2 (X ) + C1 )] ≤ Pk (y )2nh(k/n)
k y ∈Tn

2 l +t ? 2 t 2n ? 2t

≤2nh(k/n)

l +t 2 l +t ? 2 t nh(k/n) 2 ≤ 2 2n ? 2t 2n

for k ≤ n/2, where the last inequality follows from l + t ≤ n. This value is also bounded by 1. Hence, EX [1 ? P (ΓC2 (X ) + C1 )]
n

=
k =0 n

? (k )EX [1 ? Pk (ΓC (X ) + C1 )] P 2 ? (k )g (2l+t?n |n, k ). P



k =0

V.

GENERALIZED PAULI CHANNEL

In this section, for the preparation of our proof, we give some notations concerning generalized Pauli channels. In order to describe it, for any two elements x = (x1 , . . . , xn ), y = (y1 , . . . , yn ) ∈ Fn 2 , we use the product:
n

x · y :=

xi yi .
i=1

?n Thus, the space H2 = (C2 )?n is spanned by the {|x }x∈Fn . Now, we de?ne the unitary 2

matrices Xx and Zz for x, z ∈ Fn 2 as:

Xx |x′ = |x′ ? x Zz |x′ = (?1)x ·z |x′ . From the de?nition, we have the relation [20]. (Xx Zz )(Xx Zz ) = (?1)x·z ?x ·z (Xx Zz )(Xx Zz ). 17
′ ′ ′ ′ ′ ′ ′

When the channel Λ has the form: Λ(ρ) =
x,z ∈Fn 2

PΛ (x, z )(Xx Zz )ρ(Xx Zz )? ,

it is called a generalized Pauli channel. Indeed, a generalized Pauli channel is a quantum analogue of an additive channel. In fact, it is known [21, 22] that the channel Λ is generalized Pauli if and only if Λ(ρ) = (Xx Zz )? Λ((Xx Zz )ρ(Xx Zz )? )(Xx Zz ), For any channel Λ, we often focus on its twirling Λt de?ned as Λt (ρ) := 1 22n Λx,z (ρ)
x,z ∈Fn 2

?x, z ∈ Fn 2.

(10)

Λx,z (ρ) := (Xx Zz )? Λ((Xx Zz )ρ(Xx Zz )? )(Xx Zz ). From (10), the twirling Λt is always a generalized Pauli channel. In the treatment of generalized Pauli channels, the distribution PΛ (x, z ) is important. Hence, we introduce some notations for this distribution. We de?ne the distributions PΛ,X (x) and PΛ,Z (z ) as PΛ,X (x) :=
z ∈Fn 2

PΛ (x, z ),

PΛ,Z (z ) :=
x∈Fn 2

PΛ (x, z ).

These are called marginal distributions. We also de?ne the conditional distribution as PΛ,Z |X (z |x) := PΛ (x, z ) . PΛ,X (x)

Next, we treat a generalized Pauli channel Λ on the tensor product system (C2 )?n1 ? (C2 )?n2 .

18

In this case, we use the following notation. PΛ,1 (x1 , z1 ) :=
n x2 ,z2 ∈F2 2

PΛ (x1 x2 , z1 z2 ) PΛ (x1 x2 , z1 z2 )
n x1 ,z1 ∈F2 1

PΛ,2 (x2 , z2 ) := PΛ,X,i (xi ) :=
n zi ∈F2 i

PΛ,i (xi , zi ) PΛ,i (xi , zi )
n xi ∈F2 i

PΛ,Z,i(zi ) := ?Λ,Z,1,2(k1 , k2 ) := P
n xi ∈F2 i

k1 k2 PΛ,Z (Tn × Tn ) 1 2
n

(11)

PΛ,1|Z,2(x1 , z1 |z2 ) := PΛ,Z,1|Z,2(z1 |z2 ) :=

x2 ∈F2 2

PΛ,1|Z,2(x1 x2 , z1 z2 ) PΛ,Z,2(z2 )

n x1 ∈F2 1

PΛ,1|Z,2(x1 , z1 |z2 ).

?Λ,Z,1,2 is di?erent from P ?Λ,Z . These notations will be used in the following Note that P sections.

VI. A.

PROOF OF MAIN THEOREM Modi?ed protocol

In this section, we prove Theorem 1 by treating the security of the following protocol. In the following protocol, we ?x the generalized Pauli channel Λ from n-qubits system to itself.
n (i) Alice generates Z+ ∈ Fm 2 randomly, and sends Bob G(C1 )Z+ ∈ F2 with the + basis

through the n-qubits generalized Pauli channel Λ. (ii) Bob measures the received n qubits with the + basis. Performing the decoding of the ?+ ∈ Fm . code C1 ≈ Fm , he obtains Z
2 2

(iii) They do the processes (ix) – (xi) of the previous protocol. In this case, we assume that the dimension of the code C1 (the subcode C2,+ (Y+ )) is t (s). This protocol is the special case that the channel is known. 19

For any channel Λ from the system H to itself, the state on the environment system can be described by using its Stinespring representation (HE , U, |0 Λ(ρ) = TrHE Uρ ? |0
E E E

∈ HE ):

0| U ? .

That is, the state on the environment system is characterized by another channel ΛE (ρ) := TrHn Uρ ? |0 2
E E

0| U ? .

In this above protocol, the distribution of Eve’s signal ZE is described by a POVM MZE on HE as P (ZE |Z ) = Tr MZE ΛE (ρZ ). Therefore, in order to evaluate the classical mutual information I (Z, ZE ) it is su?cient to evaluate the quantum mutual information (Holevo information)
1 I ([z ] ∈ C1 /C2 (Y ), ρΛ,E

C /C2 (Y )

([z ])) ([z ])
C /C2 (Y )

:=

1

2m?s

1 Tr ρΛ,E

C /C2 (Y )

[z ]∈C1 /C2 (Y )
1 · log ρΛ,E

C /C2 (Y )

1 ([z ]) ? log ρΛ,E

, and
1 ρΛ,E

(12)
C /C2 (Y )

where
1 2t?s

1 ρΛ,E

C /C2 (Y )

([z ])
C /C2 (Y )

:=

z2 ∈C2 (Y )

[z ]∈C1 /C2 (Y )

1 ρΛ,E

ΛE (|z + z2 z + z2 |)

:=

([z ]). In the following, we often abbreviate (12) as IH (Z, ZE ).

Theorem 3 We can evaluate Eve’s information as follows.
1 EY+ I ([z ] ∈ C1 /C2 (Y+ , s), ρΛ,E

C /C2 (Y )

([z ]))

n

≤ηm?s

k =0

?Λ,Z (k )g (2?s|n, k ) , P

where m = dim C1 and ηk is de?ned as ηk (x) := h(x) + kx. This theorem will be proved in Section VIII.

B.

Proof of Theorem 1

Now, we back to our main protocol. First, we ?x the random variables pos+ , k+ , Y× . Then, it is su?cient to treat the quantum system of the n+ + l× qubits. In the following, 20

we characterize the system of raw keys Cn by the subscript k , and the other system of check qubits Cl× by the subscript c. Hence, we denote the quantum channel of this system by Λ. Note that Λ is not necessarily generalized Pauli. In the following, we abbreviate l× , pos× , k× , Y+ by l, pos, k, Y , respectively. In this case, the variable pos takes a subset of l elements {i1 , . . . , il } ? {1, . . . , n + l}, where i1 < . . . < il . Then, we de?ne the unitary matrix Upos as Upos (ui1 ? · · · ? uil ? uj1 ? · · · ? ujn ) = u1 ? · · · ? un+l , where {j1 , . . . , jn } = {i1 , . . . , il }c and j1 < · · · < jn . Every subset is choosed with the probability
1
l (n+ l )

. We also de?ne the channel Λpos for any channel Λ as
? ? Λpos (ρ) := Upos (Λ(Upos ρUpos ))Upos .

Then, we can show that (Λpos )t = (Λt )pos . Hence, any generalized Pauli channel Λ satis?es ?Λpos ,Z,k,c(kk , kc ) Epos P ?Λ,Z (kk + kc )Phg (kc |n, l, kk + kc ), =P where we used the notation given in (11). Now, we consider the case where Alice and Bob choose the variable pos and obtain the di?erence zc between their check bit with the × basis. When k ≤ |zc | ≤ k , the average of Eve’s ?nal information is evaluated as EY+ I ([z ] ∈ C1 /C2 (Y+ , nh(
n

(13)

(14)

|zc | C1 /C2 (Y ) + δ|zc | )), ρ(Λ pos,z ,E ([z ])) t) l

≤h

k =0

?(Λt )pos ,Z,k|Z,c(k |zc )f (k, |zc | |n, l, δk ) P

+ n(R ? h(|zc |/l + δk ))
n

·

k =0

?(Λt )pos ,Z,k|Z,c(k |zc )f (k, |zc | |n, l, δk ). P

(15)

21

When |zc | < k , we obtain k C1 /C2 (Y ) EY+ I ([z ] ∈ C1 /C2 (Y+ , nh( + δk )), ρ(Λ pos,z ,E ([z ])) t) l
n

≤h

k =0

?(Λt )pos ,Z,k|Z,c(k |zc )f (k, k|n, l, δk ) P

+ n(R ? h(k/l + δk ))
n

·

k =0

?(Λt )pos ,Z,k|Z,c(k |zc )f (k, k |n, l, δk ). P

(16)

Of course, when |zc | > k , the average of Eve’s ?nal information is equal to zero because any information is discarded in this case. The inequalities (15) and (16) will be shown in Appendix C by using Theorem 3. Finally, we take the expectation concerning zc and pos:

1 2 Epos Ezc EY+ I ([z ] ∈ C1 /C2 (Y+ , nh(|zc |/l + δ|zc | )), ρ(Λ pos,z ,E ([z ])) t)

C /C (Y )

k

k

≤h max
j

kc =0 k

Phg (kc |n, l, j )f (j ? k, k |n, l, δk ) +

kc =k+1

Phg (kc |n, l, j )f (j ? kc , kc |n, l, δkc )

+ max
j kc =0

Phg (kc |n, l, j )n(R ? h(k/l + δk ))f (j ? k, k |n, l, δk )
k

+
kc =k+1

Phg (kc |n, l, j )n(R ? h(kc /l + δkc ))f (j ? kc , kc |n, l, δk+c ) .

(17)

This inequality will be proved in Appendix D. Hence, we obtain Theorem 1. Similarly, we have Epos Ezc EY+
1 2 I ([z ] ∈ C1 /C2 (Y+ , nh(|zc |/l + δ|zc | )), ρ(Λ pos,z ,E ([z ])) t)

C /C (Y )

n(R ? h(k× /l× + δk× ))
k

1 ≤ h max j n(R ? h(k/l× + δk ))
k

k

kc =0

Phg (kc |n, l, j )f (kk , k|n, l, δk ) +
k

kc =k+1

Phg (kc |n, l, j )f (kk , kc |n, l, δkc ) (18)

+ max
j kc =0

Phg (kc |n, l, j )f (kk , k |n, l, δk ) +

kc =k +1

Phg (kc |n, l, j )f (kk , kc |n, l, δk+c ) ,

This inequality will be proved in Appendix D. Hence, we obtain Theorem 2.

22

VII.

SECURITY AND PHASE ERROR

In this section, we treat the relation between Eve’s information and the phase error. This relation is one of essential parts for Theorem 3. The purpose of this section is proving the following lemmas[28]. Lemma 2 Let Λ be a generalized Pauli channel on the system (C2 )?n . Then, we have I (x ∈ Fn 2 , ΛE (|x x|)) ≤ ηn (1 ? PΛ,Z (0)). (19)

Since 1 ? PΛ,Z (0) can be regarded as the phase error, this lemma gives a relation between the phase error and Eve’s information. Proof: The Stinespring representation of Λ is given as ((C2 )?2n , U, |φ ): |φ := U :=
x,z ∈Fn 2 x,z ∈Fn 2

PΛ (x, z )|x, z Xx Zz ? |x, z x, z |.

Since U |x′ ? |φ = =
x∈Fn 2

x,z ∈Fn 2

PΛ (x, z )(?1)x ·z |x′ ? x ? |x, z PΛ,X (x)|x ,



|x′ ? x ? |φx,x′ ?

Eve’s state can be written as ΛE (|x′ x′ |) = where |φx,x′ :=
z ∈Fn 2

x∈Fn 2

PΛ,X (x)|φx,x′ φx,x′ | ? |x x|,


PΛ,Z |X (z |x)(?1)x ·z |z . Since x′ obeys the uniform distribution, I (x ∈ Fn 2 , ΛE (|x x|)) =
x∈Fn 2

PΛ,X (x)H (

1 2n

x′ ∈Fn 2

|φx,x′ φx,x′ |)

=
x∈Fn 2

PΛ,X (x)H (PΛ,Z |X (·|x)) ≤ H (PΛ,Z ).

Hence, using Lemma 3, we obtain (19). 23

Lemma 3 Let P = {P (i)} be a distribution on {0, . . . , d ? 1}. Then, H (P ) ≤ h(1 ? P (0)) + log(d ? 1)(1 ? P (0)). Proof: H (P ) = ? P (0) log P (0) ? (1 ? P (0)) log(1 ? P (0)) ? (1 ? P (0))
d?1 i=1

P (i) P (i) log (1 ? P (0)) (1 ? P (0))

≤h(1 ? P (0)) + log(d ? 1)(1 ? P (0)).

VIII.

SECURITY OF KNOWN CHANNEL

In this section, we treat the security when the channel is known, i.e., prove Theorem 3
n ⊥ using Lemmas 2 and 1. To prove it, for any code C ? Fn 2 and any elements [z ] ∈ F2 /C

and [x] ∈ Fn 2 /C , we de?ne

|x, z

C

:=

1 ′ (?1)z ·x |x + x′ . |C | x′ ∈C

(20)

Note that this de?nition does not depend on the choice of the coset representative elements z (x) of [z ] ([x]). When we choose Fn 2 as C , the above is the discrete Fourier transform. Then, we have the following lemma.
⊥ ⊥ Lemma 4 When two codes C1 and C2 satisfy C2 ? C1 , any elements x ∈ Fn 2 , [z1 ] ∈ C2 /C1 ,

⊥ and [z2 ] ∈ Fn 2 /C2 satisfy

|x, z1 + z2 = 1

C1

|C1 /C2 | [x1 ]∈C1 /C2

(?1)(z1 +z2 )·x1 |x + x1 , z2

C2 .

(21)

Note that the RHS does not depend of the choice of the coset representative elements x1 of [x1 ].

24

Proof: 1 (?1)(z1 +z2 )·x1 |x + x1 , z2 |C1 /C2 | [x1 ]∈C1 /C2 = · 1 1 |C1 /C2 | [x1 ]∈C1 /C2
x2 ∈C2 C2

| C2 |

(?1)(z1 +z2 )·x1 +z2 ·x2 |x + x1 + x2 .

Since (z1 + z2 ) · (x1 + x2 ) = (z1 + z2 ) · x1 + z2 · x2 , we obtain (21). Lemma 5 |x + x1 x + x1 | =
C1 ,

x1 ∈C1

⊥ [z1 ]∈Fn 2 /C1

|x, z1

C1 C1

x, z1 |.

(22)

Proof: From the de?nition of |x, z1
⊥ [z1 ]∈Fn 2 /C1

we have x, z1 | (?1)z1 ·(x +x ) |x + x′′ x + x′ |
′ ′′

|x, z1

C1 C1

= =

1 | C1 | 1 | C1 | 1 | C1 |

⊥ x′ ∈C1 x′′ ∈C1 [z1 ]∈Fn 2 /C1

⊥ x′ ∈C1 x′′ ∈C1 [z1 ]∈Fn 2 /C1

(?1)z1 ·(x +x +(x





′′ ?x′ ))

|x + x′ + x′′ ? x′ x + x′ |

= =

⊥ x′ ∈C1 y ∈C1 [z1 ]∈Fn 2 /C1

(?1)z1 ·y |x + x′ + y x + x′ |

x′ ∈C1

|x + x′ x + x′ |, ? ? 1 if y = 0 = ? 0 if y = 0.

because y ∈ C1 satis?es 1 | C1 | (?1)z1 ·y

⊥ [z1 ]∈Fn 2 /C1

Now, we de?ne the minimum error:
⊥ ⊥ P ([z1 ] ∈ C2 /C1 , Λ(|0, z1 + z2 C1 C1

0, z1 + z2 |))

:= min 1?
M
⊥ /C ⊥ [z1 ]∈C2 1

Tr M[z1 ] Λ(|0, z1 + z2 C1 C1 0, z1 + z2 |)) , ⊥ ⊥ | C2 /C1 | 25

where M is a POVM {M[z1 ] }[z1 ]∈C2 ⊥ /C ⊥ . Then, we have the following evaluation. 1 Lemma 6 I ([x1 ] ∈ C1 /C2 , ΛE ( ≤ηm?s 1 | C2 | 1 | C2 | x |x1 + x2 x1 + x2 |))

2 ∈C2

⊥ [z2 ]∈Fn 2 /C2

⊥ ⊥ · P (z1 ∈ C2 /C1 , Λ(|0, z1 + z2

C1 C1

0, z1 + z2 |)),

(23)

where m = dim C1 and s = dim C2 . Proof: Using Lemma 5 and the convexity of mutual information, we have I ([x1 ] ∈ C1 /C2 , ΛE ( 1 | C2 | x |x1 + x2 x1 + x2 |)) |x1 , z2
C2 C2

1 =I ([x1 ] ∈ C1 /C2 , ΛE ( | C2 | ≤ 1 | C2 |
⊥ [z2 ]∈Fn 2 /C2

2 ∈C2

⊥ [z2 ]∈Fn 2 /C2

x1 , z2 |)) x1 , z2 |)). (24)

I ([x1 ] ∈ C1 /C2 , ΛE (|x1 , z2

C2 C2

Applying Lemma 2, we have I (x1 ∈ C1 /C2 , (ΛE (|x1 , z2
C2 C2

x1 , z2 |))
C1 C1

⊥ ⊥ ≤ηm?s P (z1 ∈ C2 /C1 , Λ(|0, z1 + z2

0, z1 + z2 |)).

From (24), the concavity of ηm?s implies I ([x1 ] ∈ C1 /C2 , ΛE ( 1 ≤ | C2 | ≤ηm?s 1 | C2 | x
2 ∈C2

|x1 + x2 x1 + x2 |))
C1 C1

⊥ [z2 ]∈Fn 2 /C2

⊥ ⊥ ηm?s P (z1 ∈ C2 /C1 , Λ(|0, z1 + z2 ⊥ ⊥ P (z1 ∈ C2 /C1 , Λ(|0, z1 + z2

0, z1 + z2 |)) 0, z1 + z2 |)).

1 | C2 |

C1 C1

⊥ [z2 ]∈Fn 2 /C2

Since Λ is a generalized Pauli channel, any coset [x0 ] ∈ Fn 2 /C1 satis?es Λ(|x0 , z1 + z2
C1 C1

x0 , z1 + z2 |)) = Xx0 Λ(|0, z1 + z2

C1 C1

0, z1 + z2 |))(Xx0 )? . Hence,
C1 C1 C1 C1

⊥ ⊥ P ([z1 ] ∈ C2 /C1 , Λ(|0, z1 + z2

0, z1 + z2 |)) x0 , z1 + z2 |)).

⊥ ⊥ =P ([z1 ] ∈ C2 /C1 , Λ(|x0 , z1 + z2

26

Thus,
⊥ ⊥ P (z1 ∈ C2 /C1 , Λ(|0, z1 + z2 C1 C1

=

| C1 | 2n

0, z1 + z2 |))

[x0 ]∈Fn 2 /C1 C1 C1

⊥ ⊥ P (z1 ∈ C2 /C1 , Λ(|x0 , z1 + z2 ⊥ ⊥ ≤P z1 ∈ C2 /C1 ,

x0 , z1 + z2 |))

| C1 | 2n

[x0 ]∈Fn 2 /C1

Λ(|x0 , z1 + z2

C1 C1

x0 , z1 + z2 |)

⊥ ⊥ =P z1 ∈ C2 /C1 ,

Λ(

| C1 | 2n

⊥ z0 ∈C1

|z0 + z1 + z2

n Fn 2 F2

z0 + z1 + z2 |) .

(25)

⊥ G(C1 )C2 (Y, s) to C2 (Y, s). Then, the dual code C2 (Y, s)⊥ satis?es C1 ? C2 (Y, s)⊥ and

Now, we focus on the step (ix) and the subcode G(C1 )C2 (Y, s) ? C1 , and abbreviate

⊥ and C1 , respectively. Then, n ? (l + t) in Lemma 1 is given by s. Since the generalized

the condition of C2 (X ) in Lemma 1 when t, l and C1 in Lemma 1 is given by n ? v , v ? s,

Pauli channel can be regarded as the additive channel, we can apply Lemma 1. Hence, EY 1 |C2 (Y, s)| | C1 | 2n

⊥ [z2 ]∈Fn 2 /C2 (Y,s)

⊥ P z1 ∈ C2 (Y, s)⊥ /C1 ,

ΛE (
n

⊥ z0 ∈C1

|z0 + z1 + z2

n Fn 2 F2

z0 + z1 + z2 |) (26)



k =0

?Wt (k )g (2?s|n, k ). P

27

From (25), (26), and (23), the convexity of ηm?s yields that EY 1 | C2 |

⊥ [z2 ]∈Fn 2 /C2

I ([x1 ] ∈ C1 /C2 , ΛE (|x1 , z2 ≤ηm?s EY 1 | C2 |
⊥ [z2 ]∈Fn 2 /C2

C2 C2

x1 , z2 |))

⊥ ⊥ P z1 ∈ C2 /C1 , Λ(|0, z1 + z2

C1 C1

0, z1 + z2 |

≤ηm?s

?n/2? k =0

?Wt (k )g (2?s|n, k ) . P

Therefore, from (24), we obtain Theorem 3.

IX.

OPTIMAL ATTACK

In this section, we prove that there exists a collective attack attaining the the exponential rate (4) under a condition. Indeed, it is not so easy to evaluate max I (Z, ZE ). Hence, we treat IH (Z, ZE ) instead of I (Z, ZE ). Lemma 7 Assume that the sequence of codes C1,n,k+ satis?es
k ≤(p+?(p))n

max

⊥ Pe,Wk,n (C1 ,n ) → 0

(27)

where the channel Wk,n is de?ned on Fn 2 as PWk,n (j ) = δk,j . Then, we have lim ?r log Ek× |pos× ,Y+ ,pos+ ,k+ ,Y× max IH (Z, ZE ) E n (28)

≤ min h(p + r?(p)) ? (1 ? r )h(p) ? rh(p + ?(p)),
p∈[p,p]

where the maximum is taken concerning Eve’s operation E . Note that, the above inequality holds for any ?xed variable Y+ . Hence, if ?(p) is su?ciently small and the sequence of codes C1,n satis?es the condition (27), we have lim ?r log Epos× ,k× ,Y+ |pos+ ,k+ ,Y× max IH (Z, ZE ) n (29)

=h(p + r?(p)) ? (1 ? r )h(p) ? rh(p + ?(p)). 28

This indicates that the method of randomly choosing code C2 is optimal in the sense of large deviation. In this lemma, we assume the condition (27). Indeed, we need some conditions in Lemma 7. For example, consider the code C1 that consists of the elements x whose the ?rst n ? m components is zero. In this case, the following proof is not valid. Indeed, when the limit limn→∞
1 n

log |C1,n | is greater than h(p + ?(p)) and we choose C1,n randomly, the condition

(27) holds. Hence, the condition (27) is not so unnatural. However, a more natural condition is needed. As is shown later, the exponential rate minp∈[p,p] h(p + r?(p)) ? (1 ? r )h(p) ? rh(p + ?(p)) can be attained by a collective attack, in which Eve’s is allowed only individual unitary operations to quantum states sent by Alice and any global generalized measurement on the Eve’s local states. Hence, the exponential rate of Eve’s information cannot be improved by any collective attack, in which Eve’s is allowed to use any unitary operation to all quantum states sent by Alice. Now, we construct Eve’s strategy attaining the bound minp∈[p,p] h(p + r?(p)) ? (1 ? r )h(p) ? rh(p + ?(p)) and prove (28). Choose p0 := argminp∈[p,p] h(p + r?(p)) ? (1 ? r )h(p) ? rh(p + ?(p)). Eve performs a unitary action Up0 +r?(p0 ) Up |x ? |0
E

:=



p| x ? | 0

E

+ (?1)x

1 ? p| x ? | 1

E

for a every qubit, where |x E is Eve’s state. ?k : We de?ne the unitary U ? n |x ? |0 U k We can easily show that H Λk E,k
x∈C1,n E

:=

1
n k y ∈Fn 2 : | x | =k

(?1)x·y |x ? |y

E.

|x x| |y + x y + x| for y ∈ Fn 2.

=H Λ k E,k
x∈C1,n

29

Hence, applying Lemma 6 to the case of C1 = Fn 2 , C2 = C1,n , we have log n ? H Λn E,k k |x x| |x x| |x x|

x∈C1,n

=H Λ n E,k
x∈Fn 2

? H Λn E,k

x∈C1,n

⊥ ⊥ ≤h(Pe,Wk,n (C1 ,n )) + log |C1,n |Pe,Wk,n (C1,n ),

where ?n Λn E,k (ρ) := TrB Uk (ρ ? |0
E E

? n )? . 0|)(U k

Now, we evaluate Eve’s information. In this case, the subcode C2,n,k× depends on the outcome k× . Taking the pinching map: ρ → space spanned by {|x }|x|=k ), we have
k

Pn,k ρPn,k (Pn,k is the projection to the

n H Ek× Λ? E

x∈C1,n

|x x| |x x|

?

n H Λ? E [x]2 ∈C1,n /C2,n,k× y ∈C2,n,k×

|x + y x + y | |x + y x + y | ,

≥H Ek× ,k Λn E,k

x∈C1,n

?

H Λn E,k
[x]2 ∈C1,n /C2,n,k× n k y ∈C2,n,k×

? (k ) := where k is the random variable with distribution P When k = n(p0 + ?(p0 ) + ?), k× = p0 , we have 1 H Λn E,k n ≥ 1 n 1 = n log |x x| ? 1 n

(p0 + r?(p0 ))k (1 ? p0 ? r?(p0 ))n?k .

H Λn E,k
[x]2 ∈C1,n /C2,n,k× y ∈C2,n,k×

x∈C1,n

|x + y x + y |

n ⊥ ⊥ ? h(Pe,Wk,n (C1 ,n )) ? log |C1,n |Pe,Wk,n (C1,n ) ? log |C2,n,k× | k k× n k× ⊥ ⊥ ? nh( log + ?( )) ? h(Pe,Wk,n (C1 ,n )) ? log |C1,n |Pe,Wk,n (C1,n ) k n n

→h(p0 + ?(p0 ) + ?) ? h(p0 + ?(p0 )) as n → ∞.

30

Hence, Eve’s information can be bounded as ? ≥
?n Ek× ?H (ΛE ( x∈C1,n

|x x|))) ?

n H (Λ? E ( y ∈C2,n,k×

[x]2 ∈C1,n /C2,n,k×

n (p0 + r?(p0 ))n(p0 +?(p0 )+?) (1 ? p0 ? r?(p0 ))n?n(p0+?(p0 )+?) n(p0 + ?(p0 ) + ?) l (p0 + r?(p0 ))lp0 (1 ? p0 ? r?(p0 ))l(1?p0 ) (n(h(p0 + ?(p0 ) + ?) ? h(p0 + ?(p0 ))) + o(n)) · lp0 n(h(p0 + ?(p0 ) + ?) ? h(p0 + ?(p0 ))) + o(n) ?nd(p0 +?(p0 )+? p0 +r?(p0 ))?ld(p0 p0 +r?(p0)) ≥ 2 . (n + 1)2

|x + y x + y |))?

?

Thus, we obtain lim ?r log Ek× |pos× ,Y+ ,pos+ ,k+ ,Y× max IH Z + , ZE n

≤h(p0 + r?(p0 )) ? (1 ? r )h(p0 ) ? rh(p0 + ?(p0 ) + ?). Taking the limit ? → 0, we obtain (28).
X. CONCLUSION

In this paper, we obtained a practical evaluation of security of quantum key distribution. This bound improves existing bounds. In order to guarantee the security of implemented QKD system, we need a tighter bound in the ?nite-coding length. Hence, our bound is useful for guaranteeing the security of quantum key distribution with perfect single photon source. However, for a precise evaluation, we have to treat hypergeometric distributions, because our bound contains hypergeometric distributions. Hence, it is needed to calculate these bounds by numerical analysis based on several calculations of hypergeometric distributions. We also derived the exponential rate of our bound as (4), and proved its optimality with in the sense of Holevo information with a class of one-way communication when Cp is less than the critical case. However, our condition for our code is not su?ciently natural. Hence, it is required to prove this optimality under a more natural condition. One candidate of a more natural condition is max
⊥ Pe,Wk,n (C1 ,n ) → 0.

? ?1 (1?h(p+?(p)))n k ≤h

(30)

Hence, it is a future problem to show the optimality under the above condition. 31

Further, we assumed that perfect single photon source. One idea for the weak coherent case is the decoy method [23], which is based on the observation of the security with imperfect devices[24]. However, any existing paper [25, 26, 27] of the decoy method does not discuss the degree of Eve’s information in the framework of ?nite coding-length, precisely. Hence, it is required to extend our result to the weak coherent case with the decoy method.

Acknowledgments

The author would like to thank Professor Hiroshi Imai of the ERATO-SORST, QCI project for support. He is grateful to Professor Hiroshi Imai, Dr. Akihisa Tomita, Professor Keiji Matsumoto, and Mr. Jun Hasewaga for useful discussions. He is also bene?ted by referee for pointing out several mistakes in the ?rst version.

APPENDIX A: DERIVATION OF (3)

?k ) ? h( k + δk ) ≥ 0}. In the case of j = pm, and de?ne the number kp (m) := max{k |h( pm n l ? (δ, n, l, k, k) goes to 0. Hence, we focus on the second term of this case, the ?rst term of P ? (δ, n, l, k, k), which is divided as P

Now, we prove (3). In the following, we denote n + l by m and ?x p ∈ [p, p]. We treat

?2 (δ, n, l, k, k ) P
k

:=
k =0

Phg (k |n, l, j )f (j ? k, k|n, l, δk× )
k

+
k =k+1 kp (m)

Phg (k |n, l, j )f (j ? k, k |n, l, δk× )

=
k =0

Phg (k |n, l, j )
k

+
k =kp (m)+1

Phg (k |n, l, j )f (j ? k, k |n, l, δk× ).
nl δ . m k ? ?

k/l Using the relation δk = √ m √ √ and the continuity of Cp , we have kp (m) = (1 ? r )pm ? r (1 ? r )? ?(p) m + o( m). The

kp (m) Since h( pm?n ) = h( kp (lm) + δk ), we have kp (m) = pl ? lj n+l

average of k is

= (1 ? r )pm and the variance of k is 32

jln(n+l?j ) (n+l)2 (n+l?1)

=

r (1?r )p(1?p)m . 1 1? m

Hence,

kp (m)?(1?r )pm
r (1?r )p(1?p)m 1 1? m

√ r (1?r ) √ →? ? ?(p). Thus, we have
p(1?p) kp (m)

k =0

Phg (k |n, l, j ) = Φ ?

p(1 ? p)

r (1 ? r )

? ?(p) .

When k ≥ kp (m), we can approximate the di?erence as h( Hence,
k

k l+n j?k ) ? h( + δk ) ? (k ? kp (m)). = ?h′ (p) n l ln

k =kp (m)+1

Phg (k |n, l, j )f (j ? k, k |n, l, δk× )

? =

1
p(1?p)m 2π r(1?r1)? 1 m k
(x?(1?r )pm)2 r (1?r )p(1?p)m 1 1? m

· 1 ? = 2π

e
kp (m) +∞

?

2

2?nh (p)



l+n (x?kp (m)) ln

dx

√ r (1?r ) ?√ ? ?(p)
p(1?p)

e

?x 2

2

2

√ ? mh′ (p)



rp(1?p) r (1?r ) √ ? ?(p)) (y + √ 1?r p(1?p)



·

r (1 ? r )p(1 ? p)mdy

→0 as m → ∞, where y = √ x?(1?r)pm
r (1?r )p(1?p)m

.
j m k is strictly smaller than p. The value ?h( j ? )+h( k +δk ) n l

Next, we consider the case when

k ) + h( k + δk ) is smaller than this value if k ≥ k . Hence, is strictly positive and ?h( j ? n l ?2 (δ, n, l, k, k ) goes to 0. P

Finally, we consider the case when

j m

is strictly greater than p. In this case, as is mentioned

in B, the probability that k is greater than k exponentially goes to 0. Hence, in this case ? (δ, n, l, k, k) goes to 0. Therefore, we obtain (3). P

33

APPENDIX B: DERIVATION OF (4)

From (9), we have
j ?k j k 1 2lh( l )+nh( n )?(n+l)h( n+l ) ≤ Phg (k |n, l, j ) (n + 1)(l + 1)

= Hence,

l k

n j ?k n+l j

≤ (n + l + 1)2lh( l )+nh(

k

j ?k )?(n+l)h( nj ) n +l

.

k

max
j k =0 k

Phg (k |n, l, j )f (j ? k, k |n, l, δk× ) Phg (k |n, l, j )f (j ? k, k |n, l, δk× )

+
k =k+1

≤k (n + l + 1) · 2maxj,k lh( l )+nh( Further,
k
k

j ?k k )?(n+l)h( nj )?n[h( k +δk )?h( j ? )]+ n +l l n

.

max
j k =0

Phg (k |n, l, j )f (j ? k, k |n, l, δk× ) k · n(R ? h( + δk× )) l

k

+
k =k+1

Phg (k |n, l, j )f (j ? k, k |n, l, δk× ) k · n(R ? h( + δk× )) , l

≤n(R ? h(p + ?(p)))k (n + l + 1) · 2maxj,k lh( l )+nh( Thus, substituting p = k ,r = l
n , ?(p) n+l
k

j ?k k )?(n+l)h( nj )?n[h( k +δk )?h( j ? )]+ n +l l n

.

= δk , ?′ =

k l

? δk ?

j ?k , n

we obtain (5). Since

k j ?k j ?r max lh( ) + nh( ) ? (n + l)h( ) n j,k l n n+l k j?k ? n[h( + δk ) ? h( )]+ l n ≤E (?, r, p, p), we obtain the part ≤ in (4). 34 (B1)

Conversely,
k

max
j k =0

Phg (k |n, l, j )f (j ? k, k |n, l, δk× )
k

+
k =k+1

Phg (k |n, l, j )f (j ? k, k |n, l, δk× ) .



2maxj,k lh( l )+nh(

k

j ?k j k )?(n+l)h( n+ )?n[h( k +δk )?h( j ? )]+ n l l n

(n + 1)(l + 1)

Since the equality in (B1) holds in the limit n → ∞, we obtain the part ≥ in (4).
APPENDIX C: PROOF OF (15) AND (16)

When Alice sends the classical information x + X+ (x = G(C1 )Z ), the probability that ? + is Bob obtains the local signal xb := x + X+ ? X Tr 1 2n+l
n ′ l x′ k ∈F2 zc ∈F2

′ Λpos (|x′k x′k | ? |zc
l x′ c ∈F2

n Fn 2 F2

′ ′ zc |)|x′k + x ? xb x′k + x ? xb | ? |zc ?z
n Fn 2 F2

n Fn 2 F2

′ zc ? z |)

1 Tr 2 l

Tr = = =

1 2n+l
n ′ l x′′ k ∈F2 zc ∈F2

′ Λpos (ρmix,n ? |zc

′ | )I ? | z ′ ? z zc c

n Fn 2 F2

′ ? z |) zc
n Fn 2 F2

′′ ′ Λpos (|x′′ k ? xb xk ? xb | ? |zc
l x′ c ∈F2

n Fn 2 F2

′ ′′ ′ zc |)|x′′ k ? xb xk ? xb | ? |zc ? z ′ | )I ? | z ′ ? z zc c
n Fn 2 F2

′ zc ? z |)

1 Tr 2 l

Tr 2n1+l
1 Tr 22(n +l)

n x′′ k ∈F2

pos n 0|)| ? xb +l (Λ ) (| ? xb ?xb | ? |0 Fn x′′ ,z ′′ ∈Fn 2 F2 2 1 pos )(x′′ ,z ′′ ) (ρ n 0 | )I ? | Tr 22(n +l (Λ mix,n ? |0 Fn +l) x′′ ,z ′′ ∈Fn 2 F2 2 n 0|)| ? xb n ?z | Tr(Λt )pos (| ? x ?x| ? |0 Fn ?xb | ? | ? z Fn 2 F2 2 F2 = n 0|)I ? | ? z Fn Fn ?z |) Tr(Λt )pos (ρmix,n ? |0 Fn 2 F2 2 2

′ pos (x′′ n ) k 0,0zc ) (| ? xb ?xb | ? |0 Fn ′ ∈Fl (Λ zc 2 F2 2 1 pos (ρ n 0 | )I ? Tr 2 l Λ mix,n ? |0 Fn l x′ 2 F2 c ∈F2

′ Λpos (ρmix,n ? |zc

n Fn 2 F2

′ ? z |) zc
n Fn 2 F2

(x′′ ,z ′′ )

|?z

0|)| ? xb ?xb | ? | ? z
n Fn 2 F2

?z |)

?z |)

?z

?xb | ? | ? z
n Fn 2 F2

n Fn 2 F2

?z |)

?z |)

(C1)

= Tr(Λt )pos,z (| ? x ?x|)| ? xb ?xb |, where (Λt )pos,zc (ρ) :=
xk ,zk ∈Fn 2

P(Λt )pos ,k|Z,c(xk , zk |zc )Xxk Zzk ρ(Xxk Zzk )? .

In the derivation of (C1), we use (13). 35

Eve’s state can be regarded as ((Λt )pos,z )E (| ? x ?x|). Hence, applying Theorem 3, we obtain (15) and (16).

In this case, we can regard that Bob measures the state (Λt )pos,z (| ? x ?x|). Hence,

36

APPENDIX D: PROOF OF (17) AND (18)
1 2 as First, we evaluate Epos Ezc EY+ I ([z ] ∈ C1 /C2 (Y+ , nh(|zc |/l + δ|zc | )), ρ(Λ pos,z ,E ([z ])) t) 1 2 Epos Ezc EY+ I ([z ] ∈ C1 /C2 (Y+ , nh(|zc |/l + δ|zc | )), ρ(Λ pos,z ,E ([z ])) t)

C /C (Y )

C /C (Y )

n

≤Epos +

P(Λt )pos ,Z,c(zc )h
|zc |<k kk =0

?(Λt )pos ,Z (kk |zc )f (kk , k |n, l, δk ) P ?(Λt )pos ,Z (kk |zc )f (kk , |zc | |n, l, δ|zc | ) P
n

n

P(Λt )pos ,Z,c(zc )h
k≤|zc |≤k kk =0

+ Epos
|zc |<k

P(Λt )pos ,Z,c(zc )n(R ? h(k/l + δk ))

kk =0

?(Λt )pos ,Z (kk |zc )f (kk , k|n, l, δk ) P
n

+
k≤|zc |≤k

P(Λt )pos ,Z,c(zc )n(R ? h(|zc |/l + δ|zc | ))

kk =0

?(Λt )pos ,Z (kk |zc )f (kk , |zc | |n, l, δ|zc | ) P (D1)

n

≤h Epos +

P(Λt )pos ,Z,c (zc )
|zc |<k kk =0 n

?(Λt )pos ,Z (kk |zc )f (kk , k |n, l, δk ) P

P(Λt )pos ,Z,c(zc )
k≤|zc |≤k kk =0

?(Λt )pos ,Z (kk |zc )f (kk , |zc | |n, l, δ|zc | ) P
n

+ Epos
|zc |<k

P(Λt )pos ,Z,c(zc )n(R ? h(k/l + δk ))

kk =0

?(Λt )pos ,Z (kk |zc )f (kk , k|n, l, δk ) P
n

+
k≤|zc |≤k

P(Λt )pos ,Z,c(zc )n(R ? h(|zc |/l + δ|zc | ))

kk =0

?(Λt )pos ,Z (kk |zc )f (kk , |zc | |n, l, δk ) P (D2)

n

k

=h
kk =0 kc =0 n

?(Λt )pos ,Z,k,c(kk , kc )f (kk , k |n, l, δk ) Epos P
k

+
kk =0 kc =k+1 n k

?(Λt )pos ,Z,k,c(kk , kc )f (kk , kc |n, l, δkc ) Epos P

+
kk =0 kc =0 n

?(Λt )pos ,Z,k,c(kk , kc )n(R ? h(k/l + δk ))f (kk , k |n, l, δk ) Epos P
k

+
kk =0 kc =k+1

?(Λt )pos ,Z,k,c(kk , kc )n(R ? h(kc /l + δkc ))f (kk , kc |n, l, δk+c ) Epos P

(D3)

37

Further, RHS of (D3) is evaluated as (RHS of (D3))
n k

=h
kk =0 kc =0 n

?(Λt ),Z (kk + kc )Phg (kc |n, l, kk + kc )f (kk , k |n, l, δk ) P
k

+
kk =0 kc =k +1 n k

?(Λt ),Z (kk + kc )Phg (kc |n, l, kk + kc )f (kk , kc |n, l, δkc ) P

+
kk =0 kc =0 n

?(Λt ),Z (kk + kc )Phg (kc |n, l, kk + kc )n(R ? h(k/l + δk ))f (kk , k |n, l, δk ) P
k

+
kk =0 kc =k +1

?(Λt ),Z (kk + kc )Phg (kc |n, l, kk + kc )n(R ? h(kc /l + δkc ))f (kk , kc |n, l, δk+c ) P (D4)

k

k

≤h max
j

kc =0 k

Phg (kc |n, l, j )f (kk , k|n, l, δk ) +

kc =k+1

Phg (kc |n, l, j )f (kk , kc |n, l, δkc )

+ max
j kc =0

Phg (kc |n, l, j )n(R ? h(k/l + δk ))f (kk , k |n, l, δk )
k

+
kc =k +1

Phg (kc |n, l, j )n(R ? h(kc /l + δkc ))f (kk , kc |n, l, δk+c ) .

(D5)

In the above relations, (D1) follows from (15) and (16), and (D2) follows from the con? , (D4) follows from (14), (D5) follows by replacing kk + kc by j . Hence, we obtain vexity of h (17).

38

Similarly, we have Epos Ezc EY+
1 2 I ([z ] ∈ C1 /C2 (Y+ , nh(|zc |/l + δ|zc | )), ρ(Λ pos,z ,E ([z ])) t)

C /C (Y )

1 ≤ Epos n(R ? h(k/l× + δk )) +
k ≤|zc |≤k

n(R ? h(k× /l× + δk× )) P(Λt )pos ,Z,c (zc )h

n

|zc |<k n

kk =0

?(Λt )pos ,Z (kk |zc )f (kk , k |n, l, δk ) P

P(Λt )pos ,Z,c (zc )h
kk =0 n

?(Λt )pos ,Z (kk |zc )f (kk , |zc | |n, l, δ|zc | ) P

+ Epos
|zc |<k

P(Λt )pos ,Z,c (zc )
kk =0 n

?(Λt )pos ,Z (kk |zc )f (kk , k |n, l, δk ) P

+
k ≤|zc |≤k

P(Λt )pos ,Z,c (zc )
kk =0

?(Λt )pos ,Z (kk |zc )f (kk , |zc | |n, l, δ|zc | ) P
k k

1 h max ≤ j n(R ? h(k/l× + δk ))
k

kc =0

Phg (kc |n, l, j )f (kk , k|n, l, δk ) +
k

kc =k+1

Phg (kc |n, l, j )f (kk , kc |n, l, δkc )

+ max
j kc =0

Phg (kc |n, l, j )f (kk , k |n, l, δk ) +

kc =k +1

Phg (kc |n, l, j )f (kk , kc |n, l, δk+c ) .

Hence, we obtain (18).

[1] C.H. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing,” Proc. IEEE Int. Conf. on Computers, Systems, and Signal Processing (Bangalore, India, IEEE, New York, 1984) 175. [2] D. Mayers, “Quantum key distribution and string oblivious transfer in noisy channels,” In Advances in Cryptology – Proc. Crypto’96, Vol. 1109 of Lecture Notes in Computer Science (Ed. N. Koblitz, Springer-Verlag, New York, 1996) 343; J. Assoc. Comput. Mach. 48 (2001) 351. [3] H. Inamori, N. L¨ utkenhaus, and D. Mayers “Unconditional Security of Practical Quantum Key Distribution,” quant-ph/0107017. [4] P. W. Shor and J. Preskill, “Simple Proof of Security of the BB84 Quantum Key Distribution Protocol,” Phys. Rev. Lett. 85, 441 (2000). [5] A. R. Calderbank and P. W. Shor, “Good quantum error correcting codes exist,” Phys. Rev. A, 54, 1098 – 1105 (1996).

39

[6] M. Steane, “Multiple particle interference and quantum error correction,” Proc. Roy. Soc. Lond. A, 452, 2551 – 2577 (1996). [7] M. Hamada, “Reliability of Calderbank-Shor-Steane Codes and Security of Quantum Key Distribution,” J. Phys. A: Math. Gen. 37, (2004). [8] M. Christandl, R. Renner, and A. Ekert, “A Generic Security Proof for Quantum Key Distribution”, quant-ph/0402131v2. [9] R. Renner, N. Gisin and B. Kraus, “Information-theoretic security proof for quantum-keydistribution protocols,” Phys. Rev. A72 (2005) 012332, quant-ph/0502064. [10] M. Koashi, “Simple security proof of quantum key distribution via uncertainty principle,” quant-ph/0505108. [11] S. Watanabe, R. Matsumoto, T. Uyematsu, “Noise Tolerance of the BB84 Protocol with Random Privacy Ampli?cation,” quant-ph/0412070. [12] D. Stucki, N. Gisin, O. Guinnard, G. Ribordy, and H. Zbinden, “Quantum key distribution over 67 km with a plug & play system,” New J. Phys., 4, 41 (2002). [13] T. Kimura, Y. Nambu, T. Hatanaka, A. Tomita, H. Kosaka, and K. Nakamura, Jpn. J. Appl. Phys., 43, L1217 (2004). [14] C. Gobby, Z. L. Yuan and A. J. Shields, Appl. Phys. Lett., 84, 3762 (2004). [15] A. Tanaka, W. Maeda, A. Tajima, and S. Takahashi, Proceedings of the 18th Annual Meeting of the IEEE Lasers and Electro-Optics Society, Sidney, Australia, 23–27 October 2005, p. 557 [16] Z. L. Yuan and A. J. Shields, “Continuous operation of a one-way quantum key distribution system over installed telecom ?ber,” Optics Express, 13, 660 (2005). [17] M. Koashi and J. Preskill, Phys. Rev. Lett., 90, 057902 (2003). [18] Y. Watanabe, W. Matsumoto, and Hideki Imai, “Information reconciliation in quantum key distribution using low-density parity-check codes,” Proc. of International Symposium on Information Theory and its Applications, ISITA2004, Parma, Italy, October, 2004, p. 1265 – 1269. [19] Csisz? ar and J. K¨ orner, Information Theory: Coding Theorems for Discrete Memoryless Systems. (NY: Academic, 1981). [20] H. Weyl, Gruppentheorie und Quantenmechanik, (Leipzig: Verlag von S. Hirzel, 1928). English translation, The Theory of Groups and Quantum Mechanics, of the second (1931) ed. was reprinted by Dover, 1950.

40

[21] C. H. Bennett, D. P. DiVincenzo, J. A. Smolin, and W. K. Wootters, “Mixed-state entanglement and quantum error correction,” Phys. Rev. A, 54, 3824 – 3851 (1996). [22] M. Hamada, “Teleportation and entanglement distillation in the presence of correlation among bipartite mixed states,” Phys. Rev. A, 68, 012301 (2003). [23] W-Y. Hwang, “Quantum Key Distribution with High Loss: Toward Global Secure Communication,” Phys. Rev. Lett., 91, 057901 (2003). [24] D. Gottesman, H.-K. Lo, N. L¨ utkenhaus, and J. Preskill, “Security of quantum key distribution with imperfect devices,” Quant. Inf. Comput., 5, 325 – 360 (2004). [25] H.-K. Lo, “Quantum Key Distribution with Vacua or Dim Pulses as Decoy States,” Proc. 2004 IEEE Int. Symp. on Inf. Theor. (June 27-July 2, Chicago, 2004) 17. [26] H. K. Lo, X.-F. Ma, and K. Chen, “Decoy State Quantum Key Distribution,” Phys. Rev. Lett., 94, 230504, (2005). [27] X.-B. Wang, “Beating the PNS attack in practical quantum cryptography,” Phys. Rev. Lett., 94, 230503 (2005). [28] A similar lemma has been obtained independently by T. Miyadera and Hideki Imai “On Information-Disturbance Trade-o? Theorem,” Proceedings of ERATO conference on Quantum Information Science 2005, August 26-30, 2005, Tokyo, Japan, 165 - 166.

41


赞助商链接

更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图