Let us now consider the security of the above ideal new kind of information so di¬erent, hence so attractive.

protocol (ideal because so far we did not take into ac- Actually, this “negative rule” has clearly its positive side,

count unavoidable noise due to technical imperfections). since it prevents Eve from perfect eavesdropping, and

Assume that some adversary Eve intercepts a qubit prop- hence makes QC potentially secure.

agating from Alice to Bob. This is very easy, but if Bob

does not receive an expected qubit, he will simply inform

Alice to disregard it. Hence, in this way Eve only lowers 3. Intercept-resend strategy

the bit rate (possibly down to zero), but she does not

gain any useful information. For real eavesdropping Eve We have seen that the eavesdropper needs to send a

must send a qubit to Bob. Ideally she would like to send qubit to Bob, while keeping a necessarily imperfect copy

this qubit in its original state, keeping a copy for herself. for herself. How imperfect the copy has to be, accord-

ing to quantum theory, is a delicate problem that we

shall address in chapter VI. Here, let us develop a sim-

2. No cloning theorem ple eavesdropping strategy, called intercept-resend. This

simple and even practical attack consists in Eve measur-

Following Wootters and Zurek (1982) it is easy to prove ing each qubit in one of the two basis, precisely as Bob

that perfect copying is impossible in the quantum world does. Then, she resends to Bob another qubit in the

(see also Milonni and Hardies 1982, Dieks 1982, and the state corresponding to her measurement result. In about

anticipating intuition by Wigner in 1961). Let ψ denote half of the cases Eve will be lucky and choose the basis

the original state of the qubit, |b the blank copy8 and compatible with the state prepared by Alice. In these

denote |0 ∈ HQCM the initial state of Eve™s “quantum cases she resends to Bob a qubit in the correct state and

copy machine”, where the Hilbert space HQCM of the Alice and Bob won™t notice her intervention. However, in

quantum cloning machine is arbitrary. The ideal machine the other 50% cases, Eve unluckily uses the basis incom-

would produce: patible with the state prepared by Alice. This necessarily

happens, since Eve has no information on Alice™s random

ψ — |b — |0 ’ ψ — ψ — |fψ (3) generator (hence the importance that this generator is

truly random). In these cases the qubits sent out by Eve

where |fψ denotes the ¬nal state of Eve™s machine which 1

are in states with overlap 2 with the correct states. Al-

might depend on ψ. Accordingly, using obvious nota- ice and Bob discover thus her intervention in about half

tions, of these cases, since they get uncorrelated results. Alto-

gether, if Eve uses this intercept-resend strategy, she gets

| ‘, b, 0 ’ | ‘, ‘, f‘ (4) 50% information, while Alice and Bob have about 25%

and | “, b, 0 ’ | “, “, f“ . (5) of errors in their sifted key, i.e. after they eliminated the

cases in which they used incompatible states, there are

By linearity of quantum dynamics it follows that still about 25% errors. They can thus easily detect the

presence of Eve. If, however, Eve applies this strategy to

1

| ’, b, 0 = √ (| ‘ + | “ ) — |b, 0 only a fraction of the communication, 10% let™s say, then

(6)

2 the error rate will be only ≈2.5% while Eve™s information

1 would be ≈5%. The next section explains how Alice and

’ √ (| ‘, ‘, f‘ + | “, “, f“ ). (7)

Bob can counter such attacks.

2

4. Error correction, privacy ampli¬cation and quantum

7 secret growing

Alice and Bob can however determine the statistics of the

key.

8

|b corresponds to the stock of white paper in everyday™s At this point in the BB84 protocol, Alice and Bob

photocopy machine. We shall assume that exceptionally this share a so-called sifted key. But this key contains errors.

stock is not empty, a purely theoretical assumption, as is well The errors are caused as well by technical imperfections,

known.

6

as possibly by Eve™s intervention. Realistic error rates Without discussing any algorithm in detail, let us give

on the sifted key using today™s technology are of a few some intuition how Alice and Bob can establish a se-

percent. This contrasts strongly with the 10’9 typical in cret key when condition (8) is satis¬ed. First, once the

optical communication. Of course, the few percent errors sifted key is obtained (i.e. after the bases have been an-

will be corrected down to the standard 10’9 during the nounced), Alice and Bob publicly compare a randomly

(classical) error correction step of the protocol. In order chosen subset of it. In this way they estimate the error

to avoid confusion, especially among the optical commu- rate (more generally, they estimate their marginal prob-

nication specialists, Beat Perny from Swisscom and Paul ability distribution P (±, β)). These publicly disclosed

Townsend, then with BT, proposed to name the error bits are then discarded. Next, either condition (8) is not

rate on the sifted key QBER, for Quantum Bit Error satis¬ed and they stop the protocol. Or condition (8)

Rate, to make it clearly distinct from the BER used in is satis¬ed and they use some standard error correction

standard communications. protocol to get a shorter key without errors.

Such a situation where the legitimate partners share With the simplest error correction protocol, Alice ran-

classical information, with high but not 100% correla- domly chooses pairs of bits and announces their XOR

tion and with possibly some correlation to a third party value (i.e. their sum modulo 2). Bob replies either “ac-

is common to all quantum cryptosystems. Actually, it cept” if he has the same XOR value for his corresponding

is also a standard starting point for classical information bits, or “reject” if not. In the ¬rst case, Alice and Bob

based cryptosystems where one assumes that somehow keep the ¬rst bit of the pair and eliminate the second one,

Alice, Bob and Eve have random variables ±, β and «, re- while in the second case they eliminate both bits. In re-

spectively, with joint probability distribution P (±, β, «). ality, more complex and e¬cient algorithms are used.

Consequently, the last step in a QC protocol uses classi- After error correction, Alice and Bob have identical

cal algorithms, ¬rst to correct the errors, next to lower copies of a key, but Eve may still have some information

Eve™s information on the ¬nal key, a process called pri- about it (compatible with condition (8)). Alice and Bob

thus need to lower Eve™s information down to an arbitrar-

vacy ampli¬cation.

The ¬rst mention of privacy ampli¬cation appears in ily low value using some privacy ampli¬cation protocols.

Bennett, Brassard and Robert (1988). It was then ex- These classical protocols typically work as follows. Alice

tended in collaboration with C. Cr´peau and U. Maurer

e again randomly choses pairs of bits and computes their

from the University of Montreal and the ETH Z¨ rich, re-

u XOR value. But, contrary to error correction she does

spectively (Bennett et al. 1995, see also Bennett et al. not announce this XOR value. She only announces which

1992a). Interestingly, this work motivated by QC found bits she chose (e.g. bit number 103 and 537). Alice and

applications in standard information-based cryptography Bob then replace the two bits by their XOR value. In

(Maurer 1993, Maurer and Wolf 1999). this way they shorten their key while keeping it error

Assume that such a joint probability distribution free, but if Eve has only partial information on the two

P (±, β, «) exists. Near the end of this section, we com- bits, her information on the XOR value is even lower.

ment on this assumption. Alice and Bob have access only Consider for example that Eve knows only the value of

to the marginal distribution P (±, β). From this and from the ¬rst bit, and nothing about the second one. Then

the laws of quantum mechanics, they have to deduce con- she has no information at all on the XOR value. Also, if

straints on the complete scenario P (±, β, «), in particular Eve knows the value of both bits with 60% probability,

they have to bound Eve™s information (see sections VI E then the probability that she guesses correctly the value

of the XOR is only of 0.62 + 0.42 = 52%. This process

and VI G). Given P (±, β, «), necessary and su¬cient con-

ditions for a positive secret key rate between Alice and would have to be repeated several times; more e¬cient

Bob, S(±, β||«), are not yet known. However, a useful algorithms use larger blocks (Brassard and Salvail 1993).

lower bound is given by the di¬erence between Alice and The error correction and privacy ampli¬cation algo-

Bob™s mutual Shannon information I(±, β) and Eve™s mu- rithms sketched above are purely classical algorithms.

tual information (Csisz´r and K¨rner 1978, and theorem

a o This illustrates that QC is a truly interdisciplinary ¬eld.

1 in section VI G): Actually, the above presentation is incomplete. Indeed,

in this presentation, we have assumed that Eve has mea-

S(±, β||«) ≥ max{I(±, β) ’ I(±, «), I(±, β) ’ I(β, «)} sured her probe before Alice and Bob run the error cor-

rection and privacy ampli¬cation algorithms, hence that

(8)

P (±, β, «) exists. In practice this is a very reasonable

assumption, but, in principle, Eve could wait until the

Intuitively, this result states that secure key distillation

end of all the protocol, and then optimize her measure-

(Bennett et al. 1992a) is possible whenever Bob has more

ments accordingly. Such “delayed choice eavesdropping

information than Eve.

The bound (8) is tight if Alice and Bob are restricted

to one-way communication, but for two-way communica-

tion, secret key agreement might be possible even when

(8) is not satis¬ed (see next paragraph II C 5).

7

strategies9 ” are discussed in chapter VI. tion to keep, whereas Eve can™t in¬‚uence this process12

It should now be clear that QC does not provide a (Maurer 1993, Maurer and Wolf 1999).

complete solution for all cryptographic purposes10 . Ac- Recently a second remarkable connection between

tually, quite on the contrary, QC can only be used as quantum and classical secret key agreement has been dis-

a complement to standard symmetrical cryptosystems. covered (assuming they use the Ekert protocol described

Accordingly, a more precise name for QC is Quantum in paragraph II D 3): If Eve follows the strategy which op-

Key Distribution, since this is all QC does. Nevertheless, timizes her Shannon information, under the assumption

we prefer to keep the well known terminology which gives that she attacks the qubit one at a time (the so-called

its title to this review. individual attacks, see section VI E), then Alice and Bob

Finally, let us emphasize that every key distribution can use advantage distillation if and only if Alice and

system must incorporate some authenti¬cation scheme: Bob™s qubits are still entangled (they can thus use quan-

the two parties must identify themselves. If not, Alice tum privacy ampli¬cation (Deutsch et al. 1996)) (Gisin

could actually be communicating directly with Eve! A and Wolf 1999). This connection between the concept

straightforward possibility is that Alice and Bob initially of entanglement, central to quantum information theory,

share a short secret. Then QC provides them with a and the concept of intrinsic classical information, cen-

longer one and, for example, they each keep a small por- tral to classical information based cryptography (Maurer

tion for authenti¬cation at the next session (Bennett et and Wolf 1999), has been shown to be general (Gisin

al. 1992a). From this perspective, QC is a Quantum and Wolf 2000). The connection seems even to extend to

Secret Growing protocol. bound entanglement (Gisin et al. 2000).

5. Advantage distillation D. Other protocols

QC has triggered and still triggers research in classical 1. 2-state protocol

information theory. The best known example is proba-

bly the development of privacy ampli¬cation algorithms In 1992 Charles H. Bennett noticed that actually 4

(Bennett et al. 1988 and 1995). This in turn triggered states is more than necessary for QC: all what is really

the development of new cryptosystems based on weak but needed is 2 nonorthogonal states. Indeed the security re-

classical signals, emitted for instance by satellites (Mau- lies on the impossibility for any adversary to distinguish

rer 1993)11. These new developments required secret key unambiguously and without perturbation between the

agreement protocols that can be used even when the con- di¬erent states that Alice may send to Bob, hence 2 states

dition (8) doesn™t apply. Such protocols, called advantage are necessary and if they are incompatible (i.e. not mutu-

distillation, necessarily use two way communication and ally orthogonal), then 2 states are also su¬cient. This is

are much less e¬cient than privacy ampli¬cation. Usu- a conceptually important clari¬cation. It also made sev-

ally, they are not considered in the literature on QC. eral of the ¬rst experimental demonstrations easier (this

But, conceptually, they are remarkable from at least two is further discussed in section IV D). But in practice it

points of view. First it is somewhat surprising that se- is not a good solution. Indeed, although 2 nonorthogo-

cret key agreement is possible even if Alice and Bob start nal states can™t be distinguished unambiguously without

with less mutual (Shannon) information than Eve. How- perturbation, one can unambiguously distinguish them

ever, they can take advantage of the authenticated public at the cost of some losses (Ivanovic 1987, Peres 1988).

channel: Alice and Bob can decide which series of realiza- This possibility has even been demonstrated in practice

(Huttner et al. 1996, Clarke et al. 2000). Hence, Alice

and Bob would have to monitor the attenuation of the

9

Note however that Eve has to choose the interaction be-

tween her probe and the qubits before the public discussion

phase of the protocol. 12

The idea is that Alice picks out several instances where she

10

For a while it was thought that bit commitment (see, e.g., got the same bit and communicates the instances - but not

Brassard 1988), a powerful primitive in cryptology, could be the bit - to Bob. Bob replies yes only if it happens that for all

realized using quantum principles. However, Dominic Mayers these instances he also has the same bit value. For large error

(1996a and 1997) and Lo and Chau (1998) proved it to be rates this is unlikely, but when it happens there is a large

impossible (see also Brassard et al. 1998). chance that both have the same bit. Eve can™t in¬‚uence the

11

Note that here the con¬dentiality is not guaranteed by choice of the instances. All she can do is to use a majority

the laws of physics, but relies on the assumption that Eve™s vote for the cases accepted by Bob. The probability that Eve

technology is limited, e.g. her antenna is ¬nite, her detectors makes an error can be much larger than the probability that

have limited e¬ciencies. Bob makes an error (i.e. that all his instances are wrong),

even if Eve™s initial information is larger than Bob™s.

8

quantum channel (and even this is not entirely safe if Eve keep the data only when they happen to have done their

could replace the channel by a more transparent one, see measurements in the compatible basis. If the source is

section VI H). The two-state protocol can also be im- reliable, this protocol is equivalent to the BB84 one: Ev-

plemented using an interference between a macroscopic ery thing is as if the qubit propagates backwards in time

bright pulse and a dim pulse with less than one photon on from Alice to the source, and then forwards to Bob! But

average (Bennett, 1992). The presence of the bright pulse better than trusting the source, which could be in Eve™s

makes this protocol specially resistant to eavesdropping, hand, the Ekert protocol assumes that the 2 qubits are

even in settings with high attenuation. Indeed Bob can emitted in a maximally entangled state like:

monitor the bright pulses, to make sure that Eve does not

1

remove any. In this case, Eve cannot eliminate the dim φ+ = √ (| ‘, ‘ + | “, “ ). (9)

2

pulse without revealing her presence, because the inter-

ference of the bright pulse with vacuum would introduce

Then, when Alice and Bob happen to use the same basis,

errors. A practical implementation of this protocol is

both the x-basis or both the y-basis, i.e. in about half

discussed in section IV D. Huttner et al. extended this

of the cases, their results are identical, providing them

reference beam monitoring to the four-states protocol in

with a common key. Note the similarity between the 1-

1995.

qubit BB84 protocol illustrated in Fig. 1 and the 2-qubit

Ekert protocol of Fig. 3. The analogy can be even made

stronger by noting that for all unitary evolutions U1 and

2. 6-state protocol

U2 , the following equality hold:

While two states are enough and four states are stan- U1 — U2 ¦(+) = 1 — U2 U1 ¦(+)

t

1 (10)

dard, a 6-state protocol respects much more the sym-

metry of the qubit state space, see Fig. 2 (Bruss 1998, t

where U1 denotes the transpose.

Bechmann-Pasquinucci and Gisin 1999). The 6 states In his 1991 paper Artur Ekert suggested to base the

constitute 3 bases, hence the probability that Alice and security of this 2-qubit protocol on Bell™s inequality, an

1

Bob chose the same basis is only of 3 . But the symme- inequality which demonstrates that some correlation pre-

try of this protocol greatly simpli¬es the security anal- dicted by quantum mechanics can™t be reproduced by

ysis and reduces Eve™s optimal information gain for a any local theory (Bell 1964). For this, Alice and Bob

given error rate QBER. If Eve measures every photon, have a third choice of basis (see Fig. 4). In this way the

the QBER is 33%, compared to 25% in the case of the probability that they happen to choose the same basis

BB84 protocol. is reduced from 2 to 2 , but at the same time as they

1

9

establish a key they collect enough data to test Bell in-

equality13 . They can thus check that the source really

3. EPR protocol emits the entangled state (9) and not merely product

states. The following year Bennett, Brassard and Mer-

This variation of the BB84 protocol is of special con- min (1992b) criticized Ekert™s letter, arguing that the

ceptual, historical and practical interest. The idea is due violation of Bell inequality is not necessary for the secu-

to Artur Ekert (1991) from Oxford University, who, while rity of QC and emphasizing the close connection between

elaborating on a suggestion of David Deutsch (1985), dis- the Ekert and the BB84 schemes. This criticism might

covered QC independently of the BB84 paper. Intellec- be missing an important point. Indeed, although the ex-

tually, it is very satisfactory to see this direct connec- act relation between security and Bell inequality is not

tion to the famous EPR paradox (Einstein, Podolski and yet fully known, there are clear results establishing fasci-

Rosen 1935): the initially philosophical debate turned to nating connections, (see section VI F). In October 1992,

theoretical physics with Bell™s inequality (1964), then to an article by Bennett, Brassard and Ekert demonstrated

experimental physics (Freedmann and Clauser 1972, Fry that the founding fathers joined forces to develop the ¬eld

and Thompson 1976, and Aspect, Dalibard and Roger in a pleasant atmosphere (Bennett et al. 1992c)!

1982), and is now “ thanks to Ekert™s ingenious idea “

part of applied physics.

The idea consists in replacing the quantum channel

carrying qubits from Alice to Bob by a channel carrying

2 qubits from a common source, one qubit to Alice and

one to Bob. A ¬rst possibility would be that the source 13

A maximal violation of Bell inequality is necessary to rule

emits the two qubits always in the same state chosen ran- out tampering by Eve. In this case, the QBER must nec-

domly among the 4 states of the BB84 protocol. Alice essarily be equal to zero. With a non-maximal violation, as

and Bob would then both measure their qubit in one of typically obtained in experimental systems, Alice and Bob

the two bases, again chosen independently and randomly. can distil a secure key using error correction and privacy

The source then announces the bases and Alice and Bob ampli¬cation.

9

tem is destroyed without Alice learning anything about

4. Other variations

the quantum state, while Bob™s qubit ends in a state

isomorphic to the state of the original system (but Bob

There is a large collection of variations around the

doesn™t learn anything about the quantum state). If the

BB84 protocol. Let us mention a few, chosen somewhat

initial quantum system is a quantum message coded in

arbitrarily. First, one can assume that the two bases

the form of a sequence of qubits, then this quantum mes-

are not chosen with equal probability (Ardehali et al.

sage is faithfully and securely transferred to Bob, without

1998). This has the nice consequence that the proba-

any information leaking to the outside world (i.e. to any-

bility that Alice and Bob choose the same basis is larger

one not sharing the prior entanglement with Alice and

1

than 2 , increasing thus the transmission rate of the sifted

Bob). Finally, the quantum message could be formed of

key. However, this protocol makes Eve™s job easier as she

a 4 letter quantum alphabet constituted by the 4 states

is more likely to guess correctly the used basis. Conse-

of the BB84 protocol. With futuristic, but not impossi-

quently, it is not clear whether the ¬nal key rate, after

ble technology, Alice and Bob could have their entangled

error correction and privacy ampli¬cation, is higher or

qubits in appropriate wallets and could establish a totally

not.

secure communication at any time, without even having

Another variation consists in using quantum systems of

to know where the partner is located (provided they can

dimension larger than 2 (Bechmann-Pasquinucci and Tit-

communicate classically).

tel 2000, Bechmann-Pasquinucci and Peres 2000, Bouren-

nane et al. 2001a). Again, the practical value of this idea

has not yet been fully determined.

F. Optical ampli¬cation, quantum nondemolition

A third variation worth mentioning is due to Gold-

measurements and optimal quantum cloning

enberg and Vaidman, from Tel-Aviv University (1995).

They suggested to prepare the qubits in a superposition

After almost every general talk on QC, two questions

of two spatially separated states, then to send one compo-

arise: what about optical ampli¬ers? and what about

nent of this superposition and to wait until Bob received

quantum nondemolition measurements? In this section

it before sending the second component. This doesn™t

we brie¬‚y address these questions.

sound of great practical value, but has the nice concep-

Let us start with the second one, being the easiest. The

tual feature that the minimal two states do not need to

terminology “quantum nondemolition measurement” is

be mutually orthogonal.

simply a confusing one! There is nothing like a quan-

tum measurement that does not perturb (i.e. modify)

the quantum state, except if the state happens to be an

E. Quantum teleportation as “Quantum

eigenstate of the observable. Hence, if for some reason

one-time-pad”

one conjectures that a quantum system is in some state

(or in a state among a set of mutually orthogonal ones),

Since its discovery in 1993 by a surprisingly large

this can be in principle tested repeatedly (Braginsky and

group of physicists, Quantum teleportation (Bennett et

Khalili 1992). But if the state is only restricted to be in

al. 1993) received a lot of attention in the scienti¬c com-

a ¬nite set containing non-orthogonal states, as in QC,

munity as well as in the general public. The dream of

then there is no way to perform a measurement without

beaming travellers through the Universe is exciting, but

“demolishing” (perturbing) the state. Now, in QC the

completely out of the realm of any foreseeable technol-

terminology “nondemolition measurement” is also used

ogy. However, quantum teleportation can be seen as the

with a di¬erent meaning: one measures the number of

fully quantum version of the one-time-pad, see paragraph

photons in a pulse without a¬ecting the degree of free-

II B 3, hence as the ultimate form of QC. Similarly to

dom coding the qubit (e.g. the polarization), (see section

“classical teleportation”, let™s assume that Alice aims at

VI H), or one detects the presence of a photon without

transferring to Bob a faithful copy of a quantum system.

destroying it (Nogues et al. 1999). Such measurements

If Alice has full knowledge of the quantum state, the

are usually called “ideal measurements”, or “projective

problem is not really a quantum one (Alice information

measurements”, because they produce the least possible

is classical). If, on the opposite, Alice does not know the

perturbation (Piron 1990) and because they can be repre-

quantum state, she cannot send a copy, since quantum

sented by projectors. It is important to stress that these

copying is impossible according to quantum physics (see

“ideal measurements” do not invalidate the security of

paragraph II C 2). Nor can she send classical instructions,

QC.

since this would allow the production of many copies.

Let us consider now optical ampli¬ers (a laser medium,

However, if Alice and Bob share arbitrarily many entan-

but without mirrors, so that ampli¬cation takes place in

gled qubits, sometimes called a quantum key, and share a

a single pass, see Desurvire 1994). They are widely used

classical communication channel then the quantum tele-

in today™s optical communication networks. However,

portation protocol provides them with a mean to transfer

they are of no use for quantum communication. Indeed,

the quantum state of the system from Alice to Bob. In

as seen in section II C, the copying of quantum informa-

the course of running this protocol, Alice™s quantum sys-

tion is impossible. Here we illustrate this characteristic

10

1

2P‘‘ + Pψ(+) 2P‘ + 2 1

1

of quantum information with the example of optical am-

T r1’ph mode = (21)

pli¬ers: the necessary presence of spontaneous emission 3 3

whenever there is stimulated emission, prevents perfect

The corresponding ¬delity is:

copying. Let us clarify this important and often confus-

ing point, following the work of Simon et al. (1999 and 1

2+ 5

2000; see also Kempe et al. 2000, and De Martini et al. 2

F= = (22)

3 6

2000). Let the two basic qubit states |0 and |1 be physi-

cally implemented by two optical modes: |0 ≡ |1, 0 and

which is precisely the optimal ¬delity compatible with

|1 ≡ |0, 1 . |n, m ph — |k, l a denotes thus the state of

quantum mechanics (Buˇek and Hillery 1996, Bruss et

z

n photons in mode 1 and m in mode 2, and k, l = 0 (1)

al 1998, Gisin and Massar 1997). In other words, if we

the ground (excited) state of 2-level atoms coupled to

start with a single photon in an arbitrary state, and pass

mode 1 and 2, respectively. Hence spontaneous emission

it through an ampli¬er, then due to the e¬ect of sponta-

corresponds to

neous emission the ¬delity of the state exiting the ampli-

¬er, in the cases where it consists of exactly two photons,

|0, 0 — |1, 0 ’ |1, 0 — |0, 0 a , (11)

ph a ph

with the initial state will be equal to at most 5/6. Note