ńņš. 2 |

R(X |Y ) ā¤ H (X |Y ). (2.45)

References

1. Carter, L., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci. 18(2),

143ā“154 (1979) 15

2. Cover, T.M., Thomas, J.A.: Elements of Information Theory. Wiley-Interscience (1991). URL

http://www.amazon.ca/exec/obidos/redirect?tag=citeulike09ā“20&path=ASIN/04710625

96 19

3. National Institute of Standards and Technology: FIPS PUB 186ā“2: Digital Signature Standard

(DSS). National Institute for Standards and Technology, Gaithersburg, MD, USA (2000). URL

http://www.itl.nist.gov/ļ¬pspubs/ļ¬p186ā“2.pdf 14

4. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge

University Press, Cambridge (2000). URL http://www.amazon.ca/exec/obidos/redirect?tag=

citeulike09ā“20%&path=ASIN/0521635039 3, 5, 9, 10

5. RĀ“ nyi, A.: On measures of information and entropy. Proceedings of the 4th Berkeley Sympo-

e

sium on Mathematics, Statistics and Probability, pp. 547ā“561 (1961) 20

6. Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-

key cryptosystems. Commun. ACM 21(2), 120ā“126 (1978) 14

7. Shannon, C.E.: A mathematical theory of communication. The Bell System Technical Jour-

nal 27, 379ā“423, 623ā“656 (1948). URL http://cm.bell-labs.com/cm/ms/what/shannonday/

shannon1948.pdf 19

8. Stinson, D.R.: Universal hashing and authentication codes. In: J. Feigenbaum (ed.) CRYPTO,

Lecture Notes in Computer Science, Vol. 576, pp. 74ā“85. Springer, Heidelberg (1991) 15

9. Wegman, M.N., Carter, L.: New hash functions and their use in authentication and set equality.

J. Comput. Syst. Sci. 22(3), 265ā“279 (1981) 14, 15, 16, 17, 18, 19

10. Wootters, W.K., Zurek, W.H.: A single quantum cannot be cloned. Nature 299(5886), 802ā“803

(1982). DOI 10.1038/299802a0. URL http://dx.doi.org/10.1038/299802a0 13

Chapter 3

Quantum Key Distribution

M. Pivk

In this chapter a complete QKD protocol is presented, starting from the transmission

via the quantum channel up to the communication over the public channel. The

protocol described here is the BB84 protocol, named after Bennett and Brassard

[5]. There are other protocols like the B92 protocol [3], the six-state protocol [8], the

SARG protocol [19] and the Ekert protocol [10], which are not discussed here. We

are focusing on BB84, the most known QKD protocol. In Fig. 3.1 you see an abstract

sequence diagram of BB84. ka is the pre-shared secret needed for authentication and

K is the ļ¬nal key generated after BB84 is executed. We begin with the ļ¬rst stage,

the transmission of the photons, which is the physical representation of the qubits,

from Alice to Bob. This phase of the protocol is discussed in detail in Sect. 3.1.

Afterward the communication switches to the public channel (Sect. 3.2).

There, the ļ¬rst phase is the sifting phase, where Alice and Bob negotiate which

bits are used and which bits are discarded. To avoid a man-in-the-middle attack by

Eve, this message exchange must be authenticated. After agreeing on the bits and

being sure that Eve has not modiļ¬ed messages by using an authentication scheme,

Alice and Bob go on to the reconciliation phase or error correction phase. Because

the quantum channel is not a noiseless channel, Alice and Bob do not share the

same identical string. There is a small portion of errors in Bobā™s string, which is

corrected in this phase. Again Eve has the possibility to modify messages during

this phase to her interest. Therefore, Alice and Bob must authenticate this phase.

Passing reconciliation, Alice and Bob share a string, which is identical with very

high probability. But this string cannot be used as a key yet. Eveā™s information

about the string must be considered. She has gained information during the error

correction and maybe also during the quantum transmission. Hence, Alice and Bob

must map their string via a function to a smaller subset, so that Eveā™s knowledge

decreases almost to zero. This stage is called privacy ampliļ¬cation and afterward

Alice and Bob share a secret key only known by them.

M. Pivk (B)

Safety & Security Department, Quantum Technologies, AIT Austrian Institute of Tech-

nology GmbH, Lakeside B01A, 9020 Klagenfurt, Austria, mario.pivk@ait.ac.at:

http://www.ait.ac.at

Pivk, M.: Quantum Key Distribution. Lect. Notes Phys. 797, 23ā“47 (2010)

c Springer-Verlag Berlin Heidelberg 2010

DOI 10.1007/978-3-642-04831-9 3

24 M. Pivk

Fig. 3.1 BB84. ka is the k a Alice Bob ka

pre-shared key. K is the

generated key after protocol

Quantum channel

execution

sifting

authka(sifting)

error correction

authka(error correction)

privacy amplification

K K

3.1 Quantum Channel

As mentioned, the ļ¬rst stage of the BB84 protocol is the quantum transmission.

Therefore, we take a closer look at the physical realization: How can qubits be

represented and transmitted? In the second part we discuss what Alice and Bob have

to do, when they perform the BB84 protocol. Additionally, an equation is given,

which represents the theoretical throughput of the quantum channel.

3.1.1 Physical Realization

One way to represent a qubit is by using single photons. They are very suitable

for QKD, because photons hardly interact with each other and they can overcome

long distances with low loss in optical ļ¬bers. Polarization is one of the photonā™s

attributes which can serve as a qubit property. There exists rectilinear polarization

(horizontal/0ā—¦ and vertical/90ā—¦ ) and diagonal polarization (+45ā—¦ and ā’45ā—¦ shifted).

We can map horizontal and vertical with the qubits states |0 and |1 , and +45ā—¦

and ā’45ā—¦ shifted with the states |+ and |ā’ , respectively. Thus, we have the same

statistical probabilities as discussed in Sect. 2.1.3, which we will use next.

There are many different systems for implementing QKD. In Chap. 6 seven sys-

tems are presented which are developed for SECOQC.

One possibility to generate single photons is by attenuating the output of a

laser. This attenuator is characterized by the mean photon number, which deļ¬nes

the rate of photons passing the attenuator. Usually, the mean photon number is

0.1, meaning that 90% of the time no photon passes the attenuator but in 10%

of cases, the probability that a single photon passes is better than 95% (for more

information on the computation of the probability see [17]). Nevertheless, the

3 Quantum Key Distribution 25

output of the laser may consist of several path; in BB84 due to the amount of

different polarization states four are needed. But after a pulse passes the attenuator

it has an arbitrary polarization; therefore, linear polarizers and half-plates are used

to create the desired polarization. These elements can be seen as linear operators

(Pauli matrices) known from Sect. 2.1.2 performing the bit and phase ļ¬‚ip on the

qubits.

After the photons have the right polarization they pass through a beam splitter,

where they are combined. Now the pulse is transmitted over the quantum channel

(optical ļ¬ber or free space) and arrives at the receiver. There, a random choice is

made by the receiver as to which polarization ļ¬lter to use (e.g., horizontal or +45ā—¦ ).

If the receiver chooses differently to the sender we know from Sect. 2.1.3 that there

is a chance of 50% for the photon to pass the ļ¬lter (and change the polarization

to horizontal) or to get absorbed (this holds for both +45ā—¦ and ā’45ā—¦ polarized

photons). If the receiver chooses the same basis as the sender the photon passes

with 100% probability if it was polarized horizontal and with 0% probability if it

was polarized vertical. Behind the ļ¬lter a detector clicks every time a photon passes.

(this sendingā“receiving architecture is taken from [22]).

3.1.2 Photon Transmission and Throughput

Back to our scenario, Alice is on the transmitter and Bob on the receiver site of

the above-described quantum channel. Alice chooses now randomly two strings

independent of each other with length m. The ļ¬rst string represents the basis for

the quantum transmission and the second the proper value of the speciļ¬c bit. Alice

and Bob have the same mapping scheme in common. A sample mapping is deļ¬ned

in Tables 3.1 and 3.2.

Table 3.1 Base mapping

Base Representation bit

Rectilinear 0

Diagonal 1

Table 3.2 Value mapping

Rectilinear Diagonal value bit

Horizontal (0ā—¦ ) +45ā—¦ 0

Vertical (90ā—¦ ) ā’45ā—¦ 1

Alice starts now to transmit. Therefore, she takes the ļ¬rst bit of the ļ¬rst string,

indicating which base to use (e.g., a 0-bit denotes to use the rectilinear basis), and

the ļ¬rst bit of the second string indicating which value to take (e.g. a 1 denotes in

the rectilinear base to polarize the photon vertical and in the diagonal base to shift

the polarization by ā’45ā—¦ ). She applies this procedure on all m-bits of both strings

26 M. Pivk

and sends them as photons via the quantum channel to Bob. Bob on his part chooses

also a random string with length m, for his base choices. With these bits he measures

the incoming photons with the corresponding ļ¬lter. Note that it makes no sense to

measure with both ļ¬lters, because after measurement the original polarization is lost

as mentioned in the previous section or in Sect. 2.1.3. Bob keeps the measurement

results to himself. Consider that Bobā™s measurements do not completely match with

Aliceā™s ones, due to optical misalignment, disturbance on the quantum channel,

noise in Bobā™s detectors, or the presence of an eavesdropper Eve, although both

choose the same basis.

Before describing the next step, we continue by analyzing the throughput of the

quantum channel. In [24] a theoretical function is given by which the several losses

on the quantum channel can be computed:

gq = Ī¼ Ā· Ī± f Ā· Ī±e Ā· Ī·det Ā· kdead . (3.1)

The gain of the quantum channel gq consists now of the mean photon number Ī¼,

which we discussed in the previous section. The next factor Ī± f represents the ļ¬ber

loss. This loss is distance dependent and increases with higher distances. For the

receiverā™s detector Ī·det as detection efļ¬ciency and kdead as factor accounting for the

reduction of the photon detection rate due to the dead time is given. The dead time

is the hold-off time following each detection event; during this time the bias voltage

of the device is below a certain level such that no photon can be detected. Ī±e is the

additional loss of the system.

To compute the number of Bobā™s measurement results the data rate f data is

required, which is the number of photons Aliceā™s laser can send. This rate is given

in hertz and can have range from MHz to GHz. These different rates have impact

on the gain of the quantum channel: with higher rates the efļ¬ciency shrinks. So the

key material Bob receives per second can be computed by f data Ā· gq . The Eq. 3.1

conforms with experimental test done in [24].

As long as the strings which Alice and Bob need for the choice of bases are

randomly chosen (the probability to send a qubit in the rectilinear base or diagonal

base is 50%), half of Bobā™s results, i.e., the raw key, must be discarded because of

the independence of both strings (see later in Sect. 3.2.1). To minimize this loss of

raw key bits a concept was designed in [13], which increases the efļ¬ciency. Instead

of having the same probability for 0ā™s and 1ā™s in the string, the authors propose to

increase the probability for one of them. In fact the photons will be transmitted more

often in one base than in the other. Thus, the rate in which Alice and Bob select the

same base will increase. We will discuss this more precisely in Sect. 3.2.1.

Finally, the communication between Alice and Bob on the quantum channel is

ļ¬nished. They now switch to the public channel. So far, Alice holds the two strings

of length m containing her choice of base and value and Bob a string of length m

containing his choice of bases and his measurement results of length gq Ā· m. The

smaller size is due to the loss on the quantum channel.

3 Quantum Key Distribution 27

3.2 Public Channel

The communication via the public channel is necessary for Alice and Bob, since

they must negotiate on which bits they perform the next steps. Because they choose

their bases for the quantum transmission randomly they must know in which cases

they used the same basis. After agreeing on them, the errors must be corrected,

since the communication via the quantum channel is noisy. And as a last step Alice

and Bob must reduce Eveā™s knowledge, which she gained during the protocol. By

intercepting and resending photons Eve gains knowledge of the raw key (this issue

is reļ¬‚ected by the error rate) and also eavesdropping on the messages on the public

channel increases her knowledge. If Eve has the possibility to modify messages,

she can start a man-in-the-middle attack and then share keys with both disguised as

oneā™s peer.

3.2.1 Sifting

The ļ¬rst phase on the public channel is sifting. After Alice has sent random bits

mapped into randomly chosen quantum bases via photons, further steps are required

such that she shares the same bit string with Bob. The ļ¬rst thing Alice must know

is which photons Bob has measured. By reason of the fact that only a small fraction

of pulses contain photons, and several losses on the quantum channel and at Bobā™s

detector, Alice does not know which bit Bob received. Therefore, Bob sends a mes-

sage on the public channel to inform Alice which photons he has measured. The

easiest way is to send a string as long as the string chosen at the beginning for the

bases, which we indicate with length m. Bob sets now the position where he was

able to make a measurement to 1 and the other positions to 0. Since we want to save

communication trafļ¬c, we can beneļ¬t from the fact that the gain of the quantum

channel gq (Eq. 3.1) is a very small factor (<0.01). Bob must only tell Alice which

position he received. To represent a position log2 m-bits are necessary. Let 2n be the

length of the raw key, which is equal to gq Ā· m, then 2n log2 m-bits are necessary

to tell Alice the measured positions. This would be more efļ¬cient if the following

equation is fulļ¬lled:

2n log2 m = gq Ā· m log2 m < m.

We know that the gain of the quantum channel is less than 0.01, so it is sufļ¬cient

that m < 2100 . The sending rate is maximal in the range of GHz (109 ā 230 ), hence

adequate for this sifting transmission mode.

With this message Alice knows only which position Bob has measured but not

if he has used the same basis, because they have randomly and independently cho-

sen the bases. Thus, Bob sends a second message, in which he publishes the bases

he used. An optimized approach sends only those positions where he has success-

fully measured a photon. Thus, the length of the second message is 2n. Note that

Bob sends only his sequence bases (see Sect. 3.1.2) reduced by the bits where no

28 M. Pivk

measurement was possible, and not the measurement results. After Alice receives

both messages she can reduce her secret bit value string by canceling out those

positions which Bob did not receive (Bobā™s ļ¬rst message) and those positions where

she uses different bases at transmission (comparison by her base string and Bobā™s

second message). To make sure Bob shares the same string with her. Alice sends

a message to Bob containing her choice of bases for those positions where Bob

received a photon. Bob himself performs the same procedure as Alice and cancels

out those positions with different bases. Finally, the sifting phase is over and Alice

and Bob share a secret key: the so-called sifted key. However, error remains due to

the noisy quantum channel.

Alice Bo b

1011011000101010 1101110010011000

0010010110110101

010 1010 00101

2,3,4,6,7,8,9,12,13,14,15,16

0010010110110101

_101_1001__11000

010 1011 10101

_011_1100__01010 010 1010 00101

011011 011011

quantum public

base string key string canceled

channel channel

Fig. 3.2 QKD protocol until the end of the sifting phase

But what is the length of this key? Since Alice and Bob have chosen the two

bases for transmission and measuring randomly and independently, the probability

that they use the same basis is 1 Ā· 1 + 1 Ā· 1 = 1 . The length of the sifted key reduced

22 22 2

by mismatching bases from the raw key is 2n = n. The complete process until

2

the output of the sifted key is demonstrated in an example in Fig. 3.2. The sending

key length is m = 16. Assuming that the gain of the quantum channel is given by

gq = 0.75 (which is not a realistic value), we use Tables 3.1 and 3.2 for mapping

bits to photons. So the sifted key length is n = m Ā· g p Ā· 1 = 6.

2

As mentioned in Sect. 3.1.2 it is suggested [13] to choose the strings representing

the photon bases with different probability. So far, we chose the rectilinear or the

diagonal basis with probability 1 . Assume now that Alice and Bob choose a basis

2

with probability Ī“ ā [0, 1], whereby the other basis is used with complementary

probability 1ā’Ī“. The protocol gain for the normal BB84 is 0.5 as we have computed

before; the protocol gain g p for the case that the probability of base usages can be

changed is

g p = Ī“ Ā· Ī“ + (1 ā’ Ī“) Ā· (1 ā’ Ī“) = 2Ī“ 2 ā’ 2Ī“ + 1. (3.2)

3 Quantum Key Distribution 29

1

0.9

0.8

protocol gain

0.7

0.6

0.5

0.4

0 0.2 0.4 0.6 0.8 1

delta

Fig. 3.3 Protocol gain g p when delta Ī“ is variable (Eq. 3.2)

The fact that Ī“ is variable gives us the probability to increase the protocol gain.

As you can see in Fig. 3.3 the gain g p rises to 1 if Ī“ goes to 1 (to 0 ā“ analog for the

other basis). So the case Ī“ = 0.5 would be the worst case.

But what happens with the security if Ī“ goes to 1. In Sect. 3.2.3.1 we will

discuss this in detail. To say it right away, the chance for Eve to eavesdrop the

photons without being detected increases because Alice and Bob must negotiate at

least which bases to use with higher probability, and Eve can use this information.

The errors Eve produces decrease in the set where the basis is chosen with higher

probability and increase in the set of the other basis. Using the naive error esti-

mation, which calculates the error probability of both sets together, Alice and Bob

will fail to detect Eve, because the proportion of the sets changes. Finally, when

Ī“ reaches 1, Eve will not introduce any errors. Unless Ī“ = 1, if we use a reļ¬ned

error analysis, which reļ¬‚ects the error probability of both sets (detailed explanation

in Sect. 3.2.3.1), Eve can still be detected. In [13] it is described that the set of

bits after sifting must have enough samples to make an accurate error estimation.

Therefore, some constraints on Ī“ are deļ¬ned. Assume that m t photons are trans-

mitted from Alice to Bob, which Bob was able to measure. Then, on average, only

m t (1 ā’ Ī“)2 photons belong to the case where the basis with the smaller probability

is used. The size of this set was analyzed in [13] with the information we allow

Eve to obtain on the ļ¬nal key. If we except a ļ¬xed but arbitrarily small amount

of information on the ļ¬nal key, the number of this set is required only to scale

logarithmically with the length of the ļ¬nal key k. Thus, Ī“ must fulļ¬ll the following

equation:

30 M. Pivk

m t (1 ā’ Ī“)2 ā„ O (log k) ,

log k

Ī“ ā¤1ā’O ,

mt

if m t ā’ ā then Ī“ ā’ 1 and g p ā’ 1. (3.3)

Note that Ī“ never reaches 1 and the fact that the protocol gain goes to 1 can easily

be seen in Fig. 3.3.

3.2.2 Authentication of Sifting

Due to the possibility of a man-in-the-middle attack (combination of intercept/resend

attack, see Sect. 5.2.1, and modiļ¬cation of messages on the public channel) by

Eve we must ensure that the sifting phase is authenticated by Alice and Bob. We

know this phase consists of three messages exchanged between Alice and Bob. Two

messages sent by Bob, where he tells Alice which photons he was able to measure

and which bases he used for the measurement. The last message completing sifting

phase is sent by Alice, where she tells Bob which bases she used for those photons

Bob measured. To authenticate those messages we use Wegmanā“Carter authentica-

tion, as explained in Sect. 2.2.2. For Bobā™s two messages and for Aliceā™s message

we generate authentication tags and append them to the respective messages.

Because Wegmanā“Carter authentication is symmetric, we have to use a secret

key shared by Alice and Bob. Since key material is generated in every iteration a

small part of it can be used for the authentication of the next round. Unfortunately,

when we start the ļ¬rst round a pre-shared key must be available, which is exchanged

previously through a secret channel (face-to-face or in another way). In order that

key material remains after withdrawal by authentication, the choice of the algorithm

is a major concern. Following Eq. 2.35 the authentication cost for Wegmanā“Carter

is 4 Ā· ((b + log2 log2 a) Ā· log2 a) for an input size of a and an authentication tag size

of b. The key size grows only in the logarithmic scale, so it would be useful for our

intended purpose.

Similar to [11] we compute now the authentication cost for the sifting phase. In

the previous section we derived that the length of Bobā™s ļ¬rst message is 2n log2 m

and the length of the second message is 2n. The sum is 2n(1 + log2 m) and thus the

authentication key length w1 needed for the tag is

w1 = 4 Ā· gauth + log2 log2 2n 1 + log2 m Ā· log2 2n 1 + log2 m , (3.4)

where gauth is the length of the resulting tag. Alice and Bob compute their tag using

the hash function indexed by the authentication key and Alice compares if the tags

match.

If Alice veriļ¬es that the message is from Bob she sends her message with her

choice of bases, which has length 2n. We denote the authentication key length for

Aliceā™s message as w2 and the length is computed as

3 Quantum Key Distribution 31

w2 = 4 Ā· gauth + log2 log2 (2n) Ā· log2 (2n). (3.5)

If Bob determines that the generated tag with cost w2 matches with Aliceā™s tag

both can be sure that the probability that Eve modiļ¬ed the message is at most Īµ,

which is the property of the class of hash function (Īµ-ASU2 ).

The required key material to authenticate the sifting phase is the sum of all costs

w1 , w2 (Eqs. 3.4 and 3.5) and results in the total sifting authentication costs

t S = 4 Ā· gauth + log2 log2 2n 1 + log2 m Ā· log2 2n 1 + log2 m

+ 4 Ā· gauth + log2 log2 (2n) Ā· log2 (2n). (3.6)

3.2.3 Reconciliation

The reconciliation stage is split into two parts. The ļ¬rst major part is the error

estimation. Its aim is to ļ¬nd the correct error rate. To guarantee an optimal error

correction, part two of reconciliation. The error correction has the task of correcting

all errors in Bobā™s string via public discussion. Here some information about the

string must be disclosed and exchanged between Alice and Bob.

3.2.3.1 Error Estimation

The error estimation is an important step in the QKD protocol to determine the

proper error rate of the sifted key. Usually, in BB84, the error rate p is estimated by

picking a small random subset of bits with length r from those given in the sifted

key. This test string is publicly compared by Alice and Bob and yields in a certain

number of errors e. If the length of the test string is chosen adequate to the length of

the sifted key n, the error probability is

e

p= . (3.7)

r

Of course, since a part of the sifted key has been announced, those bits must be

deleted to avoid information leakage to Eve. This elimination has little effect on

the length of the ļ¬nal key if the length of the sifted key is large and if the error

estimation is not executed every round. The error rate found for a round can also be

used in the following rounds.

If the error rate p turns out to be very large, then either eavesdropping has

occurred or the channel is somehow unusually noisy. However, the sifted key is dis-

carded and Alice and Bob may re-start the whole protocol again (on another quan-

tum channel). This threshold pmax , for which the rate should not exceed p ā¤ pmax ,

can be set to, e.g., 11% because at the moment the best error correction code

32 M. Pivk

approaches a maximal tolerated error rate of 12.9% [21]. If the error rate p is

reasonably small ( p ā¤ pmax ), Alice and Bob can continue with error correction.

An improved error estimation was presented in [1] and [13]. In the reļ¬ned error

analysis there does not compute a single error rate but two values are estimated.

The idea is not to merge the measurements during the quantum transmission, where

Alice and Bob have used the same basis, into one set (more precisely the sifted key)

and choose the random test subset out of it. They choose two random test subsets.

The ļ¬rst subset consists of all measurements where Alice and Bob have used the

ļ¬rst basis (e.g., rectilinear) and the second one where they used the second basis

(e.g., diagonal). Let r1 be the length of the ļ¬rst subset and r2 be the length of the

second subset just before Alice and Bob publicly compare both strings and estimate

the number of errors e1 and e2 , respectively, which leads to the error rates

e1

p1 = , (3.8)

r1

e2

p2 = , (3.9)

r2

where p1 is the error rate for the photons measured with the ļ¬rst basis and p2 those

with the second basis and

p1 + p2

p= . (3.10)

2

The advantage compared to the single error rates is as follows: If Eve starts a

speciļ¬c attack like the biased eavesdropping strategy (a specialization of intercept

and resend, see Sect. 5.2.1). Then she chooses the probability q1 for measuring

each photon sent from Alice to Bob in the ļ¬rst basis (e.g., rectilinear) and a second

probability q2 for measuring each photon in the second basis (e.g., diagonal). Hence,

with probability 1 ā’ q1 ā’ q2 she does not measure the photon. When Alice and Bob

use the same basis errors occur only if Eve uses a different basis. Regarding Bobā™s

side, the photons measured by Eve are randomized and yield an incorrect bit in half

of these cases. This introduces an error rate of p1 = q22 for the ļ¬rst basis. Similarly,

for the second basis an error rate p1 = q22 is obtained (without respect to the normal

noise on the quantum channel). If we apply these two error rates and Eq. 3.10 to the

requirement p ā¤ pmax it results in (q1 + q2 ) ā¤ 4 pmax . Eve has the possibility to vary

her probability q1 in a big range. In contrast if we use the constraint p1 , p2 ā¤ pmax

which has the same property as the single error rate constraint in a random noisy

channel, Eveā™s possibility to choose the probabilities is shortened with q1 , q2 ā¤

2 pmax . With the reļ¬ned error analysis the biased eavesdropping strategy is avoided

(e.g., q1 = 3 pmax , q2 = 0 is accepted when we measure only one error rate, but

rejected by the detailed error measurement).

In Sect. 3.2.1 we have heard about a strategy to vary the probability of used

bases at sending and receiving, to boost the protocol gain g p (in standard BB84

protocol the probability for sending in one of the bases is 1 as described in Eq. 3.2).

2

3 Quantum Key Distribution 33

The difļ¬culty now is that with increasing or decreasing Ī“, a biased eavesdropping

strategy where Eve aware of Ī“ is more difļ¬cult to detect using the simple error

estimation rate. In this case the simple error rate is

Ī“ 2 p1 + (1 ā’ Ī“)2 p2 Ī“ 2 q1 + (1 ā’ Ī“)2 q2

= .

p= (3.11)

Ī“ 2 + (1 ā’ Ī“)2 2(Ī“ 2 + (1 ā’ Ī“)2 )

If Eve chooses the strategy q1 = Ī“ and q2 = 1 ā’ Ī“ we see in Fig. 3.4 that when

Ī“ ā’ 1 or Ī“ ā’ 0 the error probability p ā’ 0 unlike the reļ¬ned error analysis where

Ī“ ā’ 1 then p1 ā’ 0 but p2 ā’ 0.5. Regardless of how Ī“ is chosen (0 < Ī“ < 1) if

the measurement set is quite big (as deļ¬ned in Sect. 3.2.1) then there would be no

problem to detect Eve, which is not possible with the simple error analysis.

0.5

complete set

subset base 1

subset base 2

0.45

0.4

0.35

0.3

error rate

0.25

0.2

0.15

0.1

0.05

0

0 0.2 0.4 0.6 0.8 1

delta

Fig. 3.4 Error rates (variable Ī“) after a biased eavesdropping attack with q1 = Ī“

3.2.3.2 Error Correction

Henceforth we will model the quantum channel as binary symmetric channel (BSC).

In a BSC (p) we have an alphabet of two symbols (0, 1) which are transmitted over

the channel from a sender to a receiver. With probability p noise is added to the

transmitted symbol, meaning the receiver gets a 1 instead of a 0 and a 0 instead of a

1, respectively. For every symbol we have a probability 1ā’ p that it will be correctly

received (see Fig. 3.5).

After the sifting phase Alice holds a random string ska and Bob skb with equal

length |ska | = |skb | = n. The difference between these two strings depends on

the quantum bit error rate (QBER) p of the channel. Starting the QKD protocol

34 M. Pivk

1ā“p

0 0

p

sender receiver

p

1

1

1ā“p

Fig. 3.5 Binary symmetric channel (BSC): symbols are exposed to noise with probability p

this probability p is unknown or rests on empirical values. Further on, the error

estimation phase as presented in Sect. 3.2.3.1 gives a good approximation of the

error rate. Observe that dist (ska , skb ), the amount of places in which both strings

differ (Hamming distance), is nearly np. Setting ska = A and skb = B (A and B

are random variables) the conditional entropy (Eq. 2.38) of A given B is

H ( A|B) = H (A ā• B) = nh( p),

where h( p) is now short for Shannon entropy H (X ) and the random variable X is a

Bernoulli trial with parameter p (for each x ā X , p(x) is the same).

The task is to correct Bobā™s string B without disclosing enough information that

gives Eve chances to reconstruct the very same string. Therefore, a reconciliation

protocol R p is deļ¬ned, which runs on both strings A, B and results in the string

S by exchanging some information Q on the public channel. We write S = ā„ if

the protocol fails to produce S. Since Q must be exchanged on the public channel,

an eavesdropper Eve can gain some information on S, which can be expressed by

I E (S|Q). This is the expected amount of bits that an eavesdropper Eve can get on S

given Q.

Brassard and Salvail [7] have formulated some deļ¬nitions to characterize such

reconciliation protocols. The ļ¬rst deļ¬nition deals with the robustness.

Deļ¬nition 3.1 A reconciliation protocol R p is Īµ-robust if

(āN0 (Īµ))(ān ā„ N0 (Īµ)) pr ob(A = Ī±, B = Ī²) pr ob(R p (Ī±, Ī²) = [ā„, Ā·]) ā¤ Īµ

Ī±,Ī²ā{0,1}n

where 0 ā¤ Īµ ā¤ 1.

If a protocol is Īµ-robust the probability to fail is maximal Īµ. The next theorem is

a direct consequence of the noiseless coding theorem.

Theorem 3.1 (ā p ā¤ 1 ) (āreconciliation protocol R p ) If there exists 0 ā¤ Īµ ā¤ 1 such

2

that R p = [S, Q] is Īµ-robust then

I E (S|Q)

ā„ 1,

lim

nh( p)

nā’ā

3 Quantum Key Distribution 35

where n is the length of the transmitted string.

In other words, Eveā™s information of S is greater than or equal to the information

of A given B. Eve cannot have less than this information if the reconciliation proto-

col R p is successful. But if these two pieces of information are equal the protocol is

optimal. Let us deļ¬ne it by the next deļ¬nition:

Deļ¬nition 3.2 A protocol R p is optimal if

(āĪµ ā„ 0)[R p = [S, Q] is Īµ-r obust]

and

I E (S|Q)

= 1,

lim

nh( p)

nā’ā

where the public channel is a BSC(p).

In [7] a construction of a optimal protocol is presented. The basic idea is that

Alice creates a random label of her string A with length approximately nh( p), when

the length of string A is n. If Alice sends this label over the channel, Eve would

only have this information and so Deļ¬nition 3.2 holds, the protocol is optimal.

When Bob obtains the label f ( A), he computes all possible inputs, resulting in a

set S{B | f (B ) = f ( A)}. The string B ā S with minimal Hamming distance from

B is the desired S. Brassard and Salvail [7] described this protocol as unpractical,

n

because Alice and Bob require 2m2 functions. But if the function f (x) is chosen

from a univer sal2 class of hash functions (see Deļ¬nition 2.5) the protocol remains

optimal. The speciļ¬cation of a univer sal2 class of hash functions can be done in a

short and efļ¬cient way. The only problem which remains is that there are no known

efļ¬cient algorithms to compute the set S{B |h(B ) = h(A)}, h ā H, if the hash

value of A is known.

The goal is to create an efļ¬cient reconciliation protocol, which is deļ¬ned as

follows:

Deļ¬nition 3.3 A reconciliation protocol R p is efļ¬cient if there is a polynomial t(n)

ĀÆp

such that T R (n) ā¤ t(n) for n sufļ¬ciently large, where n is the length of the strings

ĀÆp

transmitted over the secret channel and T R (n) represent the expected running time

of R p , given an n-bit long input string.

Deļ¬nition 3.4 A reconciliation protocol R p is ideal if it is both optimal and

efļ¬cient.

Brassard and Salvail determined when their optimal protocol becomes ideal,

using the univer sal2 class of hash function H3 [9]. They proved that their protocol

is ideal if and only if NP ā BPP, which is a hypothesis.

36 M. Pivk

With the fact that a ideal reconciliation protocol depends on a open question in

complexity, which is unlikely to be true, we have to ļ¬nd another solution. In Sect.

2.2.1 (universal hashing) we had a similar problem. There we deļ¬ne a str ongly

univer sal2 class of hash functions, where the size of this class becomes too large

and unpractical. But just a small change of the probability on the theoretical bound

makes these classes useful. Here again if we do not demand optimality and allow

the reconciliation protocol to transmit a small amount of leaked information above

the theoretical bound the protocol becomes efļ¬cient and useful. In [7] this charac-

terization was deļ¬ned as in Deļ¬nition 3.5.

p

Deļ¬nition 3.5 A reconciliation protocol RĪ¶ is almost ideal if for all Ī¶ ā„ 0 we have

p

1. (āĪµ ā„ 0)[RĪ¶ = [S, Q] is Īµ-robust]

2. limnā’ā I E (S|Q) ā¤ 1 + Ī¶

nh( p)

p

3. (ā polynomial t)(āN0 (Ī¶ ))(ān ā„ N0 (Ī¶ ))[T RĪ¶ ā¤ t(n)]

ĀÆ

for n the length of the string transmitted over the B SC( p).

An almost-ideal protocol has an error probability bounded by Īµ approaching 0 for

increasing n (see Deļ¬nition 3.51). The amount of leaked information is allowed to

be slightly greater than the theoretical bound (see Deļ¬nition 3.52), but the parameter

Ī¶ indicating the excess of information is chosen by Alice and Bob before the start

p

ĀÆ

of the protocol. After their choice the expected runtime T RĪ¶ of the reconciliation

protocol must be bounded by a polynomial (see Deļ¬nition 3.53).

Such an almost-ideal protocol was presented in [7] and an earlier version in [4].

This simple protocol called CASCADE leaks an amount of information close to the

theoretical bound, when the error probability is below 15%.

The appropriate part of CASCADE for the error correction is BINARY. When

Bobā™s string contains an odd number of errors, Alice and Bob can perform an inter-

active binary search on the strings to ļ¬nd and correct one error, respectively. At the

beginning Alice sends Bob the parity of the entire string and Bob checks if his parity

bit differs from Aliceā™s bit. If not, there is an even number of errors (possibly zero)

in the string and nothing is done. If the parity bits differ the following steps are run

through to ļ¬nd the error:

1. Alice sends Bob the parity of the ļ¬rst half of the string.

2. Bob determines whether an odd number of errors occurred in the ļ¬rst or in the

second half by testing the parity of his string and comparing it to the parity sent

by Alice.

3. With the half determined in step 2 we start again at step 1, until the erroneous bit

is found.

For a better understanding see the visualization in Fig. 3.6. The leaked informa-

tion for a string with an even number of errors is one bit and for a string with an odd

number log n + 1 bits, whereas one error is corrected.

3 Quantum Key Distribution 37

skip bit

transmitted

by Alice

erroneous bit parity bit

Fig. 3.6 BINARY corrects exact one error of a block with an odd number of errors

CASCADE proceeds in several passes, which are deļ¬ned by Alice and Bob

before execution relative to the error probability p. Alice and Bob hold string A =

A1 , ..., An and B = B1 , ..., Bn ( Ai , Bi ā {0, 1}), respectively. For the ļ¬rst pass they

choose k1 (determination of parameter k1 is shown later) and split their strings into

blocks of length k1 . Block v for pass 1 is deļ¬ned by K v = {l|(v ā’ 1)k1 < l ā¤ vk1 },

1

v = 1... kn1 . On each block BINARY is performed. This can be done parallel for

each block to minimize the communication effort. For passes i > 1, Alice and Bob

choose a ki and a random function f i : [1..n] ā’ 1.. kn1 . Now the block j in

pass i has the form K ij = {l| f i (l) = j}. Again Alice and Bob perform BINARY on

these blocks to correct errors. In the previous version of CASCADE [4] the leaked

information about the string is eliminated during execution of BINARY by removing

the last bit of each subset for which a parity bit is computed. In [7] an improvement

is introduced where the removed bits are kept. This allows us to correct more errors

in later passes. Because if in pass i > 1 an error Bl = Al of block K ij is corrected,

each block K v from previous passes containing this bit l ā K v , 1 ā¤ u < i, has now

u u

an odd number of errors and can be corrected with less effort. Therefore, a set K of

these blocks is created. The smallest block in K is chosen and BINARY is executed

on it. After correcting the error Bl , we create again a new set B with the previous

blocks containing bit Bl from each pass from 1 to i. Now set K = B āŖ K\B ā© K is

determined. If K = ā… then by choosing again the smallest block further errors can

be eliminated. Pass i ends when all blocks K ij are checked and when there are no

more blocks in K .

38 M. Pivk

For determining the parameter ki let Ī“i ( j) be the probability that after the pass

i ā„ 1, 2 j errors remain in block K v . Let E i be the expected number of errors in K v

1 1

after pass i. So that after the ļ¬rst pass we have

Ī“1 ( j) = prob(X = 2 j) + prob(X = 2 j + 1), (X ā Bin(k1 , p)),

k1

2

E1 = 2 jĪ“1 ( j).

j=1

Suppose now that k1 is chosen such that

k1

2

1

Ī“1 (l) ā¤ Ī“1 ( j) (3.12)

4

l= j+1

and

ln 1

E1 ā¤ ā’ 2 (3.13)

2

are satisļ¬ed and for the following passes we simply deļ¬ne ki = 2kiā’1 for i > 1.

Brassard and Salvail have shown in [7] that if k1 satisļ¬es Eqs. 3.12 and 3.13 the

amount of information I (Ļ) per block of length k1 leaked after Ļ passes can be

bounded as follows:

k1

Ļ 2

1 ā’ (1 ā’ 2 p)k1 jĪ“1 ( j)

I (Ļ) ā¤ 2 + log k1 + 2 log k1 . (3.14)

2lā’1

2 l=2 j=1

For different error probabilities p ā {0.01, 0.05, 0.10, 0.15} in four passes the

theoretical bound and the leaked information I (4) are computed with Eq. 3.14. In

addition empirical tests were performed to ļ¬nd the average amount of leaked infor-

mation I (4) (10 tests with n = 10, 000). The results of [7] are present in Table 3.3.

Ė

I (4)

The column f ( p) kh( p) gives the percentage of additional leaked information relative

to the theoretical bound.

Table 3.3 CASCADE benchmark

f ( p) = I (4)

Ė

p k1 I (4) kh( p) I (4) kh( p)

0.01 73 6.47 5.89 6.81 1.16

0.05 14 4.60 4.01 4.64 1.16

0.10 7 3.81 3.28 3.99 1.22

0.15 5 3.80 3.05 4.12 1.35

3 Quantum Key Distribution 39

Finally, the reconciliation phase is ļ¬nished. After getting random strings for

Alice and Bob from the sifting phase with length n and error probability p the

described reconciliation protocol (CASCADE) has corrected Bobā™s string and only a

very low probability remains that Bobā™s string has still an error. The leaked informa-

tion was kept down near the theoretical bound with an additional leakage of 16ā“35%

depending on the error probability. In Chap. 4 a advancement of this protocol is

presented, called Adaptive Cascade.

3.2.4 Conļ¬rmation/Authentication of Error Correction

The next step in the protocol is on the one hand to conļ¬rm the strings in Aliceā™s

and Bobā™s possession and on the other hand to authenticate the reconciliation phase.

Fortunately, this can be done in one step based on the fact that Eve could mount

a man-in-the-middle attack during the reconciliation phase. Without the authenti-

cation step, Alice and Bob could believe that their strings, on which they operate,

are identical when they are not. Only one different bit is necessary to produce com-

pletely uncorrelated strings at the privacy ampliļ¬cation phase (see Sect. 3.2.5). The

best solution for Alice and Bob is to verify that the outputs of the error correction

phase are the same. This will authenticate the complete communication during the

reconciliation phase, because an intervention of Eve will introduce errors.

The veriļ¬cation can be done by hashing the corrected random strings and com-

pare the resulting tags. We also should keep the size of the tag small compared to

the input (corrected shifted key) size. Every additional bit will increase the leaked

information and accordingly Eveā™s knowledge.

As in Sect. 3.2.2 we have to sacriļ¬ce a part of already shared key for authen-

tication. Again the best choice to authenticate the corrected shifted key is to use

Wegman and Carter authentication as presented in Sect. 2.2.2. Gilbert and Hamrick

acknowledge that this is the best choice and analyzed the total authentication

costs for the error correction phase [11]. After Eq. 2.35 the authentication cost

is 4 Ā· ((b + log2 log2 a) Ā· log2 a) for an input size of a and an authentication tag

size of b.

The size of the corrected sifted key at the end of the error correction phase is n.

The required authentication key length w1 for the generation of an authentication

tag is

w1 = 4 Ā· (g EC + log2 log2 n) Ā· log2 n, (3.15)

where g EC is the length of the resulting tag. Alice and Bob compute the tag using

the hash function indexed by the authentication key and compare if the tags match.

The main problem is if Bob sends this tag to Alice, Eve can modify the tag with

arbitrary bits to convince Alice that the strings do not match when, in fact, they do.

To avoid this denial-of-service attack Bob must authenticate his message. Therefore,

he computes another tag, which authenticates the previous tag as his tag and sends

it to Alice. Again he needs a part of the shared key to generate the tag with length

gauth which costs

40 M. Pivk

w2 = 4 Ā· (gauth + log2 log2 g EC ) Ā· log2 g EC . (3.16)

If Alice determines that her generated tag with cost w1 matches with Bobā™s tag

and the authentication tag with cost w2 does as well, she can be sure that the strings

are equal. If the tag with cost w1 does not match but the second does, there must be

at least an error in the string of Bob. In the case that both tags do not match, she can

assume that either Eve manipulates the messages or the shared keys of Alice and

Bob are different.

To indicate Bob that the tags match Alice sends a piece of the key with length

w3 = g EC

Ė (3.17)

to Bob. Again to avoid the man-in-the-middle attack, Alice must authenticate her

message. With the same tag length gauth as Bobā™s before, yielding an authentication

cost of

w4 = 4 Ā· (gauth + log2 log2 g EC ) Ā· log2 g EC .

Ė Ė (3.18)

After Bob has compared the tags of Alice with his ones they agree the authenti-

cation step for the error correction is complete. Alice and Bob can now be sure that

with probability of 1 ā’ Īµ the strings are equal. Because they use an Īµ- ASU2 class

of hash functions the collision probability for two distinct values is at most Īµ as

the Deļ¬nition 2.5 for universal hash functions declare. Also the probability for Eve

to modify one of this authentication messages is at most Īµ, even if she suppresses

modiļ¬cations during the error correction phase or make Alice and Bob believe they

have different strings when, in fact, they have not.

The required key material to authenticate the reconciliation phase is the sum of

all costs w1 , w2 , w3 , w4 (see Eqs. 3.15, 3.16, 3.17, and 3.18), which results in the

total error correction authentication costs

t EC = 4(g EC + log2 log2 n) log2 n + 4(gauth + log2 log2 g EC ) log2 g EC

+ g EC + 4(gauth + log2 log2 g EC ) log2 g EC .

Ė Ė Ė (3.19)

3.2.5 Privacy Ampliļ¬cation

The last step to the secret key is the privacy ampliļ¬cation phase. Bennett, Brassard,

CrĀ“ peau, and Maurer [6] give a good explanation what privacy ampliļ¬cation is:

e

Privacy ampliļ¬cation is the art of distilling highly secret shared information,

perhaps for use as a cryptographic key, from a larger body of shared information

that is only partially secret. Let Alice and Bob be given a random variable W , as a

random n-bit string, while an eavesdropper Eve learns a correlated random variable

V , providing at most t < n bits of information about W , i.e., H (W |V ) ā„ n ā’ t.

The details of the distribution PV W are generally unknown to Alice and Bob, except

3 Quantum Key Distribution 41

that it satisļ¬es this constraint as well as possibly some further constraints. They

may or may not know PW . Alice and Bob wish to publicly choose a compression

function g : {0, 1}n ā’ {0, 1}r such that Eveā™s partial information on W and her

complete information on g gives her arbitrarily little information about K = g(W ),

except with negligible probability (over possible choices for g). The resulting K is

virtually uniformly distributed, given all Eveā™s information; it can hence be used

safely as a cryptographic key.

The size r of the secret that Alice and Bob can distill depends on the kind as well

as the amount of information available to Eve. Eve can obtain

ā¢ t arbitrary bits of W ,

ā¢ t arbitrary parity checks of W ,

ā¢ the result of an arbitrary function mapping n-bit strings to t-bit strings,

ā¢ the string W transmitted through a binary symmetric channel with bit error prob-

ability p satisfying h( p) = 1 ā’ n , and hence with capacity n where h denotes

t t

the binary entropy function.

Assume that we have the scenario where Alice and Bob are connected by an inse-

cure channel to which Eve has passive perfect access. Note that with authentication

of the communication active perfect access has the same characteristics, which will

not be discussed here for reasons of simplicity. So after Aliceā™s transmission on

the quantum channel each of them has knowledge of a correlated random variable.

Alice X , Bob Y , and Eve Z . Assume that these variables are distributed according

to some joint probability function p X Y Z , whereby Eve has partially control over this

distribution. Based on the fact that neither Alice nor Bob has an advantage compared

to Eve concerning information (I (X ; Y ) > I (X ; Z ), I (X ; Y ) > I (Y ; Z )), after the

sifting phase which can be denoted as random variable C, Alice can compute a string

W from X and C such that Aliceā™s uncertainty about W is 0 and Bobā™s uncertainty

about W is smaller than Eveā™s one:

H (W |XC) = 0,

H (W |Y C) < H (W |ZC). (3.20)

The reconciliation phase helps to remove Bobā™s uncertainty about W ; there-

fore, Alice sends a bit string D with length l is slightly larger than H (W |Y C)

such that H (W |Y C D) ā 0. Eveā™s uncertainty H (W |ZC D) is lower bounded by

H (W |ZC) ā’ l, which can be substantially positive, due to Eq. 3.20. We summarize

Eveā™s knowledge ZC D about W to the random variable V .

The aim of privacy ampliļ¬cation is now to generate a secret key K , of which

Eve has negligible amount of information. Therefore, Alice and Bob agree on a

function g (known by Eve) to generate K = g(W ). This g is chosen randomly from

a set G of function to avoid that Eve can decide beforehand which strategy to use.

Thus, this function is also a random variable G on the set G. The output length of

G : Wā’ {0, 1}r should decrease Eveā™s information about K to a minimum. Assume

I (W ; V ) ā¤ t then I (K ; GV ) ā 0 and H (K |GV ) ā r . But how must r be chosen? In

42 M. Pivk

[6] they state r = n ā’ t ā’ s and the security parameter s decreases Eveā™s information

ā’s

rapidly, because I (K ; GV ) ā¤ 2 2 .

ln

The theorem and the corollaries of [6] are presented now, which yields an upper

bound to Eveā™s information. It emerges that for the function set G the universal

classes of hash functions as described in Sect. 2.2.1 become useful, due to their

properties.

Theorem 3.2 Let X be a random variable over the alphabet X with probability

distribution p X and RĀ“ nyi entropy R(X ), let Q = G(X ). Then

e

2rā’R(X )

r ā’R(X )

H (Q|G) ā„ R(Q|G) ā„ r ā’ log2 1 + 2 ā„rā’ ,

ln 2

where G is the random variable corresponding to the random choice (with uniform

distribution) of a member of a universal class of hash functions X ā’ {0, 1}r .

The ļ¬rst inequality follows from Eq. 2.45. The second inequality can be proven

by using Jensenā™s inequality and using the fact that we use universal hash function.

For the complete proof we refer to [6]. The last inequality follows from log2 (1+y) ā¤

y

. The next corollary is derived from the above theorem.

ln 2

Corollary 3.1 Let PV W be an arbitrary probability distribution and let v be a par-

ticular value of V observed by Eve. If Eveā™s RĀ“ nyi entropy R(W |V = v) about W

e

is known to be at least c and Alice and Bob choose K = G(W ) as their secret key,

then

2r ā’c

H (K |G, V = v) ā„ r ā’ log2 1 + 2 ā„rā’ ,

rā’c

ln 2

where G is chosen at random from a universal class of hash functions W ā’ {0, 1}r .

Corollary 3.2 Let W be a random n-bit string with uniform distribution over

{0, 1}n , let V = e(W ) for an arbitrary eavesdropping function e : {0, 1}n ā’ {0, 1}t

for some t < n, let s < n ā’ t be a positive safety parameter, and let r = n ā’ t ā’ s.

If Alice and Bob choose K = G(W ) as their secret key, then Eveā™s expected infor-

mation about the secret key K , given G and V , satisļ¬es

2ā’s

I (K ; GV ) ā¤ ,

ln 2

where G is chosen at random from a universal class of hash functions {0, 1}n ā’

{0, 1}r .

Finally, corollary 3.2 can be proven with usage of Corollary 3.1 (see [6]). Note

that the security parameter does not depend on the error probability p or else vari-

ables, if the upper bound for Eveā™s knowledge t is known.

3 Quantum Key Distribution 43

Let us recapture the entire protocol to identify the knowledge t Eve has obtained.

The easiest knowledge to identify is in the reconciliation phase and the authenti-

cation of the reconciliation. We know that during error correction at least nh( p)

bits ( p is the error probability) are necessary to correct all errors. In Sect. 3.2.3.2 a

reconciliation protocol has been presented which reaches nearly this limit. It differs

only by a factor f ( p) given as in Table 3.3. Thus, the knowledge Eve accumulates

during this phase is n f ( p)h( p). If we formulate this as a fraction Ļ„1 by which the

reconciled key is to shorten then

n f ( p)h( p)

Ļ„1 ( p) = = f ( p)h( p) = ā’ f ( p) p log2 p + (1 ā’ p) log2 (1 ā’ p) .

n

(3.21)

In the conļ¬rmation/authentication of the error correction phase a hash value of

the key is transmitted. This tag has length g EC , giving Eve additional information.

The last phase where Eve can gain knowledge is the sifting phase, if she eaves-

drops several photons during quantum transmission. How much information Eve

gets, depends on the error probability p. LĀØ tkenhaus derived in [14] and [15] a frac-

u

tion Ļ„2 , by which we need to shorten the reconciliation key in addition to the other

parameters to get a secure key. Therefore, he used a trivial extension of Corollary

3.1:

I (K ; GV ) = H (K ) ā’ H (K |GV ) = r ā’ H (K |GV ) ā¤ r ā’ R(K |GV ). (3.22)

This inequality can be applied due to Eq. 2.45. Furthermore, in [14] it is shown

that the collision probability of a key k is bounded above by the collision probability

of his sifted key for averaged g and v, hence

I (K ; GV ) ā¤ r ā’ R(K |GV ) ā¤ r ā’ R(W |V ). (3.23)

We set the information I (K ; GV ) to zero and thus the shortening is

n ā’r R(W |V ) w

Ļ„2 = =1ā’ = 1 + log2 pc (v) v , (3.24)

n n

w

means averaged with respect to v and pc (v) is the collision probability

where v

2

wāW p(w|y) . We can express the collision probability for the sifted key as the

w

product of the collision probability for single bits of this sifted key pc (v) v =

( pc ( p))n with respect to the error rate of the quantum channel p. In [14] this colli-

(1)

sion probability was derived as

1

pc ( p) ā¤ + 2 p ā’ 2 p2 for p ā¤ 1/2,

(1)

(3.25)

2

which gives, ļ¬nally,

Ļ„2 ( p) ā¤ log2 1 + 4 p ā’ 4 p 2 for p ā¤ 1/2. (3.26)

44 M. Pivk

The gain for the privacy ampliļ¬cation g pa is composed of Ļ„1 from Eq. 3.21, Ļ„2

from Eq. 3.26, n (security parameter length) and g n (authentication tag length)

s EC

s g EC

g pa = 1 ā’ Ļ„1 ( p) ā’ Ļ„2 ( p) ā’ ā’

n n

= 1 + f ( p)( p log2 p + (1 ā’ p) log2 (1 ā’ p))

s g EC

ā’ log2 1 + 4 p ā’ 4 p 2 ā’ ā’ for p ā¤ 1/2. (3.27)

n n

Note that the two fractions n and g n are not crucial factors for the ļ¬nal key,

s EC

because they are almost ļ¬xed values and if the length of the key increases they

are comparatively small. Figure 3.7 shows that the maximal acceptable error rate

is around 10% for CASCADE and around 11% if we reach Shannonā™s limit. The

factors n and g n are not considered.

s EC

1 Cascade

Shannonā™s limit

0.8

gain of privacy amplification

0.6

0.4

0.2

0

0 0.02 0.04 0.06 0.08 0.1 0.12

error rate

Fig. 3.7 The gain of privacy ampliļ¬cation g pa for increasing quantum error rate p

Concluding the QKD protocol we give a universal class of hash function, which

can be used to reduce the reconciliation key of length n to a ļ¬nal key of length k.

Therefore, the multiplication in ļ¬nite ļ¬elds is deļ¬ned as

Deļ¬nition 3.6 Let A = GF (2n ) and B = {0, 1}k . Let h c (x) be deļ¬ned as the last k

bits of the product c Ā· x in a polynomial representation of GF (2n ). The set

HGF (2n )ā’{0,1}k = {h c : c ā GF (2n )}

is a universal family of hash functions [23].

3 Quantum Key Distribution 45

This family requires only n bits to identify the particular function (the value of c).

In particular it is chosen for privacy ampliļ¬cation because the multiplication of

large blocks can be done efļ¬ciently. We know that by using the traditional shift-

and-add algorithm, the multiplication of two elements of GF (2n ) can be achieved

in quadratic time. In [2] a simple algorithm is presented, which performs a multipli-

cation in a Ā· l log l steps for some small constant a.

The value c, which chooses a function of the family of hash functions, must be

random. Alice or Bob could randomly choose such a value c and announces it pub-

lictly to its peer. But we must consider that this data exchange must be authenticated,

not to be exposed to an attack by Eve. Recalling the sifting phase, where Bob has

sent Alice an authenticated message, in which he told her, which photons he was

able to measure and what bases he has used. A convention was that Bob chooses

his bases randomly, so Alice and Bob share a 2n authenticated random string (the

length is 2n because normal sifting has a gain of 0.5). They can now extract the ļ¬rst

n bits of this string and use it as c. For this reason the communication during the

privacy ampliļ¬cation phase and thus an additional authentication is not necessary.

As an example let the string for the random choice of base, which Bob sent

authenticated to Alice, be 0010011101011000101. After performing sifting and rec-

onciliation, the reconciliation key, shared by Alice and Bob, is 1101001110. Due to

the error rate and the information leaked during reconciliation we have computed

that Eve has 4 bits of information, so we must shorten the key to the length of 6 bits.

We extract the value of c from Bobā™s random choice of bases, which is 0010011101

and multiply c with the reconciliation key.

0010011101 Ā· 1101001110 = 100000011011010110

The ļ¬nal key consists now of the last six bits of the result (010110).

3.3 QKD Gain

In Sect. 3.1 and 3.2 discussing the communication over the classical and the quan-

tum channel we heard how a QKD system works and some equations are given to

compute the output of the several stages. The gain of the quantum channel gq in

Eq. (3.1), the protocol gain g p in Eq. (3.2), and the gain of privacy ampliļ¬cation g pa

in Eq. (3.27) form the complete gain. Additionally we must subtract the required

authentication key (t S (3.6) and t EC (3.19)) which are needed for the next round. So

the length k of the ļ¬nal authenticated key for one round is

k = m Ā· gq Ā· g p Ā· g pa ā’ t S ā’ t EC , (3.28)

where m is the length of the random sequence Alice generates at the beginning and

sends via the quantum channel to Bob. The major problem with this protocol is that

for the ļ¬rst round we need a pre-shared secret between Alice and Bob. Thus, the key

46 M. Pivk

output length would be limited to the length of the secret. After a certain āwarm-upā

phase the protocol would reach the expected output on average.

3.4 Finite Resources

All assumptions regarding the postprocessing (sifting, error estimation and correc-

tion, privacy ampliļ¬cation) and hence the security of quantum key distribution pro-

tocols have been proven in the asymptotic limit. However, the actual implementa-

tions of the protocols can only use ļ¬nite resources, such as limited computational

power and keys of ļ¬nite length. This fact has already been addressed for special

protocols like the BB84 protocol [12] or the six-state protocol [16]. In both scenarios

it has been shown that the values for the sifted key rate in the ļ¬nite scenario differ

signiļ¬cantly from the expected values from the asymptotic limit.

As described in [20] also the deļ¬nition of security has to be altered when consid-

ering ļ¬nite resources. In the asymptotic limit a key of length l is said to be secure if

its deviation Īµ from a perfect key tends to zero as l increases. Another property most

security deļ¬nitions lack is composability. Composability assures that a key coming

from a quantum cryptographic protocol can safely be used in classical applications

(e.g., for encryption with a one-time pad). For the nonasymptotic scenario Scarani

and Renner presented a security deļ¬nition, which satisļ¬es also composability [20].

Here a key is considered to be secure if the difference between the generated key

and a perfect key is smaller than Īµ, which means that Īµ is the maximum probability

that the generated key differs from a perfect key.

The main goal Scarani and Renner pursue in their paper is to obtain a sifted

key rate r based on a certain number of signals, a security parameter Īµ, and some

losses from the error correction. As starting point they take the relation from the

asymptotic limit, where the sifted key rate r is

r = S X |E ā’ H X |Y , (3.29)

where S is the von Neumann and H the Shannon entropy. The goal is achieved using

tools from Rennerā™s PhD thesis [18]. The exact formulas and proofs are described

in [20] and will not be further discussed here. The major result is that the key rate

becomes positive, e.g., for a little more than 104 signals and an error rate of 0.5% or

at least 105 signals and an error rate of 5%.

References

1. Ardehali, M., Chau, H.F., Lo, H.K.: Efļ¬cient quantum key distribution (1998). URL

http://www.citebase.org/abstract?id=oai:arXiv.org:quant-ph/98% 03007 32

2. Assche, G.V.: Quantum Cryptography and Secret-Key Distillation. Cambridge University

Press, New York, USA (2006) 45

3 Quantum Key Distribution 47

3. Bennett, C.H.: Quantum cryptography using any two nonorthogonal states. Phys. Rev. Lett.

68(21), 3121ā“3124 (1992). DOI 10.1103/PhysRevLett.68.3121 23

4. Bennett, C.H., Bessette, F., Brassard, G., Salvail, L., Smolin, J.A.: Experimental quantum

cryptography. J. Cryptology 5(1), 3ā“28 (1992) 36, 37

5. Bennett, C.H., Brassard, G.: Quantum cryptography : Public key distribution and coin tossing.

In: Proceedings of the IEEE International Conference on Computers, Systems, and Signal

Processing, pp. 175ā“179 (1984) 23

6. Bennett, C.H., Brassard, G., CrĀ“ peau, C., Maurer, U.M.: Generalized privacy ampliļ¬cation.

e

IEEE Trans. Inf. Theory 41(6), 1915ā“1923 (1995) 40, 42

7. Brassard, G., Salvail, L.: Secret-key reconciliation by public discussion. In: EUROCRYPT,

pp. 410ā“423 (1993) 34, 35, 36, 37, 38

8. Bruss, D.: Optimal eavesdropping in quantum cryptography with six states. Phys. Rev. Lett

81(14), 3018ā“3021 (1998) 23

9. Carter, L., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci. 18(2),

143ā“154 (1979) 35

10. Ekert, A.K.: Quantum cryptography based on bellā™s theorem. Phys. Rev. Lett. 67(6), 661ā“663

(1991). DOI 10.1103/PhysRevLett.67.661 23

11. Gilbert, G., Hamrick, M.: Practical quantum cryptography: A comprehensive analysis

(part one) (2000). URL http://www.citebase.org/abstract?id=oai:arXiv.org:quant-ph/00%

09027 30, 39

12. Inamori, H., LĀØ tkenhaus, N., Mayers, D.: Unconditional security of practical quantum key

u

distribution. Eur. Phys. J. D 41(3), 599ā“627 (2007) 46

13. Lo, H.K., Chau, H.F., Ardehali, M.: Efļ¬cient quantum key distribution scheme and proof of

its unconditional security. Journal of Cryptology 18, 133 (2005). URL http://www.citebase.

org/abstract?id=oai:arXiv.org:quant-ph/0011056 26, 28, 29, 32

14. LĀØ tkenhaus, N.: Estimates for practical quantum cryptography. Phys. Rev. A 59, 3301 (1999).

u

URL http://www.citebase.org/abstract?id=oai:arXiv.org:quant-ph/9806008 43

15. LĀØ tkenhaus, N.: Security against individual attacks for realistic quantum key distribution.

u

Phys. Rev. A 61(5), 052,304 (2000). DOI 10.1103/PhysRevA.61.052304 43

16. Meyer, T., Kampermann, H., Kleinmann, M., Bru, D.: Finite key analysis for symmetric

attacks in quantum key distribution. Phys. Rev. A 74(4), 042,340 (2006) 46

17. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge

University Press, Cambridge (2000). URL http://www.amazon.ca/exec/obidos/redirect?

tag=citeulike09-20% &path=ASIN/0521635039 24

18. Renner, R.: Security of Quantum Key Distribution. Ph.D. thesis, Swiss Federal Institute of

Technology 46

19. Scarani, V., Acin, A., Ribordy, G., Gisin, N.: Quantum cryptography protocols robust against

photon number splitting attacks for weak laser pulses implementations. Phy. Rev. Lett. 92(5),

057,901 (2004) 23

20. Scarani, V., Renner, R.: Quantum cryptography with finite resources: Unconditional security

bound for discrete-variable protocols with one-way postprocessing. Phys. Rev. Lett. 100(20),

200,501 (2008) 46

21. Smith, G., Renes, J.M., Smolin, J.A.: Better codes for BB84 with one-way post-processing

(2006). URL http://www.citebase.org/abstract?id=oai:arXiv.org:quant-ph/0607018 32

22. Tang, X., Ma, L., Mink, A., Nakassis, A., Xu, H., Hershmanand J. Bienfang, B., Su, D.,

Boisvert, R.F., Clark, C., Williams, C.: Quantum key distribution system operating at sifted-

key rate over 4 Mbit/s. In: Quantum Information and Computation IV., Presented at the

Society of Photo-Optical Instrumentation Engineers (SPIE) Conference, Vol. 6244 (2006).

DOI 10.1117/12.664455 25

23. Wegman, M.N., Carter, L.: New hash functions and their use in authentication and set equality.

J. Comput. Syst. Sci. 22(3), 265ā“279 (1981) 44

24. Xu, H., Ma, L., Mink, A., Hershman, B., Tang, X.: 1310-nm quantum key distribution system

with up-conversion pump wavelength at 1550 nm. Optics Express 15, 7247ā“7260 (2007) 26

Chapter 4

Adaptive Cascade

S. Rass and C. Kollmitzer

4.1 Introduction

Quantum cryptographic key exchange is a promising technology for future secret

transmission, which avoids computational infeasibility assumptions, while (almost)

not presuming pre-shared secrets to be available in each peerā™s machine. Never-

theless, a modest amount of pre-shared secret information is required in adjacent

link devices, but this information is only needed for authentication purposes. So

quantum key distribution cannot create keys from nothing, rather it is a method of

key expansion. The remarkable feature of quantum cryptography is its ability to

detect eavesdropping by the incident of an unnaturally high quantum bit error rate.

On the other hand, it has no defense against person-in-the-middle attacks by itself,

which is why authentication is of crucial importance.

We are particularly interested in the ļ¬nal steps of the BB84 protocol, in which

Alice and Bob correct errors in the bit strings they created from their measurements.

Key reconciliation involves Alice and Bob publicly exchanging parity bits in order

to correct errors and distill identical keys.

4.2 Error Correction and the Cascade Protocol

Coming to the core topic of this chapter, let us pay closer attention to the error

correction mechanism which has been proposed along with the experimental imple-

mentation of BB84 [2]. Errors in physical transmission media often exhibit burst

structures, that is, a sequence of consecutive errors is more likely to occur than

S. Rass (B)

System Security Research Group, Institute of Applied Informatics, Universitaet Klagenfurt,

Universitaetsstrasse 65-67, 9020 Klagenfurt, Austria, stefan.rass@uni-klu.ac.at

C. Kollmitzer

Safety & Security Department, Quantum Technologies, AIT Austrian Institute of Technology

GmbH, Lakeside B01A 9020 Klagenfurt, Austria, christian.kollmitzer@ait.ac.at;

http://www.ait.ac.at

Rass, S., Kollmitzer, C.: Adaptive Cascade. Lect. Notes Phys. 797, 49ā“69 (2010)

c Springer-Verlag Berlin Heidelberg 2010

DOI 10.1007/978-3-642-04831-9 4

50 S. Rass and C. Kollmitzer

sparse scattering. Consequently, a popular trick is to permute the bits prior to any

error correction in order to chop down long bursts into small pieces, ideally leaving

an almost uniform pattern of erroneous bits in the result. This is the ļ¬rst step in

the Cascade protocol that has been summarized in Chap. 3. After having agreed

on a publicly known permutation of bits, Alice and Bob take their shufļ¬‚ed strings

and partition it into blocks of size k, such that a single block is believed to con-

tain no more than one error with high probability. In [2], a theoretical treatment

of the optimal choice of block size is missing, and this is precisely the gap we

intend to close here. The problem of how errors are scattered across the raw key

has been tackled on statistical grounds before [17]. For this analysis, a binomial

distribution of errors within the blocks is assumed, which is later approximated by

a Poisson distribution. We shall take a different route here, considering the process

that induces the errors to be Poissonian, as well as adapting the initial block-size

ńņš. 2 |