PHYSICAL REVIEW A 76, 032312 共2007兲

Key rate of quantum key distribution with hashed two-way classical communication
Shun Watanabe,* Ryutaroh Matsumoto,† and Tomohiko Uyematsu‡
Department of Communication and Integrated Systems, Tokyo Institute of Technology, 2-12-1, Oookayama, Meguro-ku,
Tokyo, 152-8552, Japan

Yasuhito Kawano§
NTT Communication Science Laboratories, NTT Corporation, 3-1, Wakamiya, Morinosato, Atsugishi,
Kanagawa Prefecture, 243-0198, Japan
共Received 3 June 2007; published 12 September 2007兲
We propose an information reconciliation protocol that uses two-way classical communication. The key rates
of quantum key distribution 共QKD兲 protocols that use our protocol are higher than those using previously
known protocols for a wide range of error rates for the Bennett-Brassard 1984 and six-state protocols. We also
clarify the relation between the proposed and known QKD protocols, and the relation between the proposed
protocol and entanglement distillation protocols.
DOI: 10.1103/PhysRevA.76.032312

PACS number共s兲: 03.67.Dd, 89.70.⫹c

I. INTRODUCTIONQKD protocols that include the BB84 protocol and the sixstate protocol has been proved 关13–15兴, based on
information-theoretical techniques instead of Shor and
Preskill’s technique.
In addition to the security of QKD protocols, the key rates
of QKD protocols are also important, where the key rate isdefined by the ratio of the length of the final secure key tothe length of the raw key. Gottesman and Lo 关16兴 converted
EDPs that use two-way classical communication into QKD
protocols that use the same communication. More specifically, they proposed preprocessing that uses two-way classical communication. By inserting this two-way preprocessing
before the conventional one-way IR protocol, the key rates
of QKD protocols are increased when the error rate of achannel expressed as a percentage is higher than about 9%.
Indeed, the tolerable error rate of the BB84 protocol is increased from 11% to 18.9%, and that of the six-state protocol
is increased from 12.7% to 26.4%, where the tolerable error
rate is the error rate at which the key rate becomes zero.
Chau later showed that the two-way BB84 protocol can tolerate 20.0% error rate, and that the two-way six-state protocol can tolerate 27.6% error rate 关17兴. Recently, this kind of
two-way preprocessing has been applied to QKD protocols
with weak coherent pulses 关18,19兴. It should be noted that
this preprocessing is also known within the classical key
agreement context, in which it is usually called an advantage
distillation protocol 关20兴. Bae and Acín and Acín et al.
关21,22兴 extensively studied the tolerable error rate of QKD
protocols with advantage distillation protocols; on the other
hand, we are interested in the key rates of QKD protocols inthis paper.
Vollbrecht and Vestraete proposed a new type of two-way
EDP 关23兴. This protocol uses previously shared EinsteinPodolsky-Rosen 共EPR兲 pairs as an assistant resource 共twoway breeding EDP兲, and the distillation rate of this EDP
exceeds that of one-way EDPs for a whole range of fidelities,
where the fidelity is that between the initial mixed state andthe EPR pair. Using the fact that a breeding EDP can beconverted into a QKD protocol assisted by one-time pad encryption with a preshared secret key 关24兴, Vollbrecht and
Vestraete’s two-way breeding EDP 关23兴 was converted into a

Quantum key distribution 共QKD兲 protocols provide a way
for two parties, a sender, Alice, and a receiver, Bob, to sharean unconditionally secure key in the presence of an eavesdropper, Eve. Unlike conventional schemes of key distribution that rely on unproven computational assumptions, thesecurity of QKD protocols is guaranteed by the principles ofquantum mechanics.
QKD protocols usually consist of two parts, a quantum
and a classical part. Alice sends a binary sequence to Bob in
the quantum part by encoding it into quantum states that are
randomly chosen from a set of nonorthogonal states. Since
unknown nonorthogonal states cannot be cloned perfectly,
any eavesdropping attempt by Eve will disturb the transmitted quantum states. Thus, by estimating the error rate of thetransmitted quantum states, Alice and Bob can estimate theamount of information that Eve has gained. For the sequencethat remains after the error estimation phase, which is usually called the raw key, Alice and Bob first carry out an
information reconciliation 共IR兲 protocol 关1,2兴 to share thesame bit sequence. Alice and Bob then distill the final secure
key by conducting a privacy amplification 共PA兲 protocol
关2,3兴.
The best-known QKD protocols are the Bennett-Brassard
1984 共BB84兲 protocol 关4兴 and the six-state protocol 关5兴. The
unconditional security of the BB84 protocol has been proved关6–8兴. Shor and Preskill 关9兴 presented a simple proof of theBB84 protocol by showing that the QKD protocol that uses
the entanglement distillation protocol 共EDP兲 关10,11兴 can beconverted into the BB84 protocol. After that, the unconditional security of the six-state protocol was proved 关12兴 using
the same technique as in 关9兴. Recently, the security of generic*shun-wata@it.ss.titech.ac.jp†

ryutaroh@rmatsumoto.org; URL: http://www.rmatsumoto.org/
research.html‡
uyematsu@ieee.org§
kawano@theory.brl.ntt.co.jp
1050-2947/2007/76共3兲/032312共7兲

032312-1©2007 The American Physical Society

PHYSICAL REVIEW A 76, 032312 共2007兲

WATANABE et al.

two-way QKD protocol assisted by one-time pad encryption
关18,25兴. The key rate of the converted QKD protocol ishigher than that of one-way QKD protocols 关9,12兴 for awhole range of error rates. It should be noted that the use ofa preshared secret key is not the basis of their improvement,
because any QKD protocol that makes use of a preshared key
can be transformed into an equally efficient protocol that
does not need a preshared secret key 关26兴.
We propose an IR protocol that uses two-way classicalcommunication in this paper. Our proposed protocol is basedon Vollbrecht and Vestraete’s idea of a two-way breeding
EDP 关23兴, but does not require any preshared secret keys.
Furthermore, our protocol does not leak information that isredundantly leaked to Eve in 关18,25兴. More precisely, inthese protocols 关18,25兴, Alice sends a redundant message
that is useless to Bob, but is useful to Eve. However, in the
proposed protocol, Alice does not send that redundant information. As a result, for the BB84 and six-state protocols, thekey rates of the QKD protocols that use our IR protocol arehigher than those of previously known protocols for a wide
range of error rates. In particular, the key rate of our protocol
is higher than those of known protocols 关9,12,14,25兴 for thewhole range of error rates. We also show the relation between the proposed protocol and the advantage distillation
protocol, i.e., the B step of Gottesman and Lo 关16兴 共Remark
4兲. We also show the relation between the proposed QKD
protocol and Vollbrecht and Vestraete’s EDP. As a result, it
turns out that there does not seem to be any EDP that corresponds to our proposed protocol 共Remark 5兲.
The rest of this paper is organized as follows. Section II
proposes a two-way IR protocol. Section III presents the key
rate formula of the QKD protocol that uses our proposed IR
protocol. We present a proof of the key rate formula in the
supplementary material 关27兴, because the proof is involved
and techniques used in the proof are not new. Section IV
presents the key rate formula as a function of error rate.

II. TWO-WAY INFORMATION RECONCILIATIONPROTOCOL

We propose an IR protocol that uses two-way classicalcommunication 共called a two-way IR protocol after this兲 inthis section. When Alice and Bob have correlated classicalsequences, x , y 苸 F2n
2 , the purpose of IR protocols for Aliceand Bob is to share the same classical sequence by exchanging messages over a public authenticated channel, where F2
is a field of order 2. Here, we assume that the pair of sequences 共x , y兲 is independently identically distributed 共i.i.d兲
according to a joint probability distribution PXY on F2 ⫻ F2.
Let us review some notations for a linear code to describe
our IR protocol. An 关n , n − m兴 classical linear code Cn,m is an
共n − m兲-dimensional linear subspace of Fn2. Then a parity
check matrix M Cn,m of code Cn,m is an m ⫻ n matrix of rank mwith 0,1 entries such that cM CTn,m = 0 for any c 苸 Cn,m, where
M CTn,m is the transpose matrix of M Cn,m. A decoder gCn,m ofcode Cn,m is a map from a syndrome t 苸 Fm
2 to an error e苸 D共t兲, where D共t兲 ª 兵e 苸 Fn2 兩 eM CTn,m = t其 is the set of errors
whose syndromes are t. After this, we will assume that a

linear code is implicitly specified with a parity check matrix
and a decoder.
We need to define some auxiliary random variables to
describe our IR protocol. Let ␰1 : F22 → F2 be a function defined as ␰1共a1 , a2兲 ª a1 + a2 for a1 , a2 苸 F2, and let ␰2 : F22→ F2 be a function defined as ␰2共a , 0兲 ª a and ␰2共a , 1兲 ª 0
for a 苸 F2. For a pair of joint random variables(共X1 , Y 1兲 , 共X2 , Y 2兲) with a distribution P2XY , define randomvariables U1 ª ␰1共X1 , X2兲, V1 ª ␰1共Y 1 , Y 2兲, and W1 ª U1 + V1.
Furthermore, define random variables U2 ª ␰2共X2 , W1兲, V2ª ␰2共Y 2 , W1兲 and W2 ª U2 + V2. For the pair of sequences x= 共x11 , x12 , . . . , xn1 , xn2兲 and y = 共y 11 , y 12 , . . . , y n1 , y n2兲, which
is distributed according to the product distribution P2n
XY , let u,v, and w be 2n-bit sequences such thatui1 ª ␰1共xi1,xi2兲,vi1 ª ␰1共y i1,y i2兲,

wi1 ª ui1 + vi1

ui2 ª ␰2共xi2,wi1兲,vi2 ª ␰2共y i2,wi1兲,

wi2 ª ui2 + vi2

andfor 1 艋 i 艋 n. Then, the pair 共u , v兲 is distributed according tonthe distribution PU, and the discrepancy w between u
1U2V1V2n. For
and v is distributed according to the distribution PW
1W2
sequence w, let Tb ª 兵j 兩 1 艋 j 艋 n , w j1 = b其 be the set of indices of blocks such that the parities of the discrepancies areb 苸 兵0 , 1其. For the subsequence u2 ª 共u12 , . . . , un2兲, let u2,Tb
be the subsequence that consists of the ith bit of u2 such thati 苸 T b.
The first step of well-known methods 关16,20,23兴 of twoway processing within the key distillation context is to classify blocks of length 2 according to the parity wi1 of thediscrepancies in each block. In conventional two-way processing of key distillation protocols 关16,20兴, the so-calledadvantage distillation protocols, Alice sends the parity sequence u1 ª 共u11 , . . . , un1兲 to Bob so that he can identify theparity sequence w1 ª 共w11 , . . . , wn1兲 of the discrepancies.
Then, Alice and Bob discard u1 and v1 ª 共v11 , . . . , vn1兲, respectively, because u1 is revealed to Eve. Furthermore, Aliceand Bob discard the second bit of the ith block, if the parityof the discrepancies is 1, i.e., i 苸 T1. Finally, Alice and Bob
undertake an error correction procedure for the subsequences
共u2,T0 , v2,T0兲. More precisely, Alice sends the syndrome t2ª u2,T0M CTn ,m for the prescribed 关n0 , m0兴 linear code, and0 0then Bob decodes ŵ2,T0 ª gCn ,m 共t2 + v2,T0M CTn ,m 兲 and obtains
0 0
0 0
v2,T0 + ŵ2,T0, where n0 ª 兩T0兩 is the cardinality of the set T0.
Our two-way IR protocol, which is based on Vollbrecht
and Vestraete’s idea of two-way EDP 关23兴, is quite similar tothe previously described two-way processing except for one
significant change. As is usual in information theory, if weallow negligible error probability, Alice does not need tosend the parity sequence u1 to Bob to identify parity sequence w1. More precisely, Bob can decode w1 with negligible decoding error probability if Alice sends a syndrome
t1 ª u1M CTn,m for a linear code such that the rate is m / n⯝ H共PW1兲 共关28兴, Corollary 2兲. Since Eve’s available information from syndrome t1 is often much smaller than that fromthe sequence u1 itself, our IR protocol is more efficient than
the above-mentioned two-way processing in most cases, as

032312-2

PHYSICAL REVIEW A 76, 032312 共2007兲

KEY RATE OF QUANTUM KEY DISTRIBUTION WITH…

will be discussed in Sec. IV. Our IR protocol is formally
executed as follows, where the tilde and caret on a sequence,a set, or a number indicate that they are guessed versions of
those without these diacritics. Note that the inputs of the IR
protocol are Alice’s bit sequence x and Bob’s bit sequence y,and the outputs of the IR protocol are a sequence û guessedby Alice and a sequence ũ guessed by Bob.
共i兲 Alice locally computes u1 and Bob does the same forv 1.
共ii兲 For a prescribed 关n , n − m兴 linear code Cn,m, Alicesends syndrome t1 = u1M CTn,m to Bob.
共iii兲 Bob decodes ŵ1 ª gCn,m共t1 + v1M CTn,m兲 and sends ŵ1 to
Alice.
共iv兲 Alice computes û2. If the number n̂0 ª 兩兵i 兩 ŵi1 = 0其兩 ofblocks such that the guessed parity ŵi1 of the discrepancies is
0 does not satisfy nគ 0 艋 n̂0 艋 n̄0 for prescribed integers nគ 0 andn̄0, then Bob randomly guesses û2,Tˆ 0. Otherwise, Alice sends
the syndrome t̂2 ª û2,Tˆ 0M Cn̂ ,m̂ for a prescribed 关n̂0 , n̂0 − m̂0兴
0 0linear code Cn̂0,m̂0.
共v兲 Bob decodes w̃2,Tˆ 0 ª gCn̂ ,m̂ 共t̂2 + v̂2,Tˆ 0M CTn̂ ,m̂ 兲, and ob0 0
0 0
tains ũ2,Tˆ 0 ª v̂2,Tˆ 0 + w̃2,Tˆ 0.
Note that û2,Tˆ 1 and v̂2,Tˆ 1 are set to all 0’s in our protocol,
which is mathematically equivalent to discarding them.
According to the universal channel coding theorem for the
linear code 共关28兴, Corollary 2兲, rates m / n = H共PW1兲 + ␦ andm̂0 / n̂0 = H共PW2兩W1=0兲 + ␦ for small ␦ ⬎ 0 are sufficient for Bob
to decode w1 and w2,T0 with negligible decoding error probability. Furthermore, we set nគ 0 ª n关PW1共0兲 − ␦兴 and n̄0ª n关PW1共1兲 + ␦兴 to satisfy the condition nគ 0 艋 n̂0 艋 n̄0, in step
共iv兲 with high probability.
Remark 1. Since we cannot estimate the probability distribution of error exactly in QKD protocols and the actual
distribution fluctuates around the estimated error distribution,
universality of codes is required. Even though the distribution of errors in the QKD protocols are not necessarily i.i.d.,
it is sufficient to consider a universality condition on codes
for the i.i.d. case. More precisely, it is sufficient to use alinear code such that the decoding error probability of thelinear code is universally small for any binary symmetricchannel whose crossover probability is close to the estimatederror rate. Such observations were first pointed out by Hamada 关29兴. Efficiently decodeable linear codes such as the
low-density parity check matrix code 关30兴 and the turbo code关31兴 satisfy this condition.

bipartite state ␳ANBN on an N pair of bipartite systems 共HA丢 HB兲 丢 N, that ␳ANBN is invariant under the permutation of thesystems,1 and that Eve can access TrANBN共␳ANBNEN兲 for a purification ␳ANBNEN of ␳ANBN 共see also 关13,14兴兲. The specificform of ␳ANBN depends on which scheme Alice and Bob employ to transmit a binary sequence, noise in the channel, andEve’s attack. From 共关15兴, Lemma 4.2.2兲, without loss of generality, we can assume that purification ␳ANBNEN lies on thesymmetric subspace of 共HA 丢 HB 丢 HE兲 丢 N, because any purification can be transformed into another purification using
Eve’s local operation.
Before the protocol is started, Alice and Bob discard thelast k subsystems HA丢 k 丢 HB丢 k for technical reasons of security proof. More specifically, k subsystems are discarded toapply the de Finetti style representation theorem 共关15兴, Theorem 4.3.2兲 共see also 关32兴兲 in the security proof. Therefore, we
set N ª 2n + m + k. Then, Alice and Bob conduct the protocol
for the state, ␳A2n+mB2n+m ª Trk共␳ANBN兲, where k is the numberof discarded systems, m is the number of systems for parameter estimation, and 2n is the number of systems that areused for key distillation.
First, Alice and Bob undertake the following parameter
estimation protocol for the last m subsystems of the state␳A2n+mB2n+m. The parameter estimation protocol is conducted
to estimate the number of discrepancies between Alice andBob’s raw keys, and the amount of information that Eve has
gained by eavesdropping.
共i兲 Alice and Bob carry out a measurement that corresponds to a positive-operator-valued measure 共POVM兲, Mª 兵M a其a苸A, for each system HA 丢 HB, where A is the set ofmeasurement outcomes. The specific form of M depends onwhich scheme we use.
共ii兲 If the type Pa of the measurement outcomes a= 共a1 , . . . , am兲 satisfies Pa 苸 Q for a prescribed set Q, theprotocol outputs the type Q ª Pa, and Alice and Bob conduct
the key distillation protocol according to Q, where the typeof sequence a = 共a1 , . . . , am兲 is the frequency distribution defined by
Pa共a兲 ªfor a 苸 A

共for more details on the type, see 关关33兴, Chap. 11兴兲. Otherwise, it outputs “abort.”
It is convenient to describe the parameter estimation protocol using a completely positive 共CP兲 map as follows. Let
M 丢 m ª 兵M a其a苸Am be a product POVM on 共HA 丢 HB兲 丢 m,where M a = M a1 丢 ¯ 丢 M am. Then, we can define a CP map
EQ byIII. SECURITY OF QKD AND KEY RATEThis section presents the asymptotic key rate of a QKD
protocol that employs the IR protocol proposed in Sec. II.
The asymptotic key rate is derived by the security proof
method 关13–15兴.
We implement a prepare and measure scheme in a practical QKD protocol. However, when we analyze the securityof a QKD protocol, it is usually more convenient to consider
its entanglement-based version. Without compromising security, we can assume that Alice and Bob’s raw keys and bit
sequences for error estimation are obtained by measuring a

円兵i兩1 艋 i 艋 m,ai = a其円m

E Q: ␳ m 哫兺 TrM a␳m ,

共1兲

n
a苸TQ
共A兲

which maps the density operator to the probability such thatm
共A兲 isthe parameter estimation protocol outputs Q, where TQma set of all sequences on A with type Q.
1

By applying the random permutation after the transmission phase
of QKD protocols, we can assume that Alice’s and Bob’s bit sequences are invariant under the permutation without any compromise of the security.

032312-3

PHYSICAL REVIEW A 76, 032312 共2007兲

WATANABE et al.

When the output of the parameter estimation protocol is
Q 苸 Q, Alice, Bob, and Eve’s tripartite state is given byQ

␳A2nB2nEN ª

The QKD protocol is said to be ␧ secure 共in the sense of theaverage over the outputs of the parameter estimation protocol兲 if

1⫻ 共idA2nB2n 丢 EQ 丢 idEN兲共␳A2n+mB2n+mEN兲,
PPE共Q兲

1

兺 PPE共Q兲 2 储␳SQ S CE − ␳SQ,mix
S 丢 ␳CE 储 艋 ␧,
Q苸Q
A B

where PPE共Q兲 is the probability that the parameter estimation
protocol outputs Q, and id denotes the identity map on eachsystem.
Alice and Bob apply a measurement MXY ª 兵M x
丢 M y 其共x,y兲苸F ⫻F on HA 丢 HB to the remaining 2n systems to2
2
obtain classical data 共raw keys兲. Then, Alice and Bob’s mea2nsurement results, 共x , y兲 苸 F2n
2 ⫻ F2 , and Eve’s available information is described by a 兵ccq其 state2
Q

Q

丢 2n
␳XYEN ª 共EXY
丢 idEN兲共␳A2nB2nEN兲,

where we introduce a CP map EXY that describes the measurement procedure for convenience.
According to output Q of the parameter estimation protocol, Alice and Bob decide the parameters of the IR protocol:
the rate R共Q兲 ª m / n of the linear code Cn,m, the numbersnគ 0共Q兲 and n̄0共Q兲 that are used in step 共iv兲, and the rate
R0共Q兲 ª m0 / n0 of the linear code Cn0,m0 for nគ 0共Q兲 艋 n0
艋 n̄0共Q兲. Furthermore, Alice and Bob also decide the lengthᐉ共Q兲 of the finally distilled key according to Q. According to
the determined parameters, a final secure key pair is distilled
as follows.
共i兲 Alice and Bob undertake the two-way IR protocol inSec. II, and Alice obtains û and Bob obtains ũ.
共ii兲 Alice and Bob carry out a privacy amplification protocol to distill a key pair 共sA , sB兲 such that Eve has little
information about it. Alice first randomly chooses a hash
ᐉ共Q兲from a family of two-universal
function f : F2n
2 → 兵0 , 1其hash functions 共refer to 共关15兴, Definition 5.2.1兲 for a formal
definition of a family of two-universal hash functions兲, andsends the choice of f to Bob over the public channel. Then,
Alice’s distilled key is sA = f共û兲 and Bob’s distilled key is
sB = f共ũ兲.
The distilled key pair and Eve’s available information canbe described by a 兵cccq其 state, ␳SQ S CEN, where the classical
A B

system C consists of random variables 共T1 , T̂2 , Ŵ1兲 that describe the exchanged messages 共t1 , t̂2 , ŵ1兲 in the IR protocol
and a random variable F that describes the choice of the hashfunction in the PA protocol. To define the security of the
distilled key pair 共SA , SB兲, we use the universally composable
security definition 关34,35兴, which is defined by the trace distance between the actual key pair and the ideal key pair. We
cannot state security in QKD protocols in the sense that thedistilled key pair 共SA , SB兲 is secure for a particular output Qof the parameter estimation protocol, because there is a slightpossibility that the parameter estimation protocol will not
output “abort” even though Eve has so much information.
2
A 兵ccq其 state is a tripartite state such that the first and second
systems are classical and the third system is quantum. See 关39兴 fordetails of this notation.

N

A B

N

共2兲

ª 兺s苸SQ共1 / 兩SQ兩兲兩s , s典具s , s兩 is the uniformly diswhere ␳SQ,mix
ASB
tributed key on the key space SQ ª 兵0 , 1其ᐉ共Q兲.
To state the relation between the security and theasymptotic key rate of the previously mentioned QKD protocol, define⌫共Q兲 ª 兵␴AB兩PA␴AB = Q其as the set of two-qubit density operators that are compatible
with output Q of the parameter estimation protocol, where
PA␴AB denotes the probability distribution of the outcomeswhen measuring ␴AB with POVM M, i.e., PA␴AB共a兲
ª Tr共M a␴AB兲. For a purification ␴ABE of a density operator
丢2丢2
丢2␴AB 苸 ⌫共Q兲, let ␴X1X2Y 1Y 2E1E2 ª 共EXY
丢 idE 兲共␴ABE兲 be a 兵ccq其state that consists of two-bit pairs (共X1 , X2兲 , 共Y 1 , Y 2兲) and environment systems E1 , E2. By using functions ␰1 and ␰2, define random variables 共U1 , U2 , W1 , W2兲 for the pair of bits
(共X1 , X2兲 , 共Y 1 , Y 2兲) in the same way as in Sec. II. Then, let
␴U1U2W1E1E2 and ␴U1U2W1U1E1E2 be density operators that respectively describe the classical random variables
共U1 , U2 , W1兲 and 共U1 , U2 , W1 , U1兲 with the environment systems E1 , E2.
Theorem 1. For Q 苸 Q, i.e., the output of the parameter
estimation protocol such that the QKD protocol does notabort, let ᐉ共Q兲 / 2n be the key rate of the protocol. For any␧ ⬎ 0, if the key rate satisfies
ᐉ共Q兲 1
min max关H␴共U1U2兩W1E1E2兲 − H共PW1兲⬍
2 ␴AB苸⌫共Q兲
2n− PW1共0兲H共PW2兩W1=0兲,H␴共U2兩W1U1E1E2兲
− PW1共0兲H共PW2兩W1=0兲兴,

共3兲then there exists a protocol that is ␧ secure in the sense of
Eq. 共2兲 for sufficiently large n, where H␳共A 兩 B兲 ª H共␳AB兲− H共␳B兲 is the conditional von Neumann entropy 关36兴, andH共P兲 is the Shannon entropy 关33兴.
The meaning of the two arguments of the maximum in
Eq. 共3兲 should be noted. The first argument states that the key
rate is given by the difference between Eve’s ambiguity
H␴共U1U2 兩 W1E1E2兲 about Alice’s reconciled key and theamount H共PW1兲 + PW1共0兲H共PW2兩W1=0兲 of information leakedin the IR protocol. On the other hand, since information
leaked from the syndrome t1 = u1M CTn,m cannot be more than
u1 itself, we can evaluate the key rate under the condition
that Eve can access u1 itself, i.e., Eve’s ambiguity
H␴共U2 兩 W1U1E1E2兲 about Alice’s reconciled key and theamount PW1共0兲H共PW2兩W1=0兲 of information leaked in the IR
protocol. If either of them is omitted, the key rate is underestimated, as will be discussed in Section IV.

032312-4

PHYSICAL REVIEW A 76, 032312 共2007兲

KEY RATE OF QUANTUM KEY DISTRIBUTION WITH…

Theorem 1 is proved by demonstrating the above intuition
formally, where we use a security proof method 关13–15兴.
More precisely, we use the techniques of privacy amplification and minimum entropy, and the de Finetti style representation theorem and the property of symmetric states 共see
关15兴兲. Since the proof is involved and techniques used in the
proof are not new, we give the proof for Theorem 2 in the
supplementary material 关27兴.

Key rate1

Proposed
Vollbrecht et al.
B ste p
One way

0.8
0.6
0.4
0.2
0.025 0.05 0.075

Here, we analyze the asymptotic key rate formula inTheorem 1. More precisely, we derive a specific form of the
key rate formulas as functions of the error rates for the sixstate 关5兴 and BB84 protocols 关4兴.
Before analyzing the key rate, let us define some notations. For x , z 苸 F2, let兩␺共x,z兲典 ª1

冑2 关兩0典兩0 + x典 + 共− 1兲 兩1典兩1 + x典兴
z

be the Bell states on the two-qubit system HA 丢 HB. For aprobability distribution PXZ on F2 ⫻ F2, a state of the form

兺 PXZ共x,z兲兩␺共x,z兲典具␺共x,z兲兩

is called a Bell diagonal state. We occasionally abbreviate
PXZ共x , z兲 as pxz.
Theorem 2. For a Bell diagonal state ␴AB= 兺x,z苸F2 PXZ共x , z兲兩␺共x , z兲典具␺共x , z兲兩, we have1
max关H␴共U1U2兩W1E1E2兲 − H共PW1兲 − PW1共0兲H共PW2兩W1=0兲,2

冋= max 1 − H共PXZ兲 +PX¯ 共0兲
2

册PX¯ 共1兲
2

h冉

冊

p00p10 + p01p11,
共p00 + p01兲共p10 + p11兲⬘ 兲兴 ,
关1 − H共PXZ

共4兲

where h共p兲 ª −p log p − 共1 − p兲log共1 − p兲 is the binary entropy
function,
PX¯ 共0兲 ª 共p00 + p01兲2 + 共p10 + p11兲2 ,PX¯ 共1兲 ª 2共p00 + p01兲共p10 + p11兲,and⬘ 共0,0兲 ª
PXZ

2
2
+ p01
p00
,
共p00 + p01兲2 + 共p10 + p11兲2⬘ 共1,0兲 ª
PXZ

2p00p01,
共p00 + p01兲2 + 共p10 + p11兲2⬘ 共0,1兲 ª
PXZ

2
2
+ p11
p10
,
共p00 + p01兲2 + 共p10 + p11兲20.125 0.15

FIG. 1. 共Color online兲 Comparison of the key rates of the sixstate protocols. “Proposed” is the key rate of the six-state protocolthat uses the proposed IR protocol. “Vollbrecht et al.” is the key rateof the two-way six-state protocol of 关18,25兴. “B step” is the key rateof the two-way six-state protocol of 关16兴. “One way” is the key rateof the one-way six-state protocol with noisy preprocessing 关14兴. It
should be noted that the key rates of two-way six-state protocols of关15–17兴 are slightly higher than that of the proposed protocol for
error rates higher than about 15%. For error rates higher than 15%,
the best protocol among known protocols is the protocol presented
by Renner 关15兴, which involves the advantage distillation and thenoisy preprocessing proposed by Renner et al. 关13,14兴.

x,z苸F2

H␴共U2兩W1U1E1E2兲 − PW1共0兲H共PW2兩W1=0兲兴

0.1

Error rate

IV. ANALYSIS OF KEY RATE

⬘ 共1,1兲 ª
PXZ

2p10p11.
共p00 + p01兲2 + 共p10 + p11兲2

The theorem is proved by a straightforward calculation.
Thus, the proof is presented in the supplementary material
关27兴.
The six-state protocol 关5兴 uses three different bases defined by the z basis 兵兩0z典 , 兩1z典其, x basis 兵1 / 冑2共兩0z典 ± 兩1z典兲其, andy basis 兵1 / 冑2共兩0z典 ± i兩1z典兲其. When Alice and Bob obtain anerror rate e, the set ⌫共Q兲 consists of states whose Bell diagonal entries p00 , p10 , p01 , p11 satisfy the conditions p10 + p11= e, p01 + p11 = e, and p01 + p10 = e. Together with the normalization condition, we find p00 = 1 − 3e / 2 and p10 = p01 = p11= e / 2. Since it is sufficient only to minimize over the Belldiagonal states in Eq. 共3兲 共see the supplementary material关27兴 for a proof兲, the key rate of the six-state protocol for theerror rate e is given by substituting p00 = 1 − 3e / 2 and p10= p01 = p11 = e / 2 into Eq. 共4兲. The key rate of the six-state
protocol that uses the proposed IR protocol is plotted in Fig.
1.
The BB84 protocol is similar to the six-state protocol, butuses only the z basis and the x basis to transmit a bit sequence. Thus, we obtain only two conditions on the four
coefficients p00 , p10 , p01 , p11, and the set ⌫共Q兲 consists ofstates whose Bell diagonal entries satisfy the conditions p10+ p11 = e and p01 + p11 = e. The resulting candidates for Belldiagonal states in ⌫共Q兲 have coefficients p00 = 1 − 2e + p11,
p10 = p01 = e − p11, and p11 苸 关0 , e兴, and we have to minimize
the key rate formula of Eq. 共4兲 over the free parameter p11
苸 关0 , e兴. The key rate of the BB84 protocol that uses the
proposed IR protocol is plotted in Fig. 2.
Remark 2. By using the chain rule of von Neumann entropy, we can rewrite the left-hand side 共LHS兲 of Eq. 共4兲 as

032312-5

PHYSICAL REVIEW A 76, 032312 共2007兲

WATANABE et al.

Key rate1

Proposed
Vollbrecht et al.
B ste p
One way

0.8
0.6
0.4
0.2
0.02

0.04

0.06

0.08

0.1

0.12

Error rate
FIG. 2. 共Color online兲 Comparison of the key rates of the BB84
protocols. “Proposed” is the key rate of the BB84 protocol that uses
the proposed IR protocol. “Vollbrecht et al.” is the key rate of thetwo-way BB84 protocol of 关18,25兴. “B step” is the key rate of thetwo-way BB84 protocol of 关16兴. “One way” is the key rate of theone-way BB84 protocol with noisy preprocessing 关14兴.

1
兵max关H␴共U1兩W1E1E2兲 − H共PW1兲,0兴 + H␴共U2兩W1U1E1E2兲
2− PW1共0兲H共PW2兩W1=0兲其.

共5兲

We can interpret this formula as follows. If Bob’s ambiguity
H共PW1兲 about bit U1, i.e., the amount of transmitted syndrome per bit, is smaller than Eve’s ambiguity
H␴共U1 兩 W1E1E2兲 about bit U1, then Eve cannot decode sequence U1 关37,38兴, and there exists some remaining ambiguity about bit U1 for Eve. We can thus distill some secure key
from bit U1. On the other hand, if Bob’s ambiguity H共PW1兲
about bit U1, i.e., the amount of transmitted syndrome per
bit, is larger than Eve’s ambiguity H␴共U1 兩 W1E1E2兲 about U1,
then Eve might be able to decode sequence U1 from her sideinformation W1, E1, E2, and the transmitted syndrome关37,38兴. Thus, there exists the possibility that Eve can completely know bit U1, and we can distill no secure key frombit U1, because we have to consider the worst case in a
cryptographic scenario. Consequently, sending the hashedversion 共syndrome兲 of sequence U1 instead of U1 itself is notalways effective, and the slopes of the key rate curves in
Figs. 1 and 2 change when Eve becomes able to decode U1.
The second and third terms of Eq. 共5兲 are the same as the
key rate formula of the protocol that uses Gottesman andLo’s B step 关16兴 followed by error correction and privacy
amplification. Even though Alice sends the sequence U1 itself instead of its hashed version in the B step, the key rate of
the protocol with the B step is equal to that of the proposed
protocol for high error rates, because Eve can decode sequence U1 from her side information and the transmitted
syndrome.
Remark 3. The yield of Vollbrecht and Vestraete’s EDP
关23兴 and the key rate of the QKD protocols 关18,25兴 are givenby
1 − H共PXZ兲 +PX¯ 共1兲
4

再冉
h

冊 冉

p01
p11
+h
p00 + p01
p10 + p11

冊冎

.
共6兲

We can find by the concavity of the binary entropy functionthat the first argument in the maximum of the RHS of Eq. 共4兲
is larger than the value in Eq. 共6兲. To explain why the key
rate of the proposed protocol is higher than that of 关18,25兴,
we need to review the EDP 关23兴 by using the notations in
Sec. II. Assume that Alice and Bob share Bell diagonal states
丢 2n␴AB. First, Alice and Bob divide 2n pairs into n blocks oflength 2, and locally carry out a controlled-NOT CNOT operation on each block, where the 2ith pair is the source and the
共2i − 1兲th pair is the target. Then, Alice and Bob undertakethe breeding protocol 关10兴 to guess bit-flip errors in the 共2i− 1兲th pair for all i. The guessed bit-flip errors can be described by a sequence ŵ1. Note that two-way communication
is used in this step. According to sequence ŵ1, Alice and Bobclassify indices of blocks into two sets T̂0 and T̂1. For acollection of 2ith pairs such that i 苸 T̂0, Alice and Bob conduct the breeding protocol to correct bit-flip errors. For acollection of 2ith pairs such that i 苸 T̂1, Alice and Bob perform measurements in the 兵兩0z典 , 兩1z典其 basis, and obtain measurement results x2,Tˆ 1 and y2,Tˆ 1. Alice sends x2,Tˆ 1 to Bob.
Alice and Bob correct the phase errors for the remaining
pairs by using information T̂0 and T̂1 and bit-flip error
x2,Tˆ 1 + y2,Tˆ 1.
If we convert this EDP into a QKD protocol, the difference between that QKD protocol and ours is as follows. In
the protocol converted from 关23兴, after step 共iii兲, Alice reveals the sequence x2,Tˆ 1, which consists of the second bit xi2of the ith block such that the parity of discrepancies ŵi1 is 1.
However, Alice discards x2,Tˆ 1 in the proposed IR protocol ofSec. II. Since the sequence x2,Tˆ 1 has some correlation to thesequence u1 from the viewpoint of Eve, Alice should notreveal x2,Tˆ 1 to achieve a higher key rate.
In the EDP context, on the other hand, since the bit flip
error x2,Tˆ 1 + y2,Tˆ 1 has some correlation to the phase-flip errors
in the 共2i − 1兲th pair with i 苸 T̂1, Alice should send the measurement results x2,Tˆ 1 to Bob. If Alice discards measurement
results x2,Tˆ 1 without telling Bob what the result is, then theyield of the resulting EDP is worse than Eq. 共6兲. Consequently, there seems to be no correspondence between the
EDP and our proposed classical processing.

V. CONCLUSION

We proposed an information reconciliation protocol thatuses two-way classical communication. For the BB84 andsix-state protocols, the key rates of QKD protocols that use
our information reconciliation protocol are higher than previously known protocols for a wide range of error rates. Furthermore, we showed the relation between the proposed protocol and the B step of 关16兴 共Remark 2兲. We clarified why the
key rate of our protocol is higher than those of 关18,23,25兴
共Remark 3兲, and found that there does not seem to be any
EDP that corresponds to our proposed QKD protocol.

032312-6

PHYSICAL REVIEW A 76, 032312 共2007兲

KEY RATE OF QUANTUM KEY DISTRIBUTION WITH…
ACKNOWLEDGMENTS

We would like to thank Dr. Manabu Hagiwara, Dr. Kentaro Imafuku, Professor Hideki Imai, Dr. Mitsugu Iwamoto,Dr. Takayuki Miyadera, Dr. Jun Muramatsu, Professor Hi-

roshi Nagaoka, Dr. Tomohiro Ogawa, and Professor Stefan
Wolf for valuable discussions. This research was also partly
supported by the Japan Society for the Promotion of Science
under Grants-in-Aid No. 18760266 and No. 00197137.

关1兴 G. Brassard and L. Salvail, in Advances of Cryptology—
EUROCRYPT’93, edited by T. Helleseth, Lecture Notes in
Computer Science, Vol. 765 共Springer, Berlin, 1994兲, pp. 410–
423.
关2兴 C. H. Bennett, G. Brassard, and J. M. Robert, SIAM J. Comput. 17, 210 共1988兲.
关3兴 C. H. Bennett, G. Brassard, C. Crepeau, and U. Maurer, IEEE
Trans. Inf. Theory 41, 1915 共1995兲.
关4兴 C. H. Bennett and G. Brassard, in Proceedings IEEE International Conference on Computers, Systems and Signal Processing, Bangalore, India, 1984 共IEEE, New York, 1984兲, pp. 175–179.
关5兴 D. Bruß, Phys. Rev. Lett. 81, 3018 共1998兲.
关6兴 E. Biham, M. Boyer, P. O. Boykin, T. Mor, and V. Roychowdhury, in Proceedings on the 32nd Annual ACM Symposium of the Theory of Computing, 2000 共unpublished兲, pp.
715–724.
关7兴 E. Biham, M. Boyer, P. O. Boykin, T. Mor, and V. Roychowdhury, J. Cryptology 19, 381 共2006兲.
关8兴 D. Mayers, J. ACM 48, 351 共2001兲.
关9兴 P. W. Shor and J. Preskill, Phys. Rev. Lett. 85, 441 共2000兲.
关10兴 C. H. Bennett, G. Brassard, S. Popescu, B. Schumacher, J. A.
Smolin, and W. K. Wootters, Phys. Rev. Lett. 76, 722 共1996兲.
关11兴 C. H. Bennett, D. P. DiVincenzo, J. A. Smolin, and W. K.
Wootters, Phys. Rev. A 54, 3824 共1996兲.
关12兴 H. K. Lo, Quantum Inf. Comput. 1, 81 共2001兲.
关13兴 B. Kraus, N. Gisin, and R. Renner, Phys. Rev. Lett. 95,
080501 共2005兲.
关14兴 R. Renner, N. Gisin, and B. Kraus, Phys. Rev. A 72, 012332
共2005兲.
关15兴 R. Renner, Ph.D thesis, Dipl. Phys. ETH, Switzerland, 2005,
e-print arXiv:quant-ph/0512258.
关16兴 D. Gottesman and H. K. Lo, IEEE Trans. Inf. Theory 49, 457
共2003兲.
关17兴 H. F. Chau, Phys. Rev. A 66, 060302共R兲 共2002兲.
关18兴 X. Ma, C. H. F. Fung, F. Dupuis, K. Chen, K. Tamaki, and H.
K. Lo, Phys. Rev. A 74, 032330 共2006兲.
关19兴 B. Kraus, C. Branciard, and R. Renner, Phys. Rev. A 75,
012316 共2007兲.
关20兴 U. Maurer, IEEE Trans. Inf. Theory 39, 733 共1993兲.

关21兴 J. Bae and A. Acín, Phys. Rev. A 75, 012334 共2007兲.
关22兴 A. Acín, J. Bae, E. Bagan, M. Baig, L. Masanes, and R.
Munöz-Tapia, Phys. Rev. A 73, 012327 共2006兲.
关23兴 Karl-Gerd H. Vollbrecht and F. Vestraete, Phys. Rev. A 71,
062325 共2005兲.
关24兴 H. K. Lo, New J. Phys. 5, 36 共2003兲.
关25兴 S. Watanabe, R. Matsumoto, and T. Uyematsu, in Proceedingsof AQIS 2006, Beijing, China, 2006 共unpublished兲, pp. 11–12.
关26兴 M. Christandl, A. Ekert, M. Horodecki, P. Horodecki, J. Oppenheim, and R. Renner, in Proceedings of the Fourth Theoryof Cryptography Conference, Amsterdam, The Netherlands,
2007, edited by P. Vadhan, Lecture Notes in Computer Science, Vol. 4392 共Springer, Berlin, 2007兲, pp. 456–478.
关27兴 See EPAPS Document No. E-PLRAAN-76-169708 for the
proofs of Theorems 1 and 2. For more information on EPAPS,
see http://www.aip.org/pubservs/epaps.html.
关28兴 I. Csiszár, IEEE Trans. Inf. Theory 28, 585 共1982兲.
关29兴 M. Hamada, J. Phys. A 37, 8303 共2004兲.
关30兴 R. G. Gallager, Low Density Parity Check Codes 共MIT Press,
Cambridge, MA, 1963兲.
关31兴 C. Berrou and A. Glavieux, IEEE Trans. Commun. 44, 1261
共1996兲.
关32兴 R. Renner, e-print arXiv:quant-ph/0703069.
关33兴 T. M. Cover and J. A. Thomas, Elements of Information
Theory, 2nd ed. 共John Wiley & Sons, New York, 2006兲.
关34兴 M. Ben-Or, M. Horodecki, D. W. Leung, D. Mayers, and J.
Oppenheim, in Second Theory of Cryptography Conference
TCC, Cambridge, MA, 2005, edited by J. Kilian, Lecture Notes
in Computer Science, Vol. 3378 共Springer, Berlin, 2005兲, pp.
386–406.
关35兴 R. Renner and R. Konig, in Second Theory of Cryptography
Conference TCC, Cambridge, MA 2005 共Ref. 关34兴兲, pp. 407–425.
关36兴 M. Hayashi, Quantum Information: An Introduction 共Springer,
Berlin, 2006兲.
关37兴 D. Slepian and J. K. Wolf, IEEE Trans. Inf. Theory 19, 471
共1973兲.
关38兴 I. Devetak and A. Winter, Phys. Rev. A 68, 042301 共2003兲.
关39兴 I. Devetak and A. Winter, Proc. R. Soc. London, Ser. A 461,
207 共2004兲.

032312-7