<< . .

. 2
( : 12)



. . >>

the sifted key.6 The fact that Alice and Bob use a public
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-

<< . .

. 2
( : 12)



. . >>