IEICE TRANS. FUNDAMENTALS, VOL.E91–A, NO.10 OCTOBER 2008

2870

LETTER

Special Section on Information Theory and Its Applications

Key Rate Available from Mismatched Measurements in the BB84
Protocol and the Uncertainty Principle
Ryutaroh MATSUMOTO†a) , Member and Shun WATANABE† , Student Member

SUMMARY
We consider the mismatched measurements in the BB84
quantum key distribution protocol, in which measuring bases are diﬀerent
from transmitting bases. We give a lower bound on the amount of a secret
key that can be extracted from the mismatched measurements. Our lower
bound shows that we can extract a secret key from the mismatched measurements with certain quantum channels, such as the channel over which
the Hadamard matrix is applied to each qubit with high probability. Moreover, the entropic uncertainty principle implies that one cannot extract thesecret key from both matched measurements and mismatched ones simultaneously, when we use the standard information reconciliation and privacy
amplification procedure.
key words: BB84, mismatched measurement, quantum key distribution

1.

Introduction

The BB84 protocol [1] is one of the most-known protocols
for quantum key distribution. In this protocol, the sender,
Alice, sends qubits in √one of four quantum state√ vectors |0,
|1, |+ = (|0 + |1)/ 2, |− = (|0 − |1)/ 2, where {|0,|1} forms an orthonormal basis. Then the receiver, Bob,
measures the received qubits with either {|0, |1} or {|+,|−} basis. After that, Alice publicly announces to which{|0, |1} or {|+, |−} basis each qubit belong. Bob discard
the measurement outcomes whose bases do not contain thetransmitted qubit. We call such measurement mismatchedmeasurement in this paper. After that, Alice and Bob perform the information reconciliation and the privacy amplification to obtain the same secret key as described in [12].
As far as the authors know, there is no literature thatclarifies the amount of key that can be extracted frommismatched measurements in the BB84 protocol, though
Pawlowski [10] studied the same problem with a protocol
completely diﬀerent from the BB84. The eﬃciency of aquantum key distribution (QKD) protocol is measured by
the ratio of extracted bits of secret key per remaining bits
not disclosed nor discarded, which is called key rate. We
shall show a lower bound on the key rate that can be extracted from mismatched measurements in the BB84 protocol. Moreover, we shall show that, when we use the standard information reconciliation and privacy amplification in[12] and the well-known lower bound on the key rate [4],the entropic uncertainty principle [8] implies that one canManuscript received January 15, 2008.
Manuscript revised March 31, 2008.
†
The authors are with the Department of Communications andIntegrated Systems, Tokyo Institute of Technology, Tokyo, 1528550 Japan.
a) E-mail: ryutaroh@rmatsumoto.org
DOI: 10.1093/ietfec/e91–a.10.2870

not extract the secret key from both matched measurements
and mismatched ones simultaneously.
The reader may think that the probability of getting
the measurement outcome |+ is always 0.5 when the transmitted qubit is |0, and considering mismatched measurement outcomes is useless and nonsense. We cannot extracta secret key from mismatched measurement outcomes whensuch a probability is 0.5. However, consider the quantum
channel over which the Hadamard matrix is applied to each
qubit with high probability. With such a quantum channel
the above probability is close to 0 or 1. The lower boundobtained in this paper shows that we can extract a secret key
from mismatched measurement outcomes with such a quantum channel.
This paper is organized as follows: Section 2 presents avariant of the BB84 protocol. Section 3 verifies its unconditional security and shows a lower bound on its key rate. Section 4 shows that the lower bounds on the key rates available
from matched measurements and mismatched ones cannot
be simultaneously positive, by using the entropic uncertainty principle [8]. Section 5 gives concluding remarks andlists several open research questions.
2.

ProtocolIn this section, we shall show a variant of the BB84 protocolthat tries to extract secret key from mismatched measurement outcomes. We define the matrices X and Z representing the bit error and the phase error, respectively, as
X|0 = |1, X|1 = |0,
Z|+ = |−, Z|− = |+.
1. Alice makes a random qubit sequence according to
the i.i.d. uniform distribution on {|0, |1, |+, |−} andsends it to Bob.
2. Bob chooses the {|0, |1} basis or {|+, |−} basis uniformly randomly for each received qubit and measure
it by the chosen basis.
3. Alice publicly announces which basis {|0, |1} or {|+,|−} each transmitted qubit belongs to. Bob also publicly announces which basis was used for measurementof each qubit. In the following steps they will only consider qubits with which transmission basis and measuring bases do not coincide between Alice and Bob.
4. Suppose that there are 2n qubits transmitted in the {|0,|1} basis and measured with the {|+, |−} basis by Bob.

c 2008 The Institute of Electronics, Information and Communication Engineers
Copyright 

LETTER

2871

Index those qubits by 1, . . . , 2n. Define the bit ai = 0 if
Alice’s i-th qubit was |0, and ai = 1 otherwise. Define
the bit bi = 0 if Bob’s measurement outcome for i-th
qubit was |+, and bi = 1 otherwise.
5. Suppose also that there are 2n qubits transmitted in the{|+, |−} basis and measured with the {|0, |1} basis
by Bob. Index those qubits by 1, . . . , 2n . Define thebit αi = 0 if Alice’s i-th qubit was |+, and αi = 1
otherwise. Define the bit βi = 0 if Bob’s measurement
outcome for i-th qubit was |0, and βi = 1 otherwise.
For the simplicity of the presentation, we shall describe theprocedure extracting the secret key from ai and bi . The key
rate for αi , βi will turn out to be the same as that for ai , bi
at the end of Sect. 3.2. In the following steps, the half ofmeasurement outcomes will be disclosed and used for estimation of error rates qX and qZ . The amount of disclosure
can be arbitrarily chosen provided that the estimation of error rates can be done suﬃciently accurately.
6. Alice chooses a subset S ⊂ {1, . . . , 2n} with size |S | = n
uniformly randomly from subsets of {1, . . . , 2n}, andpublicly announces the choice of S . Alice and Bob
publicly announce ai and bi for i ∈ S and compute theerror rateqX =|{i ∈ S | ai  bi }|
.
|S |

(1)

7. Alice chooses a subset S  ⊂ {1, . . . , 2n } with size
|S  | = n uniformly randomly from subsets of {1, . . . ,2n }, and publicly announces the choice of S  . Aliceand Bob publicly announce αi and βi for i ∈ S  andcompute the error rateqZ =|{i ∈ S  | αi  βi }|.
|S  |(2)

8. Alice and Bob decide a linear code C1 of length n suchthat its decoding error probability is suﬃciently small
over all the binary symmetric channel whose crossoverprobability is close to qX . Let H1 be a parity checkmatrix for C1 , a be Alice’s remaining (not announced)
bits among ai ’s, and b be Bob’s remaining bits amongbi ’s.
9. Alice publicly announces the syndrome H1a.
10. If qX > 0.5 then Bob negates every bit in b before executing the following steps.
11. Bob compute the error vector f such that H1 f = H1b −H1a by the decoding algorithm for C1 . With high probability b − f = a.
12. Alice chooses a subspace C2 ⊂ C1 with dim C2 =nh(qZ ) uniformly randomly, where h denotes the binary
entropy function, and publicly announces her choice of
C2 . The final shared secret key is the coset a + C2 .
When measuring bases are the same as the transmitting bases, we can use the standard BB84 protocol. Thus,
we discard no measurement outcome when we combine theabove protocol with the standard BB84.

3.

Security Proof and a Lower Bound on the Key Rate

We shall verify the unconditional security of our proposed
protocol by directly relating it to the quantum error correction by the quantum CSS (Calderbank-Shor-Steane) codes[2], [13]. To make this paper self-contained, we shall briefly
review the CSS code. After that we shall relate our variantof the BB84 protocol to the CSS code in a similar way to
Shor and Preskill [12].
3.1 Review of the CSS CodeFor a binary vector v = (v1 , . . . , vn ) ∈ Fn2 , where F2 is the
Galois field with two elements, we define the quantum statevector |v by|v = |v1  ⊗ · · · ⊗ |vn .
For two binary linear codes C2 ⊂ C1 ⊂ Fn2 , the CSS code is
the complex linear space spanned by the vectors
1 |v + w
 ,√
|C2 | w ∈C2
for all v ∈ C1 . We also need parameterized CSS codes introduced in [12]. The parameterized CSS code for x,z ∈ Fn2 isdefined as the linear space spanned by1 (−1)(z,w) |x + v + w
 ,
(3)
√
|C2 | w ∈C2
for all v ∈ C1 , where (·, ·) denotes the inner product.
3.2 Security Proof and Analysis of the Key Rate
We shall first show that our protocol is equivalent to sendinga parameterized CSS codeword with the parameter z randomly chosen. If we fix v and x and choose z uniformly
randomly in Eq. (3), then the resulting density operator is⎛⎞⎟⎟⎟1  ⎜⎜⎜⎜⎜ (z,w1 )
⎟⎟⎟⎟
(−1)
|
x
+

v
+
w


⎜
1
⎜
⎠
2n |C2 | n ⎝z∈F2 w1 ∈C2

⎞
⎛
⎟⎟⎟
⎜⎜⎜ 
⎟⎟
⎜⎜⎜
(z,w2 )
(−1)

x
+

v
+
w

|
2⎟
⎟⎠
⎜⎝
w2 ∈C2=

1 |x + v + w
  x + v + w
 |,
|C2 |

(4)

w
 ∈C2

by the exactly same argument as [12].
Denote the right hand side of Eq. (4) by ρ(x,v). By astraightforward computation we can see
1 
1 ρ(x,v) = n|a a|.
(5)n
2 |C1 | n2nx∈F2 v∈C1

a∈F2

The right hand side of Eq. (5) means sending |0 or |1 ntimes with equal probability, which is exactly what Alice isIEICE TRANS. FUNDAMENTALS, VOL.E91–A, NO.10 OCTOBER 2008

2872

doing in our protocol. Announcing the syndrome H1a in
Step 9 is equivalent to announcing which x is chosen.
Consider the Hadamard matrix H defined by H|0 =|+ and H|1 = |−. Consider the memoryless quantum
channel Γ over which the error HX occurs with probability
rX , HZ occurs with probability rZ , HXZ occurs with probability rXZ , and H occurs with probability 1−rX −rZ −rXZ , with
qX = rX + rXZ and qZ = rZ + rXZ . The qubits received by Bob
can be regarded as the output of Γ when Alice sends |0 and|1 with equal probability, which is equivalent to sending aquantum codeword in the CSS code as described above.
If we apply H −1 to each qubit, then the quantum channel can be regarded as causing the X error with probability
rX , the Z error with probability rZ , and the XZ error withprobability rXZ . Therefore, if we use the standard decoding
procedure of the CSS code after applying H −1 to each qubit
in the received codeword, then the transmitted CSS codeword is recovered with high fidelity provided that qX < 0.5
and qZ < 0.5. Observe also that this imaginary quantum decoding process is equivalent to what is actually performedin our variant of the BB84 protocol described in Sect. 2 by
the almost same argument as [12].
When qX > 0.5 and qZ < 0.5, applying X to each qubit
in the received codeword after H −1 makes qX to 1 − qX andleaves qZ unchanged. When qX < 0.5 and qZ > 0.5, apply
Z to each qubit, and when qX > 0.5 and qZ > 0.5, apply
XZ. By the above operations we can regard both qX and qZ
being less than 0.5 provided that qX  0.5 and qZ  0.5.
Observe that application of Z is purely imaginary and does
not correspond to the actual operations in the protocol in
Sect. 2. On the other hand, application of X corresponds toflipping each bit in Step 10 in our protocol. Application of
XZ is equivalent to that of X in the actual protocol.
We have shown that the procedure in Sect. 2 can be regarded as the quantum error correction of the CSS code overa peculiar quantum channel Γ. It was shown in Corollary 2of [3] that there exists a linear code C1 of information rate
1 − h(qX ) satisfying the condition in Step 8. If we use suchC1 then we can correct HX errors on Γ with high probability.
It is stated in [12] and proved in [14] that random
choice of [n − nh(qZ )]-dimensional subspace C2 in C1 almost always gives the low phase error decoding probability
in the standard CSS decoding procedure. This implies that
randomly chosen [n − nh(qZ )]-dimensional subspace C2 in
C1 can almost always correct HZ errors on Γ. Therefore, if
the choice of C1 is appropriate, then the fidelity of quantum
error correction in the imaginary transmission of the CSS
codeword (3) over the channel Γ is close to 1, which implies
that the eavesdropper Eve can obtain little information by
the same argument as [5], which shows the security of theBB84 protocol directly relating it to the quantum error correction without use of entanglement distillation argument.
Therefore, we can extract 1 − h(qX ) − h(qZ ) bit of secret
key from one bit of the raw bits a. With a similar argument,
we can also see that the key rate available from αi ’s is 1 −h(qX ) − h(qZ ). Because with the key rate from αi ’s the roles
of qX and qZ are interchanged, which does not change thekey rate 1 − h(qX ) − h(qZ ).
4.

Implication by the Uncertainty Principle

At the end of Sect. 2, we stated that we try to extract asecret key from both matched measurement outcomes andmismatched ones. In this section, we shall consider the
relation between the amount of secret key extracted frommatched measurement outcomes and that from mismatched
ones. We shall show that we cannot extract secret key fromboth matched and mismatched measurement outcomes by
the entropic version [8] of the uncertainty principle, when
we use the information reconciliation and privacy amplification in [12] and the lower bound on its key rate in [4].
Note that Koashi already used the uncertainty principle forsecurity analysis of QKD protocols [6].
Maassen and Uﬃnk [8] (see also Box 11.1 of [9])proved the following version of uncertainty principle interms of the Shannon entropy. Let ρ be a density operator ofa qubit. Let P01 (resp. P+− ) be the probability distribution of
the measurement outcome by measuring ρ by {|0, |1} (resp.
{|+, |−}). Let H(·) denotes the Shannon entropy. Then we
have H(P01 ) + H(P+− ) ≥ 1 as described at Eq. (11.3) in [9],where the entropy is counted in the unit of bits.
Let Γ be the memoryless quantum channel that represents Eve’s manipulation and the channel noise between Alice and Bob. Γ is a map between density operators. DefinepX− = +|Γ(|− −|)|+,
pX+ = −|Γ(|+ +|)|−,
qX1 = +|Γ(|1 1|)|+,
qX0 = −|Γ(|0 0|)|−,
pZ1 = 0|Γ(|1 1|)|0,
pZ0 = 1|Γ(|0 0|)|1,
qZ− = 0|Γ(|− −|)|0,
qZ+ = 1|Γ(|+ +|)|1.
Observe that qX = (qX0 + qX1 )/2 and qZ = (qZ+ + qZ− )/2,
where qX and qZ are as defined in Eqs. (1) and (2).
Define pX = (pX+ + pX− )/2 and pZ = (pZ0 + pZ1 )/2.
Observe that pZ (resp. pX ) is the error rate of the matchedmeasurement in the BB84 protocol when transmitting basis
is {|0, |1} (resp. {|+, |−}). The lower bound on key rate of
the plain one-way postprocessing described in [12] is given
by 1 − h(pX ) − h(pZ ) [4].
From the entropic uncertainty principle reviewed at the
beginning of this section, we haveh(pX+ ) + h(qZ+ ) ≥ 1,h(pX− ) + h(qZ− ) ≥ 1,
h(pZ0 ) + h(qX0 ) ≥ 1,
h(pZ1 ) + h(qX1 ) ≥ 1.

(6)
(7)
(8)
(9)

By the concavity of the entropy functionh(pX ) = h

pX+ + pX−
h(pX+ ) + h(pX− )
,
≥
2
2

(10)

LETTER

2873

qZ+ + qZ−
h(qZ+ ) + h(qZ− ),≥22
pZ0 + pZ1
h(pZ0 ) + h(pZ1 )h(pZ ) = h,≥
22
qX0 + qX1
h(qX0 ) + h(qX1 )h(qX ) = h≥.
22h(qZ ) = h

(11)
(12)
(13)

Applying Eqs. (10) and (11) to the sum of Eqs. (6) and (7)divided by two, we obtainh(pX ) + h(qZ ) ≥ 1.

(14)

From Eqs. (8, 9, 12, 13) in a similar manner we obtainh(pZ ) + h(qX ) ≥ 1.

(15)

Equations (14) and (15) imply[1 − h(pX ) − h(pZ )] + [1 − h(qX ) − h(qZ )] ≤ 0.

Acknowledgment
This research was partly supported by the Japan Society for the Promotion of Science under Grants-in-Aid No.
18760266 and No. 00197137.
References(16)

The first term in Eq. (16) is the lower bound on key rate of
the matched measurement in the BB84 protocol, while thesecond term is that of the mismatched measurement. Equation (16) means that both lower bounds on key rates cannot
be simultaneously positive.
5.

rately postprocess bits obtained by matched measurements
and mismatched ones, because the matched measurement
outcomes are processed with the standard BB84 protocol
separately. It is not clear whether or not such separate processing of matched and mismatched measurement outcomesdecreases the total amount of secret key. We leave thesequestions as future research agenda. Note added in proof:
The second problem was recently solved in [16].

Concluding Remarks

We proposed a variant of the BB84 protocol that extracts secret key from measurement outcomes with which measuringbases are diﬀerent from transmitting bases, obtained a lower
bound on the key rate which has a similar form to that of thestandard BB84 protocol, and verified its unconditional security. After that, we showed that the lower bounds on the
key rates available from matched and mismatched measurements cannot be simultaneously positive.
Our result generates a number of interesting researchquestions. Firstly, the well-known upper bound (Table I
in [4]) on the key rates of the BB84 protocol [12] is expressed in terms of error rates for matched measurementswith which measuring bases are the same as the transmitting bases. If both error rates for the matched bases are 0.5,
for example the Hadamard matrix is applied to every qubit,then those upper bounds state that we cannot extract secretkey. However, our proposed variant of the BB84 protocol
can extract secret key in such case. It is desirable to havean upper bound on the amount of available secret key taking
into account mismatched measurement in the BB84 protocol.
Secondly, we could not disprove the possibility that we
can extract secret key from both matched and mismatchedmeasurements by more sophisticated postprocessing of theBB84 protocol such as Refs. [4], [7], [11], [15]. It is desirable to prove or disprove such possibility.
Thirdly, in the standard BB84 protocol, it is generally
believed that we can postprocess bits transmitted by {|0, |1}basis and {|+, |−} basis separately without decreasing the
key rate. The proposed variant of the BB84 protocol sepa-[1] C.H. Bennett and G. Brassard, “Quantum cryptography: Public key
distribution and coin tossing,” Proc. IEEE Intl. Conf. on Computers,
Systems, and Signal Processing, pp.175–179, 1984.
[2] A.R. Calderbank and P.W. Shor, “Good quantum error-correcting
codes exist,” Phys. Rev. A, vol.54, no.2, pp.1098–1105, Aug. 1996.
[3] I. Csizár, “Linear codes for sources and source networks: Error exponents, universal coding,” IEEE Trans. Inf. Theory, vol.28, no.4,
pp.585–592, July 1982.
[4] D. Gottesman and H.K. Lo, “Proof of security of quantum key distribution with two-way classical communications,” IEEE Trans. Inf.
Theory, vol.49, no.2, pp.457–475, Feb. 2003.
[5] M. Hamada, “Reliability of Calderbank-Shor-Steane codes and security of quantum key distribution,” J. Phys. A, Math. Gen., vol.37,
no.34, pp.8303–8328, Aug. 2004.
[6] M. Koashi, “Unconditional security of quantum key distribution andthe uncertainty principle,” J. Physics: Conference Series, vol.36,
pp.98–102, 2006.
[7] X. Ma, C.H.F. Fung, F. Dupuis, K. Chen, K. Tamaki, and H.K. Lo,“Decoy-state quantum key distribution with two-way classical postprocessing,” Phys. Rev. A, vol.74, no.3, 032330, Sept. 2006.
[8] H. Maassen and J.B.M. Uﬃnk, “Generalized entropic uncertainty relations,” Phys. Rev. Lett., vol.60, no.2, pp.1103–1106, March 1988.
[9] M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum
Information, Cambridge University Press, Cambridge, UK, 2000.
[10] M. Pawlowski, “How not to discard half of the cases in QKD,”
arXiv:0708.0933, Aug. 2007.
[11] R. Renner, N. Gisin, and B. Kraus, “Information-theoretic security
proof for quantum-key-distribution protocols,” Phys. Rev. A, vol.72,
no.1, 012332, July 2005.
[12] P.W. Shor and J. Preskill, “Simple proof of security of the BB84
quantum key distribution protocol,” Phys. Rev. Lett., vol.85, no.2,
pp.441–444, July 2000.
[13] A.M. Steane, “Multiple particle interference and quantum error correction,” Proc. Roy. Soc. London Ser. A, vol.452, no.1954, pp.2551–
2577, Nov. 1996.
[14] S. Watanabe, R. Matsumoto, and T. Uyematsu, “Noise toleranceof the BB84 protocol with random privacy amplification,” International Journal on Quantum Information, vol.4, no.6, pp.935–946,
Dec. 2006.
[15] S. Watanabe, R. Matsumoto, T. Uyematsu, and Y. Kawano, “Keyrate of quantum key distribution with hashed two-way classical communication,” Phys. Rev. A, vol.76, no.3, 032312, Sept. 2007.
[16] S. Watanabe, R. Matsumoto, and T. Uyematsu, “Tomography increases key rates of guantum-key-distribution protocols,” to be published in Phys. Rev. A, arXiv: 0802.2419.