<< . .

. 10
( : 12)



. . >>

“ ‘
  “) (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
( : 12)



. . >>