University of Montreal, hence the name BB84, as this

protocol is now known. They presented their work at an channel at some stage of their protocol is very common

IEEE conference in India, quite unnoticed by the phys- in cryptoprotocols. This channel does not have to be

ics community at the term. This underscores the need con¬dential, only authentic. Hence any adversary Eve

for collaboration in QC between different communities, can listen to all the communication on the public chan-

with different jargons, habits, and conventions.5 The in- nel, but she cannot modify it. In practice Alice and Bob

terdisciplinary character of QC is the probable reason may use the same transmission channel to implement

for its relatively slow start, but it certainly has contrib- both the quantum and the classical channels.

uted to the rapid expansion of the ¬eld in recent years. Note that neither Alice nor Bob can decide which key

We shall explain the BB84 protocol using the lan- results from the protocol.7 Indeed, it is the conjunction

1

guage of spin 2 , but clearly any two-level quantum sys-

of both of their random choices that produces the key.

tem would do. The protocol uses four quantum states

Let us now consider the security of the above ideal

that constitute two bases, for example, the states up ‘ ,

protocol (ideal because so far we have not taken into

down “ , left ← , and right ’ . The bases are maxi-

account unavoidable noise in practice, due to technical

mally conjugate in the sense that any pair of vectors, one

imperfections). Assume that some adversary Eve inter-

from each basis, has the same overlap, e.g., ‘ ← 2

cepts a qubit propagating from Alice to Bob. This is very

1

2 . Conventionally, one attributes the binary value 0 to

easy, but if Bob does not receive an expected qubit, he

states ‘ and ’ and the value 1 to the other two

will simply tell Alice to disregard it. Hence Eve only

states, and calls the states qubits (for quantum bits). In

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

the ¬rst step, Alice sends individual spins to Bob in

not gain any useful information. For real eavesdropping

states chosen at random among the four states (in Fig. 1

the spin states ‘ , “ , ’ , and ← are identi¬ed as Eve must send a qubit to Bob. Ideally she would like to

send this qubit in its original state, keeping a copy for

the polarization states ˜˜horizontal,™™ ˜˜vertical,™™ ˜˜ 45°,™™

herself.

and ˜˜ 45°,™™ respectively). How she ˜˜chooses at ran-

dom™™ is a delicate problem in practice (see Sec. III.D),

but in principle she could use her free will. The indi-

vidual spins could be sent all at once or one after the

other (much more practical), the only restriction being

2. No-cloning theorem

that Alice and Bob be able to establish a one-to-one

correspondence between the transmitted and the re-

Following Wootters and Zurek (1982) one can easily

ceived spins. Next, Bob measures the incoming spins in

prove that perfect copying is impossible in the quantum

one of the two bases, chosen at random (using a

world (see also the anticipatory intuition of Wigner in

random-number generator independent from that of Al-

1961, as well as Dieks, 1982 and Milonni and Hardies,

ice). At this point, whenever they use the same basis,

1982). Let denote the original state of the qubit, b

they get perfectly correlated results. However, whenever

the blank copy,8 and 0 HQCM the initial state of Eve™s

they use different bases, they get uncorrelated results.

˜˜quantum copy machine,™™ where the Hilbert space

Hence, on average, Bob obtains a string of bits with a

HQCM of the quantum cloning machine is arbitrary. The

25% error rate; called the raw key. This error rate is so

high that standard error correction schemes would fail. ideal machine would produce

But in this protocol, as we shall see, Alice and Bob know

6

This terminology was introduced by Ekert and Huttner in

5

1994.

For instance, it is amusing to note that physicists strive to

7

Alice and Bob can, however, determine the statistics of the

publish in reputable journals, while conference proceedings

key.

are of secondary importance. For computer scientists, in con-

8

trast, appearance in the proceedings of the best conferences is b corresponds to the stock of white paper in an everyday

considered more important, while journal publication is sec- photocopy machine. We shall assume that the machine is not

ondary. empty, a purely theoretical assumption, as is well known.

Rev. Mod. Phys., Vol. 74, No. 1, January 2002

150 Gisin et al.: Quantum cryptography

0’ cases, since they get uncorrelated results. Altogether, if

b f, (3)

Eve uses this intercept-resend strategy, she gets 50% in-

where f denotes the ¬nal state of Eve™s machine, formation, while Alice and Bob have about a 25% error

which might depend on . Accordingly, using obvious rate in their sifted key, i.e., after they eliminate the cases

notations, in which they used incompatible states, there is still

about 25% error. They can thus easily detect the pres-

‘,b,0 ’ ‘,‘,f ‘ , (4) ence of Eve. If, however, Eve applies this strategy to

only a fraction of the communication, say 10%, then the

and error rate will be only 2.5%, while Eve™s information

will be 5%. The next section explains how Alice and

“,b,0 ’ “,“,f “ . (5) Bob can counter such attacks.

By linearity of quantum dynamics it follows that

4. Error correction, privacy ampli¬cation, and quantum

1 secret growing

’,b,0 ‘ “ ) b,0 (6)

& At this point in the BB84 protocol, Alice and Bob

share a so-called sifted key. But this key contains errors.

The errors are caused by technical imperfections, as well

1

’ ‘,‘,f ‘ “,“,f “ ). (7) as possibly by Eve™s intervention. Realistic error rates in

& the sifted key using today™s technology are of the order

of a few percent. This contrasts strongly with the 10 9

But the latter state differs from the ideal copy ’, error rate typical in optical communication. Of course,

’,f ’ , whatever the states f are. the few-percent error rate will be corrected down to the

Consequently, Eve cannot keep a perfect quantum standard 10 9 during the (classical) error correction step

copy, because perfect quantum copy machines cannot of the protocol. In order to avoid confusion, especially

exist. The possibility of copying classical information is among optical communication specialists, Beat Perny

probably one of the most characteristic features of infor- from Swisscom and Paul Townsend, then with British

mation in the everyday sense. The fact that quantum Telecommunications (BT), proposed naming the error

states, nowadays often called quantum information, can- rate in the sifted key QBER, for quantum bit error rate,

not be copied is certainly one of the most speci¬c at- to clearly distinguish it from the bit error rate (BER)

tributes that make this new kind of information so dif- used in standard communications.

ferent and hence so attractive. Actually, this negative Such a situation, in which legitimate partners share

capability clearly has its positive side, since it prevents classical information with high but not 100% correlation

Eve from perfect eavesdropping and hence makes QC and with possibly some correlation to a third party, is

potentially secure. common to all quantum cryptosystems. Actually, it is

also a standard starting point for classical information-

based cryptosystems in which one assumes that some-

3. Intercept-resend strategy

how Alice, Bob, and Eve have random variables , ,

and , respectively, with a joint probability distribution

We have seen that the eavesdropper needs to send a

P( , , ). Consequently, the last step in a QC protocol

qubit to Bob while keeping a necessarily imperfect copy

uses classical algorithms, ¬rst to correct the errors, and

for herself. How imperfect the copy has to be, according

then reduce to Eve™s information on the ¬nal key, a pro-

to quantum theory, is a delicate problem that we shall

cess called privacy ampli¬cation.

address in Sec. VI. Here, let us develop a simple eaves-

The ¬rst mention of privacy ampli¬cation appeared in

dropping strategy, called intercept-resend. This simple

Bennett, Brassard, and Robert (1988). It was then ex-

and even practical attack consists of Eve™s measuring

´

tended in collaboration with C. Crepeau from the Uni-

each qubit in one of the two bases, precisely as Bob

¨

versity of Montreal and U. Maurer of ETH, Zurich, re-

does. Then, she resends to Bob another qubit in the

spectively (Bennett, Brassard, et al. 1995; see also

state corresponding to her measurement result. In about

Bennett, Bessette, et al., 1992). Interestingly, this work

half of the cases, Eve will be lucky and choose the basis

motivated by QC found applications in standard

compatible with the state prepared by Alice. In these

information-based cryptography (Maurer, 1993; Maurer

cases she resends to Bob a qubit in the correct state, and

and Wolf, 1999).

Alice and Bob will not notice her intervention. How-

Assume that a joint probability distribution P( , , )

ever, in the other half of the cases, Eve unluckily uses

exists. Near the end of this section, we shall comment on

the basis incompatible with the state prepared by Alice.

this assumption. Alice and Bob have access only to the

This necessarily happens, since Eve has no information

marginal distribution P( , ). From this and from the

about Alice™s random-number generator (hence the im-

laws of quantum mechanics, they have to deduce con-

portance of this generator™s being truly random). In

straints on the complete scenario P( , , ); in particu-

these cases the qubits sent out by Eve are in states with

1

lar they have to bound Eve™s information (see Secs. VI.E

an overlap of 2 with the correct states. Alice and Bob

and VI.G). Given P( , , ), necessary and suf¬cient

thus discover her intervention in about half of these

Rev. Mod. Phys., Vol. 74, No. 1, January 2002

151

Gisin et al.: Quantum cryptography

conditions for a positive secret-key rate between Alice Actually, the above scenario is incomplete. In this pre-

sentation, we have assumed that Eve measures her

and Bob, S( , ), are not yet known. However, a use-

probe before Alice and Bob run the error correction and

ful lower bound is given by the difference between Alice

privacy ampli¬cation algorithms, hence that P( , , )

and Bob™s mutual Shannon information I( , ) and

exists. In practice this is a reasonable assumption, but in

´ ¨

Eve™s mutual information (Csiszar and Korner, 1978, and

principle Eve could wait until the end of all the proto-

Theorem 1 in Sec. VI.G):

cols and then optimize her measurements accordingly.

S , max I , I , ,I , I , . (8) Such ˜˜delayed-choice eavesdropping strategies™™9 are

discussed in Sec. VI.

Intuitively, this result states that secure-key distillation

It should by now be clear that QC does not provide a

(Bennett, Bessette, et al., 1992) is possible whenever

complete solution for all cryptographic purposes.10 Ac-

Bob has more information than Eve.

tually, quite the contrary, QC can only be used as a

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

complement to standard symmetrical cryptosystems. Ac-

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

cordingly, a more precise name for QC is quantum key

cation, secret-key agreement might be possible even

distribution, since this is all QC does. Nevertheless, we

when condition (8) is not satis¬ed (see Sec. II.C.5).

prefer to keep the well-known terminology, which lends

Without discussing any algorithm in detail, let us offer

its name to the title of this review.

some idea of how Alice and Bob can establish a secret

Finally, let us emphasize that every key distribution

key when condition (8) is satis¬ed. First, once the sifted

system must incorporate some authentication scheme:

key is obtained (i.e., after the bases have been an-

the two parties must identify themselves. If not, Alice

nounced), Alice and Bob publicly compare a randomly

could actually be communicating directly with Eve. A

chosen subset of it. In this way they estimate the error

straightforward approach is for Alice and Bob initially

rate [more generally, they estimate their marginal prob-

to share a short secret. Then QC provides them with a

ability distribution P( , )]. These publicly disclosed

longer one and they each keep a small portion for au-

bits are then discarded. Next, either condition (8) is not

thentication at the next session (Bennett, Bessette, et al.,

satis¬ed and they stop the protocol or condition (8) is

1992). From this perspective, QC is a quantum secret-

satis¬ed and they use some standard error correction

growing protocol.

protocol to get a shorter key without errors.

With the simplest error correction protocol, Alice ran-

domly chooses pairs of bits and announces their XOR 5. Advantage distillation

value (i.e., their sum modulo 2). Bob replies either ˜˜ac-

QC has motivated and still motivates research in clas-

cept™™ if he has the same XOR value for his correspond-

sical information theory. The best-known example is

ing bits, or ˜˜reject™™ if not. In the ¬rst case, Alice and

probably the development of privacy ampli¬cation algo-

Bob keep the ¬rst bit of the pair and discard the second

rithms (Bennett et al., 1988, 1995). This in turn led to the

one, while in the second case they discard both bits. In

development of new cryptosystems based on weak but

reality, more complex and ef¬cient algorithms are used.

classical signals, emitted for instance by satellites (Mau-

After error correction, Alice and Bob have identical

rer, 1993).11 These new developments required secret-

copies of a key, but Eve may still have some information

key agreement protocols that could be used even when

about it [compatible with condition (8)]. Alice and Bob

condition (8) did not apply. Such protocols, called ad-

thus need to reduce Eve™s information to an arbitrarily

vantage distillation, necessarily use two-way communica-

low value using some privacy ampli¬cation protocols.

tion and are much less ef¬cient than privacy ampli¬ca-

These classical protocols typically work as follows. Alice

tion. Usually, they are not considered in the literature on

again randomly chooses pairs of bits and computes their

QC, but conceptually they are remarkable from at least

XOR value. But, in contrast to error correction, she

two points of view. First, it is somewhat surprising that

does not announce this XOR value. She only announces

secret-key agreement is possible even if Alice and Bob

which bits she chose (e.g., bits number 103 and 537).

start with less mutual (Shannon) information than Eve.

Alice and Bob then replace the two bits by their XOR

They can take advantage of the authenticated public

value. In this way they shorten their key while keeping it

error free, but if Eve has only partial information on the

two bits, her information on the XOR value is even less.

9

Assume, for example, that Eve knows only the value of Note, however, that Eve has to choose the interaction be-

tween her probe and the qubits before the public discussion

the ¬rst bit and nothing about the second one. Then she

phase of the protocol.

has no information at all about the XOR value. Also, if 10

For a while it was thought that bit commitment (see, for

Eve knows the value of both bits with 60% probability,

example, Brassard, 1988), a powerful primitive in cryptology,

then the probability that she correctly guesses the XOR

could be realized using quantum principles. However, Dominic

value is only 0.62 0.42 52%. This process would have

Mayers (1996a, 1997) and Lo and Chau (1998) proved it to be

to be repeated several times; more ef¬cient algorithms impossible (see also Brassard et al., 1998).

use larger blocks (Brassard and Salvail, 1994). 11

Note that here con¬dentiality is not guaranteed by the laws

The error correction and privacy ampli¬cation algo- of physics, but relies on the assumption that Eve™s technology

rithms sketched above are purely classical algorithms. is limited, e.g., her antenna is ¬nite, and her detectors have

This illustrates that QC is a truly interdisciplinary ¬eld. limited ef¬ciencies.

Rev. Mod. Phys., Vol. 74, No. 1, January 2002

152 Gisin et al.: Quantum cryptography

channel to decide which series of realizations to keep,

whereas Eve cannot in¬‚uence this process12 (Maurer,

1993; Maurer and Wolf, 1999).

Recently, a second remarkable feature of advantage

distillation, connecting quantum and classical secret-key

agreement, has been discovered (assuming one uses the

Ekert protocol described in Sec. II.D.3): If Eve follows a

strategy that optimizes her Shannon information, under

the assumption that she attacks the qubits one at a time

(the so-called individual attack; see Sec. VI.E), then Al-

ice and Bob can use advantage distillation if and only if

Alice and Bob™s qubits are still entangled (they can thus ´

FIG. 2. Poincare sphere with a representation of six states that

use quantum privacy ampli¬cation; Deutsch et al., 1996; can be used to implement the generalization of the BB84 pro-

Gisin and Wolf, 1999). This connection between the con- tocol.

cept of entanglement, central to quantum information

theory, and the concept of intrinsic classical information,

bright pulse and a dim pulse with less than one photon

central to classical information-based cryptography

on average (Bennett, 1992). The presence of the bright

(Maurer and Wolf, 1999), has been shown to be general

pulse makes this protocol especially resistant to eaves-

(Gisin and Wolf, 2000). The connection seems to extend

dropping, even in settings with high attenuation. Bob

even to bound entanglement (Gisin et al., 2000).

can monitor the bright pulses to make sure that Eve

does not remove any. In this case, Eve cannot eliminate

D. Other protocols the dim pulse without revealing her presence, because

the interference of the bright pulse with vacuum would

1. Two-state protocol introduce errors. A practical implementation of this so-

called 892 protocol is discussed in Sec. IV.D. Huttner

In 1992 Bennett noticed that four states are more than

et al. extended this reference-beam monitoring to the

are really necessary for QC: only two nonorthogonal

four-state protocol in 1995.

states are needed. Indeed the security of QC relies on

the inability of an adversary to distinguish unambigu-

ously and without perturbation between the different 2. Six-state protocol

states that Alice may send to Bob; hence two states are

While two states are enough and four states are stan-

necessary, and if they are incompatible (i.e., not mutu-

dard, a six-state protocol better respects the symmetry

ally orthogonal), then two states are also suf¬cient (Ben-

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

nett, 1992). This is a conceptually important clari¬ca-

Bechmann-Pasquinucci and Gisin, 1999). The six states

tion. It also made several of the ¬rst experimental

constitute three bases, hence the probability that Alice

demonstrations easier (as is discussed further in Sec. 1

and Bob choose the same basis is only 3 , but the sym-

IV.D). But in practice, it is not a good solution. Indeed,

metry of this protocol greatly simpli¬es the security

although two nonorthogonal states cannot be distin-

analysis and reduces Eve™s optimal information gain for

guished unambiguously without perturbation, one can

a given error rate QBER. If Eve measures every photon,

unambiguously distinguish between them at the cost of

the QBER is 33%, compared to 25% in the case of the

some losses (Ivanovic, 1987; Peres, 1988). This possibil-

BB84 protocol.

ity has been demonstrated in practice (Huttner, Gautier,

et al., 1996; Clarke et al., 2000). Alice and Bob would

3. Einstein-Podolsky-Rosen protocol

have to monitor the attenuation of the quantum channel

(and even this would not be entirely safe if Eve were

This variation of the BB84 protocol is of special con-

able to replace the channel by a more transparent one;

ceptual, historical, and practical interest. The idea is due

see Sec. VI.H). The two-state protocol can also be

to Artur Ekert (1991) of Oxford University, who, while

implemented using interference between a macroscopic

elaborating on a suggestion of David Deutsch (1985),

discovered QC independently of the BB84 paper. Intel-

lectually, it is very satisfying to see this direct connection

12

The idea is that Alice picks out several instances in which to the famous EPR paradox (Einstein, Podolski, and

she got the same bit and communicates the instances”but not Rosen, 1935): the initially philosophical debate turned to

the bit”to Bob. Bob replies yes only if it happens that for all theoretical physics with Bell™s inequality (1964), then to

these instances he also has the same bit value. For high error

experimental physics (Freedmann and Clauser, 1972; Fry

rates this is unlikely, but when it does happen there is a high

and Thompson, 1976; Aspect et al., 1982), and is now”

probability that both have the same bit. Eve cannot in¬‚uence

thanks to Ekert™s ingenious idea”part of applied phys-

the choice of the instances. All she can do is use a majority

ics.

vote for the cases accepted by Bob. The probability that Eve

The idea consists in replacing the quantum channel

makes an error can be much higher than the probability that

carrying two qubits from Alice to Bob by a channel car-

Bob makes an error (i.e., that all his instances are wrong), even

rying two qubits from a common source, one qubit to

if Eve has more initial information than Bob.

Rev. Mod. Phys., Vol. 74, No. 1, January 2002

153

Gisin et al.: Quantum cryptography

FIG. 3. Einstein-Podolsky-Rosen (EPR) protocol, with the

´

source and a Poincare representation of the four possible

states measured independently by Alice and Bob.

Alice and one to Bob. A ¬rst possibility would be that

the source always emits the two qubits in the same state

chosen randomly among the four states of the BB84 pro-

tocol. Alice and Bob would then both measure their qu-

bit in one of the two bases, again chosen independently FIG. 4. Illustration of protocols exploiting EPR quantum sys-

and randomly. The source then announces the bases, tems. To implement the BB84 quantum cryptographic proto-