ńņš. 10 |

ā“) (52)

ā“

then the state of the qubit received by Bob is given by

ā’ ā

the density matrix obtained by tracing out Eveā™s probe: ā’, (53)

ā’

TrHEve U m ,0 m ,0 U ā .

m (45) where

Bob

1

The symmetry of the BB84 protocol makes it very natu-

, (54)

ā’ ā‘ ā‘ ā“ ā“

ral to assume that Bobā™s state is related to Aliceā™s m by 2

a simple shrinking factor50 0,1 (see Fig. 29):

1

1 m . (55)

ā’ ā‘ ā‘ ā“ ā“

2

m . (46)

Bob

2

Similarly,

Eavesdropping attacks that satisfy the above condition

1

are called symmetric-attacks.

, (56)

ā ā‘ ā‘ ā“ ā“

Since the qubit state space is two dimensional, the 2

unitary operator is entirely determined by its action on

1

two states, for example, the ā‘ and ā“ states (in this . (57)

ā ā‘ ā‘ ā“ ā“

1

2

section we use spin- 2 notation for the qubits). After the

unitary interaction, it is convenient to write the states in Condition (46) for the ā’ , ā basis implies that

the Schmidt form (Peres, 1997):

ā’ and ā ā . By proper choice of the phases,

ā’

U ā‘,0 ā‘ ā“ ā‘ ā“ can be made real. By condition (49), ā“ is

ā‘, (47) ā‘

ā‘

then also real. Symmetry implies that ā’ ā Re. A

U ā“,0 ā“ ā‘

ā“, (48)

ā“ straightforward computation concludes that all scalar

products among Eveā™s states are real and that the ā™s

where the four states ā‘ , ā“ , ā‘ , and ā“ belong to the

Hilbert space of Eveā™s probe HEve and satisfy ā‘ ā‘ and generate a subspace orthogonal to the ā™s:

F and ā‘ 2

2 2 2

ā“ . By symmetry

ā“ ā‘ ā“ ā“ 0. (58)

ā‘ ā“ ā“ ā‘

D. Unitarity imposes F D 1 and

F, i.e., that the shrinking is the

2

Finally, using ā’

same for all states, one obtains a relation between the

probe statesā™ overlap and the ļ¬delity:

50

Fuchs and Peres were the ļ¬rst to derive the result presented

in this section, using numerical optimization. Almost simulta-

neously, it was derived by Robert Grifļ¬ths and his student

51

Chi-Sheng Niu under very general conditions, and by Nicolas Actually, Niu and Grifļ¬ths (1999) showed that two-

Gisin using the symmetry argument presented here. These ļ¬ve dimensional probes sufļ¬ce for Eve to get as much information

authors joined forces to produce a single paper (Fuchs et al., as with the strategy presented here, though in their case the

1997). The result of this section is thus also valid without this attack is not symmetric (one basis is more disturbed than the

symmetry assumption. other).

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

184 Gisin et al.: Quantum cryptography

Ėā‘ Ėā“

1

F , (59)

Ėā‘ Ėā“ Ėā‘ Ėā“

2

where the hats denote normalized states, e.g., Ė ā‘

ā‘D

1/2

.

Consequently the entire class of symmetric individual

attacks depends only on two real parameters:52 cos(x)

Ė ā‘ Ė ā“ and cos(y) Ė ā‘ Ė ā“ .

Thanks to symmetry, it sufļ¬ces to analyze this sce-

nario for the case when Alice sends the ā‘ state and

Bob measures in the ā‘,ā“ basis (if not, Alice, Bob, and

Eve disregard the data). Since Eve knows the basis, she

knows that her probe is in one of the following two

mixed states:

FIG. 30. Eveā™s and Bobā™s information vs the QBER, here plot-

ā‘ FP DP , (60)

ā‘ ā‘

Eve ted for incoherent eavesdropping on the four-state protocol.

For QBERā™s below QBER0 , Bob has more information than

ā“ FP DP . (61)

ā“ ā“

Eve

Eve, and secret-key agreement can be achieved using classical

An optimum measurement strategy for Eve to distin- error correction and privacy ampliļ¬cation, which can, in prin-

guish between Eve (ā‘) and Eve (ā“) consists in ļ¬rst de- ciple, be implemented using only one-way communication.

termining whether her state is in the subspace generated The secret-key rate can be as large as the information differ-

by ā‘ and ā“ or the one generated by ā‘ and ā“ . This is ences. For QBERā™s above QBER0 ( D0 ), Bob has a disad-

possible, since the two subspaces are mutually orthogo- vantage with respect to Eve. Nevertheless, Alice and Bob can

nal. Eve must then distinguish between two pure states apply quantum privacy ampliļ¬cation up to the QBER corre-

with an overlap of either cos x or cos y. The ļ¬rst alterna- sponding to the intercept-resend eavesdropping strategies (IR4

tive occurs with probability F, the second with probabil- and IR6 for the four-state and six-state protocols, respectively).

ity D. The optimal measurement distinguishing two Alternatively, they can apply a classical protocol called advan-

states with overlap cos x is known to provide Eve with tage distillation, which is effective up to precisely the same

the correct guess with probability 1 sin(x) /2 (Peres, maximal QBER IR4 and IR6 . Both the quantum and the clas-

1997). Eveā™s maximal Shannon information, attained sical protocols require two-way communication. Note that for

when she performs the optimal measurements, is thus the eavesdropping strategy that will be optimal, from Eve

Shannon point of view, on the four-state protocol, QBER0

given by

should correspond precisely to the noise threshold above

1 sin x which a Bellā™s inequality can no longer be violated.

Fā¢ 1 h

I ,

2

1 sin y Once Alice, Bob, and Eve have measured their quan-

Dā¢ 1 h , (62)

2 tum systems, they are left with classical random vari-

ables , , and , respectively. Secret-key agreement be-

where h(p) p log2(p) (1 p)log2(1 p). For a given

tween Alice and Bob is then possible using only error

error rate D, this information is maximal when x y.

correction and privacy ampliļ¬cation if and only if the

Consequently, for D 1 cos(x) /2, one obtains:

Alice-Bob mutual Shannon information I( , ) is

1 sin x greater than the Alice-Eve or the Bob-Eve mutual

I max , 1h . (63)

information,53 I( , ) I( , ) or I( , ) I( , ). It is

2

thus interesting to compare Eveā™s maximal information

This provides the explicit and analytic optimum eaves-

[Eq. (64)] with Bobā™s Shannon information. The latter

dropping strategy. For x 0 the QBER (i.e., D) and the

depends only on the error rate D:

information gain are both zero. For x /2 the QBER is

1

2 and the information gain 1. For small QBERā™s, the 1 hD

I , (65)

information gain grows linearly:

1 D log2 D 1 D log2 1 D . (66)

2

D OD

max 2

I , 2.9D. (64) Bobā™s and Eveā™s information are plotted in Fig. 30. As

ln 2

expected, for low error rates D, Bobā™s information is

greater. But, more errors provide Eve with more infor-

52

Interestingly, when the symmetry is extended to a third

maximally conjugated basis, as is natural in the six-state pro-

53

Note, however, that if this condition is not satisļ¬ed, other

tocol of Sec. II.D.2, the number of parameters reduces to one.

protocols might sometimes be used; see Sec. II.C.5. These pro-

This parameter measures the relative quality of Bobā™s and

tocols are signiļ¬cantly less efļ¬cient and are usually not consid-

Eveā™s ā˜ā˜copyā™ā™ of the qubit sent by Alice. When both copies are

ered as part of ā˜ā˜standardā™ā™ QC. Note also that, in the scenario

of equal quality, one recovers the optimal cloning presented in

analyzed in this section, I( , ) I( , ).

Sec. II.F (Bechmann-Pasquinucci and Gisin, 1999).

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

185

Gisin et al.: Quantum cryptography

mation, while decreasing Bobā™s information. Hence both or equivalently if some perturbing Eve acts on the chan-

information curves cross at a speciļ¬c error rate D0 : nel, then the quantum correlation E(a,b D) is reduced:

1 1/& E a,b D Fā¢E a,b Dā¢E a,b (70)

ā”D D0

I max

I , , 15%. (67)

2

1 2D ā¢E a,b , (71)

Consequently the security criterion against individual at-

tacks for the BB84 protocol is

where E(a,b) denotes the correlation for the unper-

turbed channel. The achievable amount of violation is

1 1/&

BB84 secureā”D D0 then reduced to S max(D) (1 2D)2&, and for large

. (68)

2 perturbations no violation at all can be achieved. Inter-

estingly, the critical perturbation D up to which a viola-

For QBERā™s greater than D0 , no (one-way communi- tion can be observed is precisely the same D0 as the limit

cation) error correction and privacy ampliļ¬cation proto- derived in the previous section for the security of the

col can provide Alice and Bob with a secret key that is BB84 protocol:

immune to any individual attacks.

Let us mention that there exists a class of more gen-

1 1/&

eral classical protocols, called advantage distillation (Sec. S max D 2ā”D D0 . (72)

2

II.C.5), which uses two-way communication. These pro-

tocols can guarantee secrecy if and only if Eveā™s inter-

vention does not disentangle Alice and Bobā™s qubits (as- This is a surprising and appealing connection between

suming they use the Ekert version of the BB84 protocol; the security of QC and tests of quantum nonlocality.

Gisin and Wolf, 2000). If Eve optimizes her Shannon One could argue that this connection is quite natural,

information as discussed in this section, this disentangle- since, if Bellā™s inequality were not violated, then quan-

ment limit corresponds to a QBER 1 1/& 30% (Gi- tum mechanics would be incomplete, and no secure

sin and Wolf, 1999). However, using more brutal strate- communication could be based on such an incomplete

gies, Eve can disentangle Alice and Bobā™s qubits for a theory. In some sense, Eveā™s information is like probabi-

QBER of 25%; see Fig. 30. The latter is thus the abso- listic local hidden variables. However, the connection

lute upper limit, taking into account the most general between Eqs. (68) and (72) has not been generalized to

secret-key protocols. In practice, the limit (67) is more other protocols. A complete picture of these connec-

realistic, since advantage distillation algorithms are tions is thus not yet available.

much less efļ¬cient than classical privacy ampliļ¬cation Let us emphasize that nonlocality plays no direct role

algorithms. in QC. Indeed, Alice is generally in Bobā™s absolute past.

Nevertheless, Bellā™s inequality can be violated by space-

F. Connection to Bellā™s inequality like separated events as well as by timelike separated

events. However, the independence assumption neces-

There is an intriguing connection between the tight- sary to derive Bellā™s inequality is justiļ¬ed by locality con-

bound [Eq. (68)] and the Clauser-Horne-Shimony-Holt siderations only for spacelike separated events.

(CHSH) form of Bellā™s inequality (Bell, 1964; Clauser

et al., 1969; Clauser and Shimony, 1978; Zeilinger, 1999):

S Ea E a,b E a ,b E a ,b 2. (69)

G. Ultimate security proofs

Here E(a,b) is the correlation between Alice and Bobā™s

data when measuring a 1 and 1 b , where a de- The security proof of QC with a perfect apparatus and

notes an observable with eigenvalues 1 parametrized a noise-free channel is straightforward. However, the

by the label a. Recall that Bellā™s inequalities are neces- fact that security can still be proven for an imperfect

sarily satisļ¬ed by all local models but are violated by apparatus and noisy channels is far from obvious.

quantum mechanics.54 To establish this connection, as- Clearly, something has to be assumed about the appara-

sume that the same quantum channel is used to test tus. In this section we simply make the hypothesis that

Bellā™s inequality. It is well known that, for error-free they are perfect. For the channel that is not under Alice

channels, a maximal violation by a factor & is achiev- and Bobā™s control, however, nothing is assumed. The

question is then Up to what QBER can Alice and Bob

able: S max 2& 2. However, if the channel is imperfect,

apply error correction and privacy ampliļ¬cation to their

classical bits? In the previous sections we found that the

threshold is close to a QBER of 15%, assuming indi-

vidual attacks. In principle Eve could manipulate several

54

Let us stress that the CHSH-Bellā™s inequality is the stron-

qubits coherently. How much help to Eve this possibility

gest possible for two qubits. Indeed, this inequality is violated

provides is still unknown, though some bounds are

if and only if the correlation cannot be reproduced by a local

known. In 1996, Dominic Mayers (1996b) presented the

hidden-variable model (Pitowski, 1989).

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

186 Gisin et al.: Quantum cryptography

main ideas on how to prove security.55 In 1998, two ma-

jor papers were made public on the Los Alamos archives

(Mayers, 1998, and Lo and Chau, 1999). Today, these

proofs are generally considered valid, thanks to the

work ofā”among othersā”Shor and Preskill (2000), In-

amori et al. (2001), and Biham et al. (1999). However, it

is worth noting that during the ļ¬rst few years after the

initial disclosure of these proofs, hardly anyone in the

community understood them.

Here we shall present the argument in a form quite

different from the original proofs. Our presentation

aims at being transparent in the sense that it rests on two

theorems. The proofs of the theorems are difļ¬cult and FIG. 31. Intuitive illustration of Theorem 1. The initial situa-

will be omitted. However, their claims are easy to under- tion is depicted in (a). During the one-way public discussion

stand and rather intuitive. Once one accepts the theo- phase of the protocol, Eve receives as much information as

rems, the security proof is straightforward. Bob; the initial information difference thus remains. After

The general idea is that at some point Alice, Bob, and error correction, Bobā™s information equals 1, as illustrated in

Eve perform measurements on their quantum systems. (b). After privacy ampliļ¬cation Eveā™s information is zero. In

The outcomes provide them with classical random vari- (c) Bob has replaced with random bits all bits to be disre-

garded. Hence the key still has its original length, but his in-

ables , , and , respectively, with P( , , ) the joint

formation has decreased. Finally, in (d) removal of the random

probability distribution. The ļ¬rst theorem, a standard of

bits shortens the key to the initial information difference. Bob

classical information-based cryptography, states the nec-

has full information on this ļ¬nal key, while Eve has none.

essary and sufļ¬cient condition on P( , , ) for Alice

Ā“

and Bob to extract a secret key from P( , , ) (Csiszar

ĀØ

and Korner, 1978). The second theorem is a clever ver- Since error correction and privacy ampliļ¬cation can be

sion of Heisenbergā™s uncertainty relation expressed in implemented using only one-way communication, Theo-

terms of available information (Hall, 1995): it sets a rem 1 can be understood intuitively as follows. The ini-

bound on the sum of the information about Aliceā™s key tial situation is depicted in Fig. 31(a). During the public

available to Bob and to Eve. phase of the protocol, because of the one-way commu-

Theorem 1. For a given P( , , ), Alice and Bob can nication, Eve receives as much information as Bob. The

establish a secret key (using only error correction and initial information difference thus remains. After error

classical privacy ampliļ¬cation) if and only if I( , ) correction, Bobā™s information equals 1, as illustrated in

I( , ) or I( , ) I( , ), where I( , ) H( ) Fig. 31(b). After privacy ampliļ¬cation Eveā™s information

H( ) denotes the mutual information and H is the is zero. In Fig. 31(c) Bob has replaced all bits to be

Shannon entropy. disregarded by random bits. Hence the key still has its

Theorem 2. Let E and B be two observables in an original length, but his information has decreased. Fi-

N-dimensional Hilbert space. Let , , , and be nally, upon removal of the random bits, the key is short-

the corresponding eigenvalues and eigenvectors, respec- ened to the initial information difference ; see Fig.

tively, and let c max , . Then 31(d). Bob has full information about this ļ¬nal key,

while Eve has none.

I , I , 2 log2 Nc , (73)

The second theorem states that if Eve performs a

where I( , ) H( ) H( ) and I( , ) H( ) measurement providing her with some information

H( ) are the entropy differences corresponding to I( , ), then, because of the perturbation, Bobā™s infor-

the probability distribution of the eigenvalues prior to mation is necessarily limited. Using these two theorems,

and deduced from any measurement by Eve and Bob, the argument now runs as follows. Suppose Alice sends

respectively. out a large number of qubits and that n are received by

The ļ¬rst theorem states that Bob must have more in- Bob in the correct basis. The relevant Hilbert spaceā™s

formation about Aliceā™s bits than does Eve (see Fig. 31).

dimension is thus N 2 n . Let us relabel the bases used

for each of the n qubits such that Alice uses n times the

x basis. Hence Bobā™s observable is the n-time tensor

55

product x ĀÆ x . By symmetry, Eveā™s optimal infor-

One of the authors (N.G.) vividly remembers the 1996 In-

stitute for Scientiļ¬c Interchange workshop in Torino, Italy, mation about the correct bases is precisely the same as

sponsored by Elsag Bailey, where he ended his talk by stress- her optimal information about the incorrect ones (May-

ing the importance of security proofs. Dominic Mayers stood

ers, 1998). Hence one can bound her information, as-

up, gave some explanation, and wrote a formula on a transpar-

z ĀÆ z . Accordingly, c

suming she measures

ency, claiming that this was the result of his proof. We think it n/2

2 , and Theorem 2 implies

is fair to say that no one in the audience understood Mayersā™

explanation. However, N.G. kept the transparency, and it con- 2 log2 2 n 2 n/2

I , I , n. (74)

tains the basic Eq. (75) (up to a factor of 2, which corresponds

That is, the sum of Eveā™s and Bobā™s information per qu-

to an improvement of Mayerā™s result obtained in 2000 by Shor

bit is less than or equal to 1. This result is quite intuitive:

and Preskill, using ideas from Lo and Chau).

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

187

Gisin et al.: Quantum cryptography

degree of freedom encoding the qubits.56 Such measure-

together, Eve and Bob cannot receive more information

than is sent out by Alice! Next, combining the bound ments are sometimes called quantum nondemolition

(74) with Theorem 1, one deduces that a secret key is measurements, because they do not perturb the qubit; in

particular they do not destroy the photons. This is pos-

achievable whenever I( , ) n/2. Using I( , ) n 1

D log2(D) (1 D)log2(1 D) , one obtains the sufļ¬- sible because Eve knows in advance that Alice sends a

cient condition on the error rate D (i.e., the QBER): mixture of states with well-deļ¬ned photon numbers57

(see Sec. II.F). Next, if Eve ļ¬nds more than one photon,

1

D log2 D 1 D log2 1 D she keeps one and sends the other(s) to Bob. In order to

, (75)

2 prevent Bob from detecting a lower qubit rate, Eve must

use a channel with lower losses. Using an ideally lossless

i.e., D 11%.

quantum channel, Eve can even, under certain condi-

This bound, QBER 11%, is precisely that obtained

tions, keep one photon and increase the probability that

in Mayersā™s proof (after improvement by Shor and

pulses with more than one photon get to Bob! Finally,

Preskill, 2000). The above proof is, strictly speaking,

when Eve ļ¬nds one photon, she may destroy it with

only valid if the key is much longer than the number of

some probability that she does not affect the total num-

qubits that Eve attacks coherently, so that the Shannon

ber of qubits received by Bob. Consequently, if the prob-

information we used represents averages over many in-

ability that a nonempty pulse has more than one photon

dependent realizations of classical random variables. In

(on Aliceā™s side) is greater than the probability that a

other words, assuming that Eve can coherently attack a

nonempty pulse is detected by Bob, then Eve can get

large but ļ¬nite number n 0 of qubits, Alice and Bob can

full information without introducing any perturbation.

use the above proof to secure keys much longer than n 0

This is possible only when the QC protocol is not per-

bits. If one assumes that Eve has unlimited power and is

fectly implemented, but it is a realistic situation (Hutt-

able to attack coherently any number of qubits, then the

ner et al., 1995; Yuen, 1997).

above proof does not apply, but Mayersā™s proof can still

Quantum nondemolition atacks have recently re-

be used and provides precisely the same bound.

ĀØ

ceived a lot of attention (Brassard et al., 2000; Lutken-

This 11% bound for coherent attacks is clearly com-

haus, 2000). The debate is not yet settled. We would like

patible with the 15% bound found for individual attacks.

to argue that it might be unrealistic, or even unphysical,

The 15% bound is also necessary, since an explicit eaves-

to assume that Eve can perform ideal quantum non-

dropping strategy reaching this bound is presented in

demolition attacks. Indeed, she ļ¬rst needs the capacity

Sec. VI.E. It is not known what happens in the interme-

to perform quantum nondemolition photon-number

diate range 11% QBER 15%, but the following sce-

measurements. Although impossible with todayā™s tech-

nario is plausible. If Eve is limited to coherent attacks

nology, this is a reasonable assumption (Nogues et al.,

on a ļ¬nite number of qubits, then in the limit of arbi-

1999). Next, she should be able to keep her photon until

trarily long keys, she has a negligibly small probability

Alice and Bob reveal the basis. In principle, this could

that the bits combined by Alice and Bob during the er-

be achieved using a lossless channel in a loop. We dis-

ror correction and privacy ampliļ¬cation protocols origi-

ńņš. 10 |