. 1
( : 12)



. . >>

REVIEWS OF MODERN PHYSICS, VOLUME 74, JANUARY 2002

Quantum cryptography
´
Nicolas Gisin, Gregoire Ribordy, Wolfgang Tittel, and Hugo Zbinden
Group of Applied Physics, University of Geneva, 1211 Geneva 4, Switzerland
(Published 8 March 2002)

Quantum cryptography could well be the ¬rst application of quantum mechanics at the
single-quantum level. The rapid progress in both theory and experiment in recent years is reviewed,
with emphasis on open questions and technological issues.


D. Frequency coding 173
CONTENTS
E. Free-space line-of-sight applications 174
F. Multi-user implementations 175
I. Introduction 145 V. Experimental Quantum Cryptography with Photon
II. A Beautiful Idea 146 Pairs 175
A. Polarization entanglement 176
A. The intuition 146
B. Energy-time entanglement 177
B. Classical cryptography 147
1. Phase coding 177
1. Asymmetrical (public-key) cryptosystems 147
2. Phase-time coding 179
2. Symmetrical (secret-key) cryptosystems 148
3. Quantum secret sharing 180
3. The one-time pad as ˜˜classical
VI. Eavesdropping 180
teleportation™™ 148
A. Problems and objectives 180
C. The BB84 protocol 149
B. Idealized versus real implementation 180
1. Principle 149
C. Individual, joint, and collective attacks 181
2. No-cloning theorem 149
D. Simple individual attacks: Intercept-resend and
3. Intercept-resend strategy 150
measurement in the intermediate basis 181
4. Error correction, privacy ampli¬cation, and
E. Symmetric individual attacks 182
quantum secret growing 150 F. Connection to Bell™s inequality 185
5. Advantage distillation 151 G. Ultimate security proofs 185
D. Other protocols 152 H. Photon number measurements and lossless
1. Two-state protocol 152 channels 187
2. Six-state protocol 152 I. A realistic beamsplitter attack 188
3. Einstein-Podolsky-Rosen protocol 152 J. Multiphoton pulses and passive choice of states 188
4. Other variations 153 K. Trojan horse attacks 189
E. Quantum teleportation as a ˜˜quantum one-time L. Real security: Technology, cost, and complexity 189
VII. Conclusions 190
pad™™ 154
Acknowledgments 190
F. Optical ampli¬cation, quantum nondemolition
References 190
measurements, and optimal quantum cloning 154
III. Technological Challenges 155
A. Photon sources 155 I. INTRODUCTION
1. Faint laser pulses 156
2. Photon pairs generated by parametric Electrodynamics was discovered and formalized in the
downconversion 156 19th century. The 20th century was then profoundly af-
3. Photon guns 157 fected by its applications. A similar adventure may be
B. Quantum channels 158
underway for quantum mechanics, discovered and for-
1. Single-mode ¬bers 158
malized during the last century. Indeed, although the la-
2. Polarization effects in single-mode ¬bers 158
ser and semiconductor are already common, applica-
3. Chromatic dispersion effects in single-mode
tions of the most radical predictions of quantum
¬bers 160
mechanics have only recently been conceived, and their
4. Free-space links 160
full potential remains to be explored by the physicists
C. Single-photon detection 161
and engineers of the 21st century.
1. Photon counting at wavelengths below 1.1
The most peculiar characteristics of quantum mechan-
m 163
2. Photon counting at telecommunications ics are the existence of indivisible quanta and of en-
wavelengths 163 tangled systems. Both of these lie at the root of quantum
D. Quantum random-number generators 164
cryptography (QC), which could very well be the ¬rst
E. Quantum repeaters 164
commercial application of quantum physics at the single-
IV. Experimental Quantum Cryptography with Faint
quantum level. In addition to quantum mechanics, the
Laser Pulses 165
20th century has been marked by two other major scien-
A. Quantum bit error rate 166
ti¬c revolutions: information theory and relativity. The
B. Polarization coding 167
status of the latter is well recognized. It is less well
C. Phase coding 168
known that the concept of information, nowadays mea-
1. The double Mach-Zehnder implementation 170
sured in bits, and the formalization of probabilities are
2. ˜˜Plug-and-play™™ systems 171


0034-6861/2002/74(1)/145(51)/$35.00 145 ©2002 The American Physical Society
146 Gisin et al.: Quantum cryptography


quite recent,1 although they have a tremendous impact a tool for new engineering. Apparently, information
on our daily life. It is fascinating to realize that QC lies theory, classical cryptography, quantum physics, and
at the intersection of quantum mechanics and informa- quantum optics ¬rst had to develop into mature sci-
tion theory and that, moreover, the tension between ences. It is certainly not a coincidence that QC and,
quantum mechanics and relativity”the famous more generally, quantum information were developed
Einstein-Rosen-Podolsky (EPR) paradox (Einstein by a community including many computer scientists and
et al., 1935)”is closely connected to the security of QC. more mathematically oriented young physicists: broader
Let us add a further point for young physicists. Unlike interests than traditional physics were needed.
laser and semiconductor physics, which are manifesta-
tions of quantum physics at the ensemble level and can
thus be described by semiclassical models, QC, and to an A. The intuition
even greater extent quantum computers, require a full
Quantum physics is well known for being counterin-
quantum-mechanical description (this may offer an in-
tuitive or even bizarre. We teach students that quantum
teresting challenge for physicists well trained in the
physics establishes a set of negative rules stating things
subtleties of their science).
that cannot be done. For example,
This review article has several objectives. First, we
present the basic intuition behind QC. Indeed, the basic
(1) One cannot take a measurement without perturbing
idea is so beautiful and simple that every physicist and
the system.
student should be given the pleasure of learning it. The
(2) One cannot determine simultaneously the position
general principle is then set in the broader context of
and the momentum of a particle with arbitrarily
modern cryptology (Sec. II.B) and made more precise
high accuracy.
(Sec. II.C). Section III discusses the main technological
(3) One cannot simultaneously measure the polariza-
challenges. Then, Secs. IV and V present the most com-
tion of a photon in the vertical-horizontal basis and
mon implementations of QC: the use of weak laser
simultaneously in the diagonal basis.
pulses and photon pairs, respectively. Finally, the impor-
(4) One cannot draw pictures of individual quantum
tant and dif¬cult problems of eavesdropping and secu-
processes.
rity proofs are discussed in Sec. VI, where the emphasis
(5) One cannot duplicate an unknown quantum state.
is more on the diversity of the issues than on formal
details. We have tried to write the different parts of this This negative viewpoint of quantum physics, due to its
review in such a way that they can be read indepen- contrast with classical physics, has only recently been
dently. turned positive, and QC is one of the best illustrations of
this psychological revolution. Indeed, one could charac-
terize quantum information processing as the science of
II. A BEAUTIFUL IDEA
turning quantum conundrums into potentially useful ap-
The idea of quantum cryptography was ¬rst proposed plications.
in the 1970s by Stephen Wiesner2 (1983) and by Charles Let us illustrate this point for QC. One of the basic
H. Bennett of IBM and Gilles Brassard of The Univer- negative statements of quantum physics reads
sity of Montreal (1984, 1985).3 However, this idea is so
´
One cannot take a measurement without perturbing
simple that any ¬rst-year student since the infancy of
the system (1)
quantum mechanics could actually have discovered it!
Nevertheless, it is only now that the ¬eld is mature (unless the quantum state is compatible with the mea-
enough and information security important enough that surement). The positive side of this axiom can be seen
physicists are ready to consider quantum mechanics, not when applied to a communication between Alice and
only as a strange theory good for paradoxes, but also as Bob (the conventional names of the sender and receiver,
respectively), provided the communication is quantum,
that is, quantum systems, for example, individual pho-
tons, carry the information. When this is the case, axiom
1
The Russian mathematician A. N. Kolmogorov (1956) is
(1) also applies to eavesdroppers, i.e., to a malicious Eve
credited with being the ¬rst to have formulated a consistent
(the conventional name given to the adversary in cryp-
mathematical theory of probabilities in the 1940s.
2
tology). Hence Eve cannot get any information about
S. Wiesner, then at Columbia University, was the ¬rst to pro-
pose ideas closely related to QC in the 1970s. However, his the communication without introducing perturbations
revolutionary paper did not appear until a decade later. Since that would reveal her presence.
it is dif¬cult to ¬nd, we reproduce his abstract here: The un- To make this intuition more precise, imagine that Al-
certainty principle imposes restrictions on the capacity of certain ice codes information in individual photons, which she
types of communication channels. This paper will show that in
sends to Bob. If Bob receives the photons unperturbed,
compensation for this ˜˜quantum noise,™™ quantum mechanics al-
then, according to the basic axiom (1), the photons were
lows us novel forms of coding without analogue in communica-
not measured. No measurement implies that Eve did not
tion channels adequately described by classical physics.
get any information about the photons (note that acquir-
3
Artur Ekert (1991) of Oxford University discovered QC in-
ing information is synonymous with carrying out mea-
dependently, though from a different perspective (see Sec.
surements). Consequently, after exchanging the photons,
II.D.3).


Rev. Mod. Phys., Vol. 74, No. 1, January 2002
147
Gisin et al.: Quantum cryptography


Before continuing, we need to see how QC could ¬t
into existing cryptosystems. For this purpose the next
section brie¬‚y surveys some of the main aspects of mod-
ern cryptology.


B. Classical cryptography

Cryptography is the art of rendering a message unin-
telligible to any unauthorized party. It is part of the
broader ¬eld of cryptology, which also includes cryp-
toanalysis, the art of code breaking (for a historical per-
spective, see Singh, 1999). To achieve this goal, an algo-
FIG. 1. Implementation of the Bennett and Brassard (BB84) rithm (also called a cryptosystem or cipher) is used to
´
protocol. The four states lie on the equator of the Poincare combine a message with some additional information”
sphere. known as the key”and produce a cryptogram. This
technique is known as encryption. For a cryptosystem to
be secure, it should be impossible to unlock the crypto-
Alice and Bob can check whether someone ˜˜was listen-
gram without the key. In practice, this requirement is
ing™™: they simply compare a randomly chosen subset of
often weakened so that the system is just extremely dif-
their data using a public channel. If Bob received this
¬cult to crack. The idea is that the message should re-
subset unperturbed, then the logic goes as follows:
main protected at least as long as the information it con-
No perturbation’No measurement tains is valuable. Although con¬dentiality is the
traditional application of cryptography, it is used nowa-
’No eavesdropping. (2)
days to achieve broader objectives, such as authen-
Actually, there are two more points to add. First, in tication, digital signatures, and nonrepudiation (Bras-
order to ensure that axiom (1) applies, Alice encodes sard, 1988).
her information in nonorthogonal states (we shall illus-
trate this in Secs. II.C and II.D). Second, as we have
1. Asymmetrical (public-key) cryptosystems
presented it so far, Alice and Bob could discover any
eavesdropper, but only after they have exchanged their Cryptosytems come in two main classes”depending
message. It would of course be much better to ensure on whether Alice and Bob use the same key. Asym-
their privacy in advance and not afterwards. To achieve metrical systems involve the use of different keys for
this, Alice and Bob complement the above idea with a encryption and decryption. They are commonly known
second idea, again a very simple one, and one which is as public-key cryptosystems. Their principle was ¬rst
entirely classical. Alice and Bob do not use the quantum proposed in 1976 by Whit¬eld Dif¬e and Martin Hell-
channel to transmit information, but only to transmit a man, who were then at Stanford University. The ¬rst
random sequence of bits, i.e., a key. Now, if the key is actual implementation was then developed by Ronald
unperturbed, then quantum physics guarantees that no Rivest, Adi Shamir, and Leonard Adleman of the Mas-
sachusetts Institute of Technology in 1978.4 It is known
one has gotten any information about this key by eaves-
dropping, i.e., measuring, the quantum communication as RSA and is still widely used. If Bob wants to be able
channel. In this case, Alice and Bob can safely use this to receive messages encrypted with a public-key crypto-
key to encode messages. If, on the other hand, the key system, he must ¬rst choose a private key, which he
turns out to be perturbed, then Alice and Bob simply keeps secret. Then he computes from this private key a
disregard it; since the key does not contain any informa- public key, which he discloses to any interested party.
tion, they have not lost any. Alice uses this public key to encrypt her message. She
Let us make this general idea somewhat more precise, transmits the encrypted message to Bob, who decrypts it
in anticipation of Sec. II.C. In practice, the individual with the private key. Public-key cryptosystems are con-
quanta used by Alice and Bob, often called qubits (for venient and have thus become very popular over the last
quantum bits), are encoded in individual photons; for 20 years. The security of the Internet, for example, is
example, vertical and horizontal polarization code for partially based on such systems. They can be thought of
bit values 0 and 1, respectively. The second basis can as a mailbox in which anybody can insert a letter. Only
then be the diagonal one ( 45° linear polarization), the legitimate owner can then recover it, by opening it
with 45° coding for bit 1 and 45° for bit 0, respec- with his private key.
tively (see Fig. 1). Alternatively, the circular polarization
basis could be used as second basis. For photons the
quantum communication channel can be either free 4
According to the British Government, public-key cryptogra-
space (see Sec. IV.E) or optical ¬bers”special ¬bers or phy was originally invented at the Government Communica-
the ones used in standard telecommunications (Sec. tions Headquarters in Cheltenham as early as 1973. For an
III.B). The communication channel is thus not really historical account, see, for example, the book by Simon Singh
quantum. What is quantum are the information carriers. (1999).


Rev. Mod. Phys., Vol. 74, No. 1, January 2002
148 Gisin et al.: Quantum cryptography


(sk m 1  kk m 1 ). Because the bits of the
The security of public-key cryptosystems is based on
computational complexity. The idea is to use mathemati- scrambled text are as random as those of the key, they
cal objects called one-way functions. By de¬nition, it is do not contain any information. This cryptosystem is
easy to compute the function f(x) given the variable x, thus provably secure according to information theory
(Shannon, 1949). In fact, it is the only provably secure
but dif¬cult to reverse the calculation and deduce x
cryptosystem known today.
from f(x). In the context of computational complexity,
Although perfectly secure, this system has a
the word ˜˜dif¬cult™™ means that the time required to per-
problem”it is essential for Alice and Bob to possess a
form a task grows exponentially with the number of bits
common secret key, which must be at least as long as the
in the input, while ˜˜easy™™ means that it grows polynomi-
message itself. They can only use the key for a single
ally. Intuitively, it is easy to understand that it takes only
encryption”hence the name ˜˜one-time pad.™™ If they
a few seconds to work out 67 71, but it takes much
used the key more than once, Eve could record all of the
longer to ¬nd the prime factors of 4757. However, fac-
scrambled messages and start to build up a picture of the
toring has a ˜˜trapdoor,™™ which means that it is easy to do
plain texts and thus also of the key. (If Eve recorded two
the calculation in the dif¬cult direction provided that
different messages encrypted with the same key, she
you have some additional information. For example, if
could add the scrambled texts to obtain the sum of the
you were told that 67 was one of the prime factors of
plain texts: s 1  s 2 m 1  k  m 2  k m 1  m 2  k  k
4757, the calculation would be relatively simple. The se-
m 1  m 2 , where we use the fact that  is commuta-
curity of RSA is actually based on the factorization of
tive.) Furthermore, the key has to be transmitted by
large integers.
some trusted means, such as a courier, or through a per-
In spite of its elegance, this technique suffers from a
sonal meeting between Alice and Bob. This procedure
major ¬‚aw. It has not been possible yet to prove whether
can be complex and expensive, and may even amount to
factoring is ˜˜dif¬cult™™ or not. This implies that the exis-
a loophole in the system.
tence of a fast algorithm for factorization cannot be
Because of the problem of distributing long sequences
ruled out. In addition, the discovery in 1994 by Peter
of key bits, the one-time pad is currently used only for
Shor of a polynomial algorithm allowing fast factoriza-
the most critical applications. The symmetrical crypto-
tion of integers with a quantum computer casts addi-
systems in use for routine applications such as
tional doubt on the nonexistence of a polynomial algo-
e-commerce employ rather short keys. In the case of the
rithm for classical computers.
Data Encryption Standard (also known as DES, pro-
Similarly, all public-key cryptosystems rely for their
moted by the United States™ National Institute of Stan-
security on unproven assumptions, which could them-
dards and Technology), a 56-bit key is combined with
selves be weakened or suppressed by theoretical or
the plain text divided into blocks in a rather complicated
practical advances. So far, no one has proved the exis-
way, involving permutations and nonlinear functions to
tence of any one-way function with a trapdoor. In other
produce the cipher text blocks (see Stallings, 1999 for a
words, the existence of secure asymmetric cryptosystems
didactic presentation). Other cryptosystems (e.g.,
is not proven. This poses a serious threat to these cryp-
IDEA, The International Data Encryption System, or
tosystems.
AES, the Advanced Encryption Standard) follow similar
In a society like ours, where information and secure
principles. Like asymmetrical cryptosystems, they offer
communication are of the utmost importance, one can-
only computational security. However, for a given key
not tolerate such a threat. For instance, an overnight
length, symmetrical systems are more secure than their
breakthrough in mathematics could make electronic
asymmetrical counterparts.
money instantly worthless. To limit such economic and
In practical implementations, asymmetrical algorithms
social risks, there is no alternative but to turn to sym-
are used not so much for encryption, because of their
metrical cryptosystems. QC has a role to play in such
slowness, but rather for distribution of session keys for
alternative systems.
symmetrical cryptosystems such as DES. Because the se-
curity of those algorithms is not proven (see Sec. II.B.1),
2. Symmetrical (secret-key) cryptosystems the security of the whole implementation can be com-
promised. If these algorithms were broken by math-
Symmetrical ciphers require the use of a single key for
ematical advances, QC would constitute the only way to
both encryption and decryption. These systems can be
solve the key distribution problem.
thought of as a safe in which the message is locked by
Alice with a key. Bob in turns uses a copy of this key to
unlock the safe. The one-time pad, ¬rst proposed by Gil-
3. The one-time pad as ˜˜classical teleportation™™
bert Vernam of AT&T in 1926, belongs to this category.
In this scheme, Alice encrypts her message, a string of The one-time pad has an interesting characteristic.
bits denoted by the binary number m 1 , using a ran- Assume that Alice wants to transfer to Bob a faithful
domly generated key k. She simply adds each bit of the copy of a classical system, without giving any informa-
message to the corresponding bit of the key to obtain tion to Eve about this system. For this purpose Alice
the scrambled text (s m 1  k, where  denotes the bi- and Bob have access only to an insecure classical chan-
nary addition modulo 2 without carry). It is then sent to nel. The operation is possible provided they share an
Bob, who decrypts the message by subtracting the key arbitrarily long secret key. Indeed, in principle, Alice

Rev. Mod. Phys., Vol. 74, No. 1, January 2002
149
Gisin et al.: Quantum cryptography


which bits are perfectly correlated (the ones for which
can measure the state of her classical system with arbi-
trarily high precision and then use the one-time pad to Alice and Bob used the same basis) and which ones are
securely communicate this information to Bob, who can completely uncorrelated (all the other ones). Hence a
then, in principle, reconstruct (a copy of) the classical straightforward error correction scheme is possible: For
system. This somewhat arti¬cial use of the one-time pad each bit Bob announces publicly in which basis he mea-
has an interesting quantum relative (see Sec. II.E). sured the corresponding qubit (but he does not tell the
result he obtained). Alice then reveals only whether or
not the state in which she encoded that qubit is compat-
C. The BB84 protocol
ible with the basis announced by Bob. If the state is
1. Principle
compatible, they keep the bit; if not, they disregard it. In
this way about 50% of the bit string is discarded. This
The ¬rst protocol for QC was proposed in 1984 by
shorter key obtained after basis reconciliation is called
Charles H. Bennett, of IBM and Gilles Brassard, of the

. 1
( : 12)



. . >>