January 4, 2007 16:49 WSPC/187-IJQI

00231

International Journal of Quantum Information
Vol. 4, No. 6 (2006) 935–946
c World Scientific Publishing Company


NOISE TOLERANCE OF THE BB84 PROTOCOL WITHRANDOM PRIVACY AMPLIFICATION∗SHUN WATANABE† , RYUTAROH MATSUMOTO‡ and TOMOHIKO UYEMATSU§
Department of Communications and Integrated Systems,
Tokyo Institute of Technology,
Tokyo 152-8552, Japan†shun-wata@it.ss.titech.ac.jp‡ryutaroh@it.ss.titech.ac.jp§uyematsu@ieee.org
Received 2 February 2006
This paper shows that the random privacy amplification is secure with a higher key rate
than Mayers’ evaluation at the same error rate in the BB84 protocol with one-way or
two-way classical communications. There exists only Mayers’ evaluation on the secure
key rate with random privacy amplification that is applicable to the BB84 protocol with
two-way classical communications. Our result improves the secure key rate of the random
privacy amplification in the BB84 protocol with two-way classical communications.
Keywords: BB84 protocol; CSS code; quantum key distribution; random privacy amplification; two-way protocol.

1. Introduction
The BB84 protocol is the ﬁrst quantum key distribution (QKD) protocol, which
was proposed by Bennett and Brassard in 1984.1 Unlike conventional cryptographies that rely on the conjectured diﬃculty of computing certain functions, thesecurity of QKD is guaranteed by the postulate of quantum mechanics. In the
BB84 protocol, the participants (Alice and Bob) agree on a secret key about which
any eavesdropper (Eve) can obtain little information. The security proof of thisprotocol against arbitrary eavesdropping strategies was ﬁrst proved by Mayers,21
later another proof was shown by Biham et al.,3 and a simple proof was later shownby Shor and Preskill.23 After them, many security analyses are studied.12,16,18,24
The proof method of Ref. 23 is also extended to the BB84 protocol with two-way
classical communication13 . It is known that the BB84 protocol with two-way classical communications can tolerate higher error rate than the BB84 protocol with
one-way classical communication. The tolerable error rates are 18.9% in Ref. 13
and 20% in Ref. 5.
∗ Part of this paper was presented in the 2005 IEEE International Symposium on Information
Theory, Adelaide Convention Centre, Adelaide, Australia, 4–9 September, 2005.

935

January 4, 2007 16:49 WSPC/187-IJQI

936

00231

S. Watanabe, R. Matsumoto & T. Uyematsu

Roughly speaking, the BB84 protocol is divided into a quantum part and a classical part. In the quantum part, the transmitter Alice sends qubits to the receiver
Bob to share a raw key (random binary sequence), which may be partially known tothe eavesdropper, Eve. In the classical part, ﬁrst Alice and Bob optionally perform
two-way preprocessing. Then, the receiver Bob corrects his raw key so that his ﬁnal
key will be identical to Alice’s ﬁnal key. Finally, Alice and Bob perform the privacy
ampliﬁcation to extract a shorter but secret key from the raw key, about which Eve
knows little information.
For the key distribution protocol to be practical, we have to perform the error
correction and the privacy ampliﬁcation eﬃciently. Based on the security proof ofthe BB84 protocol in Refs. 21 and 23, we use a pair of linear codes C1 and C2 withC2 ⊂ C1 . The linear code C1 is used for error correction, and the linear code C2
is used for the privacy ampliﬁcation. In order that the BB84 protocol is secure,the decoding error probability of C1 and C2⊥ regarded as a Calderbank–Shor–Stean(CSS) code have to be small. As a practical requirement, the linear code C1 haveto be eﬃciently decodeable, while the linear code C2 need not to be eﬃciently
decodeable. It is diﬃcult to ﬁnd a pair of linear codes C1 and C2 that satisfy theabove conditions. Mayers showed that if one arbitrarily ﬁxes C1 and chooses C2
with rate h(2p) at random from subcodes of C1 , the minimum Hamming weight of
C2⊥ \C1⊥ is greater than pn with high probability (Lemma 4 in Ref. 21), where p
is estimated error rate and h(·) is the binary entropy function. Consequently, thedecoding error probability of C2⊥ regarded as a CSS code is small. When we use alinear code C1 with rate close to 1 − h(p), Mayers’ evaluation guarantees the secure
key rate 1 − h(p) − h(2p), which is lower than the achievable rate 1 − 2h(p) given
in Ref. 23. In this paper, we call the random privacy ampliﬁcation as the method
such that one chooses C2 at random from subcodes of a ﬁxed code C1 and performs
the privacy ampliﬁcation by C2 .
By evaluating directly the decoding error probability of C2⊥ instead of the minimum Hamming weight, we can decrease the rate of C2 while maintaining thesecurity of the protocol. This paper shows that when one chooses C2 with rate h(p)at random from subcodes of C1 , the decoding error probability of C2⊥ regarded asa CSS code is exponentially small with high probability.
It should be noted that the random privacy ampliﬁcation (without two-way
preprocessing) is known to be secure with rate h(p) according to Refs. 8 and 22.
However, the proof method in Refs. 8 and 22 relies on the result in Ref. 17, which
is only applicable to the QKD with one-way classical communication (Footnote 6
in Ref. 22), and it is not known how to extend that method to the QKD with
two-way classical communications. On the other hand, the proof method of Ref. 23
is extended to the security proof of QKD with two-way classical communications,13and our result is valid for the BB84 protocol with two-way classical communications.
It should be also noted that our result is diﬀerent from previously known results
based on security proof method in Ref. 23. In Lemma 4 of Ref. 21, it is proved that
if we ﬁx C1 of rate 1 − h(p) and choose its subcode C2 of rate h(2p) at random, theJanuary 4, 2007 16:49 WSPC/187-IJQI

00231

Noise Tolerance of the BB84 Protocol with Random Privacy Amplification

937

BB84 protocol is secure. In Ref. 23, they also cite Lemma 4 of Ref. 21 to show that
we can securely choose a random subcode C2 of an eﬃciently decodeable code C1 .
However, it is not clariﬁed in Ref. 23 that we can securely choose C2 at randomwith rate h(p). Other previous papers12,13,16,18,24 are based on the result in Ref. 23.
We also stress that the random hashing method cannot be directly applied to thesecurity proof of the BB84 protocol with random privacy ampliﬁcation as used inRef. 19, because a ﬁxed C1 and the condition C2 ⊂ C1 decrease the randomnessof hashing. Application of the random hashing to a security proof of the random
privacy ampliﬁcation requires a careful argument similar to Sec. 3 of this paper.
Although an idea to decouple the error correction and the privacy ampliﬁcation in
the random hashing was proposed in Ref. 25, a rigorous proof was not shown.
This paper is organized as follows. In Sec. 2, we review the Calderbank–Shor–
Stean (CSS) code and the BB84 protocol. In Sec. 3, we show our main result. In
Sec. 4, the secure key rate of the protocol is discussed.
2. Calderbank–Shor–Stean Code and BB84 Protocol
2.1. Calderbank–Shor–Steane code
In this section, we review the CSS code,4 which is relevant to the security of theBB84 protocol.23 Let H be the two-dimensional complex linear space (qubit) withan orthonormal basis {|0, |1}. We use another orthonormal basis {|+, |−} of H,√√
and |− = |0−|1. Let F2 be a ﬁnite ﬁeld of order 2, and Fn2 be
where |+ = |0+|1
2
2
the n-dimensional vector space on F2 . For a vector x = (x1 , . . . , xn ) ∈ Fn2 , deﬁne
the quantum state|x = |x1  ⊗ · · · ⊗ |xn .
Deﬁne unitary matrices σx and σz on H by
σx |i = |i + 1,σz |i = (−1)i |i,i ∈ F2 .

For a vector e = (e1 , . . . , en ) ∈ Fn2 , deﬁne the unitary matrix
σa[e] = σae1 ⊗ · · · ⊗ σaen ,where a ∈ {x, z} and σa0 is the identity matrix on H.
A CSS code Q ⊂ H⊗n is constructed from two linear codes C1 and C2 thatsatisfy C2 ⊂ C1 ⊂ Fn2 , where dim C1 = m1 and dim C2 = m2 . Let C1⊥ and C2⊥ bedual spaces of C1 and C2 , respectively. A CSS code Q ⊂ H⊗n is spanned by
1|φu  = |u + w u ∈ C1 .
|C2 | w∈C2
For vectors x, z ∈ Fn2 , a subspace Qxz ⊂ H⊗n is spanned by1(−1)z·w |u + w + x u ∈ C1 ,|φuxz  = |C2 | w∈C2
and Qxz is also called a CSS code.

January 4, 2007 16:49 WSPC/187-IJQI

938

00231

S. Watanabe, R. Matsumoto & T. Uyematsu

In the recovery process of the CSS code, bit ﬂip error correction and phase ﬂip
error correction is decoupled from each other. The linear code C1 is related to thebit ﬂip error correction and the linear code C2⊥ is related to the phase ﬂip error[e]correction. Let Ex ⊂ Fn2 be the set such that the set {σx | e ∈ Ex } is the set ofnuncorrectable bit ﬂip errors of the CSS code, and Ez ⊂ F2 be the set such that the[e]set {σz | e ∈ Ez } is the set of uncorrectable phase ﬂip errors of the CSS code.
Definition 1. We deﬁne the decoding error probability of C1 regarded as a CSS
code over a BSC (binary symmetric channel) whose crossover probability is q asPerr (C1 , q) =Qn (e),
e∈Exnwhere Q(0) = 1−q, Q(1) = q, and Q (e) = Q(e1 )×· · ·×Q(en ) for e = (e1 , . . . , en ).
Similarly, we deﬁne the decoding error probability of C2⊥ regarded as a CSS codeover a BSC whose crossover probability is q asPerr (C2⊥ , q) =Qn (e).
e∈Ez

The decoding error probability Perr (C1 , q) represents the decoding error probabilityof bit ﬂip errors, and the decoding error probability Perr (C2⊥ , q) represents the
decoding error probability of phase ﬂip errors. See Ref. 16 for the formal deﬁnitionof Ex and Ez . We discuss Perr (C2⊥ , q) and Ez in Sec. 3 of this paper. Perr (C1 , q) andPerr (C2⊥ , q) are used to lower bound the ﬁdelity of the transmitted state suﬀered by
the noise and the recovery operation (Eq. (27) in Ref. 16). These facts follow fromthe theory of symplectic codes (stabilizer code).6,7,11,15
2.2. BB84 protocol
In this section, we review the BB84 protocol with one-way or two-way classicalcommunications. The idea of the BB84 protocol with two-way classical communications is ﬁrst proposed in Ref. 13 by extending the result of Ref. 23 to the two-way
entanglement puriﬁcation protocol (EPP).2 The protocol consists of transmissionof raw key (Steps i–iv), estimation about eavesdropper (Steps v–vii), two-way preprocessing (Step viii), error correction (Steps ix and x), and privacy ampliﬁcation(Step xi). The protocol without two-way preprocessing (Step viii) is exactly the
BB84 protocol with one-way classical communication. For a sequence k ∈ FN
2 anda subset T ⊂ {1, . . . , N }, we denote the subsequence of k that consist of ith bitwith i ∈ T by kT .
(i) Alice chooses a binary vector a ∈ FN
2 , where Pr{ai = 1} = 1/2. Alice chooses.
a random binary vector k ∈ FN
2(ii) Alice repeats the following procedures for 1 ≤ i ≤ N . If ai = 0, Alice sends
either state |0 for ki = 0 or |1 for ki = 1. If ai = 1, Alice sends either state|+ for ki = 0 or |− for ki = 1.
(iii) Bob chooses a binary vector b ∈ FN
2 , where Pr{bi = 1} = 1/2.

January 4, 2007 16:49 WSPC/187-IJQI

00231

Noise Tolerance of the BB84 Protocol with Random Privacy Amplification

939(iv) Bob repeats the following procedures for 1 ≤ i ≤ N . If bi = 0, he measures
ith received qubit with σz . If bi = 1, he measures ith received qubit with σx .
If the measurement result of ith received qubit is +1 (−1), then Bob setsk̃i = 0 (k̃i = 1). After these procedures Bob will obtain k̃ = (k̃1 , . . . , k̃N ).
(v) Alice announces a.
(vi) If ai = bi , Alice and Bob discard ith bit of k, and k̃, respectively. Let R0 ={i | ai = bi = 0} ⊂ {1, . . . , N } and R1 = {i | ai = bi = 1} ⊂ {1, . . . , N }.
R = R0 ∪ R1 are the remaining positions. Alice and Bob randomly divide R0
into S0 and T0 , and R1 into S1 and T1 . S = S0 ∪ S1 are the positions forgenerating a ﬁnal key, and T = T0 ∪ T1 are the positions for estimating error
rates. We assume |S0 | = |S1 | = |T0 | = |T1 | = N .
(vii) Alice and Bob compare kT and k̃T, and estimate error rates from tx = kT0 −k̃T0 and tz = kT1 − k̃T1 . Alice and Bob choose a random permutation π on
{1, . . . , N  }.
(viii) Let l = π(k S0 ) and l̃ = π(k̃S0 ). Alice and Bob perform the two-way preprocessing (see Sec. 7 of Ref. 13) appropriate times.
(ix) Let m ∈ Fn2 and m̃ ∈ Fn2 be Alice and Bobs’ remaining sequences in Step
viii respectively. Alice chooses a random codeword u ∈ C1 , and announcesu + m.
(x) Bob subtracts m̃ from u + m and corrects u + e to a code word ũ ∈ C1 ,where e = m + m̃.
(xi) Alice uses the coset u + C2 as the ﬁnal key, and Bob uses the coset ũ + C2
as the ﬁnal key.
We can generate the ﬁnal key from kS1 and k̃S1 in the same way, where kS1 andk̃S1 are the raw keys transmitted in the {|+, |−} basis. Before Steps ix–xi, Aliceand Bob decide a pair of linear codes C1 and C2 according to estimated error rates
and the result of two-way preprocessing.
Let px and pz be px = Ptx (1) + δ and pz = Ptz (1) + δ, where Ptx and Ptz are
the types10 of tx and tz , respectively, and δ > 0 is a suﬃciently small constant.
Then, the bit error rate p̂x and phase error rate p̂z after two-way preprocessing arecalculated from px , pz (see Ref. 13). The conditions for the protocol to be secure isgiven as follows.
(i) If C1 is used over a BSC whose crossover probability is smaller than p̂x , thenthe decoding error probability of C1 regarded as a CSS code is smaller than orequal to ε, i.e. Perr (C1 , q) ≤ ε ∀q ≤ p̂x .
(ii) If C2⊥ is used over a BSC whose crossover probability is smaller than p̂z , thenthe decoding error probability of C2⊥ regarded as a CSS code is smaller thanor equal to ε, i.e. Perr (C2⊥ , q) ≤ ε ∀q ≤ p̂z .
Note that δ is required due to the deviation of estimated error rate from the error
rate on the raw key bits (Lemma 3 in Ref. 13). Note also that ε is a small positive
number decided from the acceptable level of Eve’s information about the ﬁnal key.

January 4, 2007 16:49 WSPC/187-IJQI

940

00231

S. Watanabe, R. Matsumoto & T. Uyematsu

Although Eve’s eavesdropping on each qubit is not independently identical, the useof random permutation π in the protocol enables us to securely use linear codes C1and C2 whose decoding error probability regarded as a CSS code is small over the
BSC13,16,23 . We stress that the decoding error probabilities of C1 and C2⊥ have tobe small over any BSCs with crossover probabilities below p̂x and p̂z , instead of asingle pair of BSCs with crossover probabilities p̂x and p̂z in the conditions (i) and(ii), respectively. The necessity of such a requirement on decoding error probability
is already observed in the proof of Lemma 3 in Ref. 13 or in Ref. 16.
3. Random Privacy Amplification
To implement the BB84 protocol, we need a linear code C1 to be eﬃciently decodeable, which is used for error correction in Step x. Under the conditions (i) and(ii) of Sec. 2.2 and the condition C2 ⊂ C1 , it is diﬃcult to ﬁnd a pair of linear codes C1 and C2 of which C1 is eﬃciently decodeable. On the other hand,since we do not decode C2⊥ in the BB84 protocol, we can evaluate the condition(ii) with an arbitrary decoding method. Therefore, ﬁrst we choose a code C1 thatsatisﬁes the condition (i) and is eﬃciently decodeable. Then we will ﬁnd a code
C2 that satisﬁes the conditions (ii) and C2 ⊂ C1 . Given a code C1 , choosing acode C2 with the condition C2 ⊂ C1 is same as choosing a code C2⊥ that satisﬁes
C1⊥ ⊂ C2⊥ .
If we ﬁx a rate R lower than 1 − h(2p̂z ) and choose a code C2⊥ of rate R at
random with the condition C1⊥ ⊂ C2⊥ , then with high probability the condition (ii)is satisﬁed (Lemma 4 in Ref. 21). In this section, we will prove that if we ﬁx a
rate R lower than 1 − h(p̂z ) and choose a code C2⊥ of rate R at random with thecondition C1⊥ ⊂ C2⊥ , with high probability the condition (ii) will be satisﬁed. Some
ideas used in the proof are borrowed from Refs. 14 and 20.
3.1. The code for privacy amplification
2
Given a code C1⊥ of dimension n − m1 , ﬁx a rate R = n−m< 1 − h(p̂z ), and letn ⊥A = C2 ⊂ Fn2 | C2⊥ is a linear space, dim C2⊥ = n − m2 , C1⊥ ⊂ C2⊥

be the set from which we choose a code C2⊥ .
Theorem 1. If we choose a code C2⊥ at random from A, for arbitrary µ > 0, wehavePr Perr (C2⊥ , q) ≤ (n + 1)2 exp{−n(E(R, p̂z ) − µ)} ∀ q ≤ p̂z≥ 1 − (n + 1) exp{−µn},
where


E(R, p̂z ) = min D(p p̂z ) + |1 − R − h(p)|+ ,p

January 4, 2007 16:49 WSPC/187-IJQI

00231

Noise Tolerance of the BB84 Protocol with Random Privacy Amplification941

the base of exp(·) is 2, |x|+ = max{x, 0}, and D(· ·) is the Kullback–Leibler
information.9 Note that minp is taken over 0 ≤ p ≤ 1. Since D(p p̂z ) = 0 if andonly if p = p̂z , and R < 1 − h(p̂z ), we have E(R, p̂z ) > 0.
Consequently, we can obtain a code C2⊥ that satisﬁes the condition (ii) with highprobability by choosing a code at random from A.
3.2. Proof of the theorem
Refer to Ref. 10 for the method of type used in this section. The type of a vectore ∈ Fn2 is denoted by Pe , the set of all types of vectors in Fn2 is denoted by Pn , andfor Q ∈ Pn the set of all vectors of type Q is denoted by TQn . We use the following
bounds|Pn | ≤ (n + 1),|TQn | ≤ exp{nh(Q)} ∀ Q ∈ Pn ,pn (TQn ) ≤ exp{−nD(Q p)},where h(Q) is the entropy of the distribution Q(a) over F2 .
To evaluate the decoding error probability, we employ the minimum entropy
decoding. In the minimum entropy decoding, we choose a coset representative zfrom each coset of F2 /C2⊥ such that h(Pz ) is the minimum in the coset z + C2⊥ .
Let
E(C2⊥ ) = e ∈ Fn2 | ∃e h(Pe ) ≤ h(Pe ), e + e ∈ C2⊥ \C1⊥ .
From the general theory of symplectic codes and the property of the minimum
entropy decoding,14 we have Ez ⊂ E(C2⊥ ). Thus, we evaluate the probability(C2⊥ , q) =Perr

Qn (e).

e∈E(C2⊥ )
Observe that Perr (C2⊥ , q) ≤ Perr
(C2⊥ , q).
We classify E(C2⊥ ) by the types in Pn as

E(C2⊥ ) = ∪P ∈Pn EP (C2⊥ ),where EP (C2⊥ ) = E(C2⊥ ) ∩ TPn . First, we prove the following lemma.
Lemma 1. If we choose a code C2⊥ at random from A, for arbitrary µ > 0, we havePr

|EP (C2⊥ )|≤ exp{−n(|1 − h(P ) − R|+ − µ)} ∀ P ∈ Pn
|TPn |≥ 1 − (n + 1) exp{−µn}.

January 4, 2007 16:49 WSPC/187-IJQI

942

00231

S. Watanabe, R. Matsumoto & T. Uyematsu

Proof. We evaluate the average ofthat cannot correct e as

|EP (C2⊥ )||TPn |

over C2⊥ ∈ A. Deﬁne the set of codesB(e) = C2⊥ ∈ A | e ∈ E(C2⊥ ) .
Deﬁne C(e) asC(e) = C2⊥ ∈ A | e ∈ C2⊥ \C1⊥
and G as the set of bijective linear maps α on Fn2 that satisﬁes α(C1⊥ ) = C1⊥ . Then
we have the following equalities: ⊥
C2 ∈ A | e ∈ C2⊥ \C1⊥

= α(C2⊥ ) | e ∈ α(C2⊥ \C1⊥ ), α ∈ G, C2⊥ is ﬁxed= βα(C2⊥ ) | β(e) ∈ βα(C2⊥ \C1⊥ ), α, β ∈ G, β and C2⊥ are ﬁxed .

|C(e)| =Since there exists β ∈ G such that e = β(e) for arbitrary e and e ∈ Fn2 \C1⊥ ,|C(e)| does not depend on e ∈ Fn2 \C1⊥ and|C(e)| =⊥ |C(e)|
e∈Fn
2 \C1
n
|F2 \C1⊥ |

=

⊥
⊥
⊥
⊥ |{C2 ∈ A | e ∈ C2 \C1 }|
e∈Fn
2 \C1
|Fn2 \C1⊥ |

=

n
⊥
⊥
⊥
C2⊥ ∈A |{e ∈ F2 \C1 | e ∈ C2 \C1 }||Fn2 \C1⊥ |=|C2⊥ \C1⊥ ||A|.
|Fn2 \C1⊥ |From the deﬁnition, it is obvious that |C(e)| = 0 for e ∈ C1⊥ . Hence|C(e)| ≤|C2⊥ \C1⊥ ||A|
|Fn2 \C1⊥ |=2n−m2 − 2n−m1|A|
2n − 2n−m1=|A| 1 − 2m2 −m1
2m2 1 − 2−m1

≤

|A|
2 m2

= |A| exp{−n(1 − R)}.

January 4, 2007 16:49 WSPC/187-IJQI

00231

Noise Tolerance of the BB84 Protocol with Random Privacy Amplification

943

Because the condition for C2⊥ ∈ A to belong to B(e) is ∃e , h(Pe ) ≤ h(Pe ), e+e ∈C2⊥ \C1⊥ , we obtain|B(e)|
1
≤
|A|
|A|


e ∈Fn2h(P  )≤h(Pe )e≤|C(e + e )|exp{−n(1 − R)}.

e ∈Fn2h(P  )≤h(Pe )e

We also have a trivial upper bound |B(e)||A| ≤ 1. Thus we have









|B(e)|≤ minexp{−n(1 − R)}, 1 .


|A|


 e ∈Fn2h(Pe )≤h(Pe )Let |x|+ = max{x, 0} and note that if a, b ≥ 0, then min{a + b, 1} ≤ min{a, 1} +min{b, 1}. Using the above deﬁnitions, we have1  |EP (C2⊥ )||A| ⊥|TPn |C2 ∈A

1  |B(e)||TPn |
|A|
e∈TPn









1 
min
exp{−n(1 − R)}, 1
≤ n


|TP |


e∈TPn
 e ∈Fn2h(P  )≤h(Pe )
e






 

n
= min
|TP  | exp{−n(1 − R)}, 1
 P  ∈Pnh(P  )≤h(P )≤
exp{−n|1 − R − h(P  )|+ }=P  ∈Pnh(P  )≤h(P )≤ |Pn |max

P  ∈Pnexp{−n|1 − R − h(P  )|+ }h(P  )≤h(P )≤ (n + 1) exp{−n|1 − R − h(P )|+ .
Let AP and Ag be|EP (C2⊥ )|⊥+> (n + 1) exp{−n(|1 − R − h(P )| − µ)} ,AP = C2 ∈ A ||TPn |Ag = A\ ∪P ∈Pn AP .

January 4, 2007 16:49 WSPC/187-IJQI

944

00231

S. Watanabe, R. Matsumoto & T. Uyematsu

From the union bound and the Chebychev inequality, we have
| ∪P ∈Pn AP |
|Ag |
= 1−
|A|
|A|
 |AP |
≥ 1−
|A|
P ∈Pn



≥ 1−

P ∈Pn

(n + 1) exp{−n|1 − R − h(P )|+ }(n + 1) exp{−n(|1 − R − h(P )|+ − µ)}≥ 1 − (n + 1) exp{−µn}.
The probability Perr
(C2⊥ , q) of C2⊥ ∈ Ag is upper bounded as
(C2⊥ , q) =Qn (e)Perre∈E(C2⊥ )=Qn (e)

P ∈Pn e∈EP (C2⊥ )= |EP (C ⊥ )|
2

P ∈Pn

≤



|TPn |Qn (TPn )(n + 1) exp{−n(|1 − R − h(P )|+ − µ)}(by Lemma 1)

P ∈Pn

× exp{−nD(P ||q)}≤ |Pn | max (n + 1) exp{−n(|1 − R − h(P )|+ − µ)}P ∈Pn

× exp{−nD(P ||q)}≤ (n + 1)2 exp{−nE(R, q) − µ},
where


E(R, q) = min D(p||q) + |1 − R − h(p)|+ .
p

We can rewrite E(R, q) into the form√√
−R + 1 − 2 log( q + 1 − q) if 0 ≤ R < R ,E(R, q) =D(q ∗ ||q)if R ≤ R < 1 − h(q),√√ √where R = 1 − h(q  ), q  = q/( q + 1 − q), and q ∗ satisﬁes R = 1 − h(q ∗ ) (seep. 168, pp. 192–193 of Ref. 10). Thus E(R, q) is an increasing function of q for aﬁxed R, and we have min0≤q≤pz E(R, q) = E(R, pz ) and
(C2⊥ , q) ≤ (n + 1)2 exp{−n(E(R, pz ) − µ)}Perr∀ q ≤ pz .

January 4, 2007 16:49 WSPC/187-IJQI

00231

Noise Tolerance of the BB84 Protocol with Random Privacy Amplification

945

4. Secure Key Rate
In this section, we discuss the secure key rate of the BB84 protocol. When we use
a linear code C1 of rate close to 1 − h(p̂x ) and choose a linear code C2 at random
from subcodes of C1 , according to Lemma 4 in Ref. 21, the secure key rate after
C2
is about
two-way preprocessing Rkey = dim C1 −dimn1 − h(p̂x ) − h(2p̂z ).
According to our result in Sec. 3, the secure key rate is about
1 − h(p̂x ) − h(p̂z ).
Note that the secure key rate 1−h(px )−h(pz ) with the random privacy ampliﬁcationin the BB84 protocol with one-way classical communication is already shown in
Refs. 8 and 22, where px and pz are error rates without two-way preprocessing.
5. Conclusion
In this paper, we have shown that for a ﬁxed linear code C1 , if we choose a linear code C2 ⊂ C1 at random with rate h(p̂z ), then C2 satisﬁes the condition forthe security with high probability. Consequently, when we use the random privacy
ampliﬁcation in the BB84 protocol with one-way or two-way classical communication, the secure key rate is increased and the protocol can tolerate more severe
noise.
Acknowledgments
We appreciate the helpful comment by Dr. Masahito Hayashi on an earlier version ofthis paper. This research is partly supported by the Japan Society for the Promotionof Science under Grants–in–Aid for Young Scientists No. 16760289.
References
1. C. H. Bennett and G. Brassard, Quantum cryptography: Public key distribution andcoin tossing, in Proc. IEEE Int. Conf. Computers, Systems, and Signal Processing,Bangalore, India (1984), pp. 175–179.
2. C. H. Bennett, D. P. DiVincenzo, J. A. Smolin and W. K. Wootters, Mixed-state
entanglement and quantum error correction, Phys. Rev. A 68(5) (1996) 3824–3851.
[quant-ph/9604024].
3. E. Biham, M. Boyer, P. O. Boykin, T. Mor and V. Ryoichowdhury, A proof of the
security of quantum key distribution, in Proc. 32nd Ann. ACM Symp. Theory ofComputing, New York (2000), pp. 715–724 [quant-ph/9912053].
4. A. R. Calderbank and P. W. Shor, Good quantum error correcting codes exist, Phys.
Rev. A 54(2) (1996) 1098–1105 [quant-ph/9512032].
5. H. F. Chau, Practical scheme to share a secret key through a quantum channel witha 27.6% bit error rate, Phys. Rev. A 66(6) (2002) 060302 [quant-ph/0205060].
6. A. R. Calderbank, E. M. Rains, P. W. Shor and N. J. A. Sloane, Quantum
error correction and orthogonal geometry, Phys. Rev. Lett. 78(3) (1997) 405–408[quant-ph/9605005].

January 4, 2007 16:49 WSPC/187-IJQI

946

00231

S. Watanabe, R. Matsumoto & T. Uyematsu

7. A. R. Calderbank, E. M. Rains, P. W. Shor and N. J. A. Sloane, Quantum error
correction via codes over GF (4), IEEE Trans. Inform. Theory 44(4) (1998) 1369–
1387 [quant-ph/9608006].
8. M. Christandl, R. Renner and A. Ekert, A generic security proof for quantum key
distribution, quant-ph/0402131v2.
9. T. M. Cover and J. A. Thomas, Elements of Information Theory (Wiley, New York,
1991).
10. I. Csiszár and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems (Akademiai Kiado, 1981).
11. D. Gottesman, Class of quantum error-correcting codes saturating the quantum Hamming bound, Phys. Rev. A 54(3) (1996) 1862–1868 [quant-ph/9604038].
12. D. Gottesman and J. Preskill, Secure quantum key distribution using squeezed states,
Phys. Rev. A 63(2) (2000) 022309 [quant-ph/0008046].
13. D. Gottesman and H.-K. Lo, Proof of security of quantum key distribution with twoway classical communications, IEEE Trans. Inform. Theory 49(2) (2003) 457–475[quant-ph/0105121].
14. M. Hamada, Exponential lower bound on the highest ﬁdelity achievable by quantum
error-correcting codes, Phys. Rev. A 65(5) (2002) 052305 [quant-ph/0109114].
15. M. Hamada, Notes on the ﬁdelity of symplectic quantum error-correcting codes, Int.
J. Quant. Inf. 1(4) (2003) 443–463 [quant-ph/0311003].
16. M. Hamada, Reliability of Calderbank-Shor-Steane codes and security of quantum key
distribution, J. Phys. A: Math. Gen. 37(34) (2004) 8303–8328 [quant-ph/0308029].
17. R. König, U. Maurer, and R. Renner, On the power of quantum memory, IEEE Trans.
Inform. Theory 51(7) (2005) 2391–2401 [quant-ph/0305154].
18. H.-K. Lo, H. F. Chau and M. Ardehali, Eﬃcient quantum key distribution schemeand proof of its unconditional security, J. Cyptol. 18(2) (2005) 133–165 [quantph/0011056].
19. H.-K. Lo, Proof of unconditional security of six-state quantum key distribution
scheme, Quant. Inform. Comput. 1(2) (2001) 81–94 [quant-ph/0102138].
20. R. Matsumoto and T. Uyematsu, Lower bound for the quantum capacity of a discrete memoryless quantum channel, J. Math. Phys. 43(9) (2002) 4391–4403 [quantph/0105151].
21. D. Mayers, Unconditional security in quantum cryptography, J. ACM 48(3) (2001)
351–406 [quant-ph/9802025].
22. R. Renner, N. Gisin and B. Kraus, Information-theoretic security proof for quantumkey-distribution protocols, Phys. Rev. A 72 (2005) 012332 [quant-ph/0502064].
23. P. W. Shor and J. Preskill, Simple proof of security of the BB84 quantum key distribution protocol, Phys. Rev. Lett. 85(2) (2000) 441–444 [quant-ph/0003004].
24. X.-B. Wang, Quantum key distribution with asymmetric channel noise, Phys. Rev. A
71 (2005) 052328 [quant-ph/0406099].
25. X.-B. Wang, BDSW protocol revisited: an eﬃcient method for the key distillation
without classical computational complexity, quant-ph/0409099v2.