48

Optical isolators, based on the Faraday e¬ect, let light pass

through only in one direction.

physics might be.

36

tacks are called joint attacks, while an intermediate class has to be averaged over all possible results r that Eve

assumes that Eve attaches one probe per qubit, like in might get:

individual attacks, but can measure several probes coher-

Ha = P (r)H(i|r) (41)

ently, like in coherent attacks. This intermediate class is posteriori

called collective attacks. It is not known whether this r

class is less e¬cient than the most general joint one. It is

also not known whether it is more e¬cient than the sim-

H(i|r) = ’ P (i|r) log(P (i|r)) (42)

pler individual attacks. Actually, it is not even known

i

whether joint attacks are more e¬cient than individual

ones! where the a posteriori probability of bit i given Eve™s

For joint and collective attacks, the usual assumption result r is given by Bayes™s theorem:

is that Eve measures her probe only after Alice and Bob

have completed all their public discussion about bases P (r|i)P (i)

P (i|r) = (43)

reconciliation, error correction and privacy ampli¬cation. P (r)

But for the more realistic individual attacks, one assumes

with P (r) = i P (r|i)P (i). In the case of intercept-

that Eve waits only until the bases reconciliation phase

of the public discussion49 . The motivation for this is resend, Eve gets one out of 4 possible results: r ∈ {‘, “

, ←, ’}. After the basis has been revealed, Alice™s input

that one hardly sees what Eve could gain waiting for the

assumes one out of 2 values: i ∈ {‘, “} (assuming the ‘“

public discussion on error correction and privacy ampli-

basis was used, the other case is completely analogous).

¬cation before measuring her probes, since she is anyway

1

One gets P (i =‘ |r =‘) = 1, P (i =‘ |r =’) = 2 and

going to measure them independently.

P (r) = 1 . Hence, I(±, «) = 1’ 2 h(1)’ 2 h( 2 ) = 1’ 2 = 2

1 1 1 1 1

Individual attacks have the nice feature that the prob- 2

lem can be entirely translated into a classical one: Alice, (with h(p) = p log2 (p) + (1 ’ p) log2 (1 ’ p)).

Bob and Eve all have classical information in the form Another strategy for Eve, not more di¬cult to imple-

of random variables ±, β an «, respectively, and the laws ment, consists in measuring the photons in the inter-

of quantum mechanics imposes constraints on the joint mediate basis (see Fig. 27), also known as the Brei-

probability distribution P (±, β, «). Such classical scenar- dbart basis (Bennett et al. 1992a). In this way the

ios have been widely studied by the classical cryptology probability that Eve guesses the correct bit value is

√

community and many results can thus be directly ap- p = cos(π/8)2 = 1 + 42 ≈ 0.854, corresponding to a

2

plied. QBER=2p(1 ’ p) = 25% and Shannon information gain

per bit of

D. Simple individual attacks: intercept-resend, I = 1 ’ H(p) ≈ 0.399. (44)

measurement in the intermediate basis

Consequently, this strategy is less advantageous for Eve

than the intercept-resend one. Note however, that with

The simplest attack for Eve consists in intercepting all

this strategy Eve™s probability to guess the correct bit

photons individually, to measure them in a basis cho-

value is 85.%, compared to only 75% in the intercept-

sen randomly among the two bases used by Alice and to

resend case. This is possible because in the latter case

send new photons to Bob prepared according to her re-

Eve™s information is deterministic in half the cases, while

sult. As presented in paragraph II C 3 and assuming that

in the ¬rst one Eve™s information is always probabilistic

the BB84 protocol is used, Eve gets thus 0.5 bit of infor-

(formally this results from the convexity of the entropy

mation per bit in the sifted key, for an induced QBER

function).

of 25%. Let us illustrate the general formalism on this

simple example. Eve™s mean information gain on Alice™s

bit, I(±, «), equals their relative entropy decrease:

E. Symmetric individual attacks

I(±, «) = Ha ’ Ha (40)

priori posteriori

In this section we present in some details how Eve

i.e. I(±, β) is the number of bits one can save writing ± could get a maximum Shannon information for a ¬xed

when knowing β. Since the a priori probability for Alice™s QBER, assuming a perfect single qubit source and re-

bit is uniform, Ha priori = 1. The a posteriori entropy stricting Eve to attacks on one qubit after the other (i.e.

individual attacks). The motivation is that this ideal-

ized situation is rather easy to treat and nicely illustrates

several of the subtleties of the subject. Here we concen-

49

trate on the BB84 4-state protocol, for related results on

With today™s technology, it might even be fair to assume,

the 2-state and the 6-state protocols see Fuchs and Peres

in individual attacks, that Eve must measure her probe before

(1996) and Bechmann-Pasquinucci and Gisin (1999), re-

the basis reconciliation.

spectively.

37

The general idea of eavesdropping on a quantum chan- U | “, 0 = | “ — φ“ + | ‘ — θ“ (48)

nel goes as follows. When a qubit propagates from Al-

where the 4 states φ‘ , φ“ , θ‘ and θ“ belong to Eve™s probe

ice to Bob, Eve can let a system of her choice, called a

Hilbert space HEve and satisfy φ‘ ⊥ θ‘ and φ“ ⊥ θ“ .

probe, interact with the qubit (see Fig. 28). She can

By symmetry |φ‘ |2 = |φ“ |2 ≡ F and |θ‘ |2 = |θ“ |2 ≡ D.

freely choose the probe and its initial state, but it has to

Unitarity imposes F + D = 1 and

be a system satisfying the quantum rules (i.e. described

in some Hilbert space). Eve can also choose the interac-

φ‘ |θ“ + θ‘ |φ“ = 0. (49)

tion, but it should be independent of the qubit state and

she should follow the laws of quantum mechanics, i.e. her

The φ™s correspond to Eve™s state when Bob gets the

interaction is described by a unitary operator. After the

qubit undisturbed, while the θ™s are Eve™s state when

interaction a qubit has to go to Bob (in section VI H we

the qubit is disturbed.

consider lossy channels, so that Bob does not always ex-

Let us emphasize that this is the most general unitary

pect a qubit, a fact that Eve can take advantage of). It

interaction satisfying (46). One ¬nds that the shrinking

makes no di¬erence whether this qubit is the original one

factor is given by: · = F ’ D. Accordingly, if Alice

(possibly in a modi¬ed state) or not. Actually the ques-

sends | ‘ and Bob measures in the compatible basis,

tion does not even make sense since a qubit is nothing

then ‘ |ρBob (m)| ‘ = F is the probability that Bob

but a qubit! But in the formalism it is convenient to use

gets the correct result. Hence F is the ¬delity and D the

the same Hilbert space for the qubit sent by Alice and

QBER.

that received by Bob (this is no loss of generality, since

Note that only 4 states span Eve™s relevant state space.

the swap operator “ de¬ned by ψ — φ ’ φ — ψ for all ψ,φ

Hence, Eve™s e¬ective Hilbert space is at most of dimen-

“ is unitary and could be appended to Eve™s interaction).

sion 4, no matter how subtle she might be51 ! This greatly

Let HEve and C2 —HEve be the Hilbert spaces of Eve™s

simpli¬es the analysis.

probe and of the total qubit+probe system, respectively.

The symmetry imposes that the attack on the other

If |m , |0 and U denote the qubit and the probe™s initial

basis satis¬es:

states and the unitary interaction, respectively, then the

state of the qubit received by Bob is given by the density | ‘, 0 + | “, 0

√

U | ’, 0 = U (50)

matrix obtained by tracing out Eve™s probe:

2

1

ρBob (m) = T rHEve (U |m, 0 m, 0|U † ). (45) = √ (| ‘ — φ‘ + | “ — θ‘ (51)

2

The symmetry of the BB84 protocol makes it very nat- + | “ — φ“ + | ‘ — θ“ ) (52)

ural to assume that Bob™s state is related to Alice™s |m

= | ’ — φ’ + | ← — θ’ (53)

by a simple shrinking factor50 · ∈ [0, 1] (see Fig. 29):

where

1 + · mσ

1

ρBob (m) = . (46)

1

2 φ’ = (φ‘ + θ‘ + φ“ + θ“ ) (54)

2

Eavesdroppings that satisfy the above condition are 1

θ’ = (φ‘ ’ θ‘ ’ φ“ + θ“ ) (55)

called symmetric attacks.

2

Since the qubit state space is 2-dimensional, the uni-

tary operator is entirely determined by its action on two Similarly,

states, for example the | ‘ and | “ states (in this section

1

1

we use spin 2 notations for the qubits). It is convenient φ← = (φ‘ ’ θ‘ + φ“ ’ θ“ ) (56)

2

to write the states after the unitary interaction in the

1

Schmidt form (Peres 1997):

θ← = (φ‘ + θ‘ ’ φ“ ’ θ“ ) (57)

2

U | ‘, 0 = | ‘ — φ‘ + | “ — θ‘ (47)

Condition (46) for the {| ’ , | ← } basis implies: θ’ ⊥

φ’ and θ← ⊥ φ← . By proper choice of the phases,

φ‘ |θ“ can be made real. By condition (49) θ‘ |φ“ is

then also real. Symmetry implies then θ’ |φ← ∈ „.

50

Chris Fuchs and Asher Peres were the ¬rst ones to derive

the result presented in this section, using numerical optimiza-

tion. Almost simultaneously Robert Gri¬ths and his stu-

dent Chi-Sheng Niu derived it under very general conditions

51

and Nicolas Gisin using the symmetry argument used here. Actually, Niu and Gri¬ths (1999) showed that 2-

These 5 authors joined e¬orts in a common paper (Fuchs et dimensional probes su¬ce for Eve to get as much information

al. 1997). The result of this section is thus also valid without as with the strategy presented here, though in their case the

this symmetry assumption. attack is not symmetric (one basis is more disturbed than the

other).

38

A straightforward computation concludes that all scalar where h(p) = ’p log2 (p) ’ (1’) log2 (1 ’ p). For a given

products among Eve™s states are real and that the φ™s error rate D, this information is maximal when x = y.

Consequently, for D = 1’cos(x) , one has:

generate a subspace orthogonal to the θ™s: 2

φ‘ |θ“ = φ“ |θ‘ = 0. (58) 1 + sin(x)

I max (±, «) = 1 ’ h( ). (64)

2

Finally, using |φ’ |2 = F , i.e. that the shrinking is the

same for all states, one obtains a relation between the This provides the explicit and analytic optimum eaves-

probe states™ overlaps and the ¬delity: dropping strategy. For x = 0 the QBER (i.e. D) and

the information gain are zero. For x = π/2 the QBER

ˆˆ 1

1 + θ‘ |θ“ is 2 and the information gain 1. For small QBERs, the

F= (59)

information gain grows linearly:

ˆˆ ˆˆ

2 ’ φ‘ |φ“ + θ‘ |θ“

2

φ

ˆ I max (±, «) = D + O(D)2 ≈ 2.9 D (65)

‘

where the hats denote normalized states, e.g. φ‘ = √D .

ln(2)

Consequently, the entire class of symmetric individual

attacks depends only on 2 real parameters52 : cos(x) ≡ Once Alice, Bob and Eve have measured their quantum

ˆˆ ˆˆ

φ‘ |φ“ and cos(y) ≡ θ‘ |θ“ ! systems, they are left with classical random variables ±, β

Thanks to the symmetry, it su¬ces to analyze this and «, respectively. Secret key agreement between Alice

scenario for the case that Alice sends the | ‘ state and and Bob is then possible using only error correction and

Bob measures in the {‘, “} basis (if not, Alice, Bob and privacy ampli¬cation if and only if the Alice-Bob mutual

Eve disregard the data). Since Eve knows the basis, she Shannon information I(±, β) is larger than the Alice-Eve

or the Bob-Eve mutual information53 , I(±, β) > I(±, «)

knows that her probe is in one of the following two mixed

states: or I(±, β) > I(β, «). It is thus interesting to compare

Eve™s maximal information (64) with Bob™s Shannon in-

ρEve (‘) = F P (φ‘ ) + DP (θ‘ ) (60) formation. The latter depends only on the error rate D:

ρEve (“) = F P (φ“ ) + DP (θ“ ). (61)

I(±, β) = 1 ’ h(D) (66)

An optimum measurement strategy for Eve to distinguish = 1 + D log2 (D) + (1 ’ D) log2 (1 ’ D) (67)

between ρEve (‘) and ρEve (“) consists in ¬rst distinguish-

ing whether her state is in the subspace generated by φ‘ Bob™s and Eve™s information are plotted on Fig. 30. As

and φ“ or the one generated by θ‘ and θ“ . This is pos- expected, for low error rates D, Bob™s information is

sible, since the two subspaces are mutually orthogonal. larger. But, more errors provide Eve with more infor-

Eve has then to distinguish between two pure states, ei- mation, while Bob™s information gets lower. Hence, both

ther with overlap cos(x), or with overlap cos(y). The ¬rst information curves cross at a speci¬c error rate D0 :

alternative happens with probability F , the second one √

1 ’ 1/ 2

with probability D. The optimal measurement distin-

I(±, β) = I max (±, «) ⇐’ D = D0 ≡ ≈ 15%

guishing two states with overlap cos(x) is known to pro- 2

vide Eve with the correct guess with probability 1+sin(x) (68)

2

(Peres 1997). Eve™s maximal Shannon information, at-

tained when she does the optimal measurements, is thus Consequently, the security criteria against individual at-

given by: tacks for the BB84 protocol reads:

√

1 + sin(x) 1 ’ 1/ 2

I(±, «) = F · 1 ’ h( ) (62) BB84 secure ⇐’ D < D0 ≡ (69)

2 2

1 + sin(y)

For QBERs larger than D0 no (one-way communica-

+ D · 1 ’ h( ) (63)

2 tion) error correction and privacy ampli¬cation protocol

can provide Alice and Bob with a secret key immune

against any individual attacks.

52

Interestingly, when the symmetry is extended to a third

maximally conjugated basis, as natural in the 6-state protocol

of paragraph II D 2, then the number of parameters reduces 53

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

to one. This parameter measures the relative quality of Bob™s

protocols might sometimes be used, see paragraph II C 5.

and Eve™s “copy” of the qubit send by Alice. When both

These protocols are signi¬cantly less e¬cient and are usu-

copies are of equal quality, one recovers the optimal cloning

ally not considered as part of “standard” QC. Note also that

presented in section II F (Bechmann-Pasquinucci and Gisin

in the scenario analysed in this section I(β, «) = I(±, «).

1999).

39

√

1 ’ 1/ 2

Let us mention that more general classical protocols,

Smax (D) > 2 ⇐’ D < D0 ≡ . (73)

called advantage distillation (paragraph II C 5), using two 2

way communication, exist. These can guarantee secrecy

This is a surprising and appealing connection between

if and only if Eve™s intervention does not disentangle Al-

the security of QC and tests of quantum nonlocality.

ice and Bob™s qubits (assuming they use the Ekert ver-

One could argue that this connection is quite natural,

sion of the BB84 protocol) (Gisin and Wolf 2000). If

since, if Bell inequality were not violated, then quantum

Eve optimizes her Shannon information, as discussed in

mechanics would be incomplete and no secure commu-

this section, this disentanglement-limit corresponds to a

√ nication could be based on such an incomplete theory.

QBER= 1 ’ 1/ 2 ≈ 30% (Gisin and Wolf 1999). But,

In some sense, Eve™s information is like probabilistic lo-

using more brutal strategies, Eve can disentangled Alice

cal hidden variables. However, the connection between

and Bob already for a QBER of 25%, see Fig. 30. The

(69) and (73) has not been generalized to other protocols.

latter is thus the absolute upper limit, taking into ac-

A complete picture of these connections is thus not yet

count the most general secret-key protocols. In practice,

available.

the limit (68) is more realistic, since advantage distilla-

Let us emphasize that nonlocality plays no direct role

tion algorithms are much less e¬cient than the classical

in QC. Indeed, generally, Alice is in the absolute past

privacy ampli¬cation ones.

of Bob. Nevertheless, Bell inequality can be violated as

well by space like separated events as by time like sep-

arated events. However, the independence assumption

F. Connection to Bell inequality

necessary to derive Bell inequality is justi¬ed by locality

considerations only for space-like separated events.

There is an intriguing connection between the above

tight bound (69) and the CHSH form of Bell inequality

(Bell 1964, Clauser et al. 1969, Clauser and Shimony G. Ultimate security proofs

1978, Zeilinger 1999):

The security proof of QC with perfect apparatuses and

S ≡ E(a, b) + E(a, b′ ) + E(a′ , b) ’ E(a′ , b′ ) ¤ 2 (70)

a noise-free channel is straightforward. However, the fact

that security can still be proven for imperfect apparatuses

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

and noisy channels is far from obvious. Clearly, some-

data when measuring σa —1 and 1 —σb , where σa denotes

1 1

thing has to be assumed about the apparatuses. In this

an observable with eigenvalues ±1 parameterized by the

section we simply make the hypothesis that they are per-

label a. Recall that Bell inequalities are necessarily sat-

fect. For the channel which is not under Alice and Bob™s

is¬ed by all local models, but are violated by quantum

mechanics54 . To establish this connection, assume that control, however, nothing is assumed. The question is

then: up to which QBER can Alice and Bob apply er-

the same quantum channel is used to test Bell inequality.

ror correction and privacy ampli¬cation to their classical

It is well-known that√ error free channels, a maximal

for √

bits? In the previous sections we found that the threshold

violation by a factor 2 is achievable: Smax = 2 2 > 2.

is close to a QBER of 15%, assuming individual attacks.

However, if the channel is imperfect, or equivalently if

But in principle Eve could manipulate several qubits co-

some perturbator Eve acts on the channel, then the quan-

herently. How much help to Eve this possibility provides

tum correlation E(a, b|D) is reduced,

is still unknown, though some bounds are known. Al-

E(a, b|D) = F · E(a, b) ’ D · E(a, b) (71) ready in 1996, Dominic Mayers (1996b) presented the

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

= (1 ’ 2D) · E(a, b) (72)

jor papers were made public on the Los Alamos archives

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

where E(a, b) denote the correlation for the unperturbed

proofs are generally considered as valid, thanks “ among

channel. The achievable amount of violation is then re-

√

duced to Smax (D) = (1 ’ 2D)2 2 and for large pertur-

bations no violation at all can be achieved. Interestingly,

the critical perturbation D up to which a violation can

be observed is precisely the same D0 as the limit derived 55

I (NG) vividly remember the 1996 ISI workshop in Torino,

in the previous section for the security of the BB84 pro- sponsored by Elsag-Bailey, were I ended my talk stressing the

tocol: importance of security proofs. Dominic Mayers stood up, gave

some explanation, and wrote a formula on a transparency,

claiming that this was the result of his proof. I think it is

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

explanation. But I kept the transparency and it contains the

54

Let us stress that the CHSH-Bell inequality is the strongest

basic eq. (76) (up to a factor 2, which corresponds to an

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

improvement of Mayers result obtained in 2000 by Shor and

and only if the correlation can™t be reproduced by a local

Preskill, using also ideas from Lo and Chau)!

hidden variable model (Pitowski 1989).

40

others “ to the works of P. Shor and J. Preskill (2000), d). Bob has full information on this ¬nal key, while Eve

H. Inamori et al. (2001) and of E. Biham et al. (1999). has none.

But it is worth noting that during the ¬rst years after The second theorem states that if Eve performs a mea-

the ¬rst disclosure of these proofs, essentially nobody in surement providing her with some information I(±, «),

the community understood them! then, because of the perturbation, Bob™s information is

Here we shall present the argument in a form quite necessarily limited. Using these two theorems, the ar-

di¬erent from the original proofs. Our presentation aims gument now runs as follows. Suppose Alice sends out

at being transparent in the sense that it rests on two a large number of qubits and that n where received by

theorems. The proofs of the theorems are hard and will Bob in the correct basis. The relevant Hilbert space™s

dimension is thus N = 2n . Let us re-label the bases used

be omitted. However, their claims are easy to understand

and rather intuitive. Once one accepts the theorems, the for each of the n qubits such that Alice used n times

security proof is rather straightforward. the x-basis. Hence, Bob™s observable is the n-time ten-

The general idea is that at some point Alice, Bob and sor product σx — ... — σx . By symmetry, Eve™s optimal

Eve perform measurements on their quantum systems. information on the correct bases is precisely the same as

The outcomes provide them with classical random vari- her optimal information on the incorrect ones (Mayers

ables ±, β and «, respectively, with P (±, β, «) the joint 1998). Hence one can bound her information assuming

she measures σz — ... — σz . Accordingly, c = 2’n/2 and

probability distribution. The ¬rst theorem, a standard

of classical information based cryptography, states nec- theorem 2 implies:

essary and su¬cient condition on P (±, β, «) for the pos-

I(±, «) + I(±, β) ¤ 2 log2 (2n 2’n/2 ) = n (75)

sibility that Alice and Bob extract a secret key from

P (±, β, «) (Csisz´r and K¨rner 1978). The second the-

a o

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

orem is a clever version of Heisenberg™s uncertainty re-

qubit is smaller or equal to 1. This is quite an intu-

lation expressed in terms of available information (Hall