. 1
( : 11)



. . >>

Quantum cryptography

Nicolas Gisin, Gr´goire Ribordy, Wolfgang Tittel and Hugo Zbinden
e
Group of Applied Physics, University of Geneva, 1211 Geneva 4, Switzerland
(July 8, 2004; submitted to Reviews of Modern Physics)



4 Free-space links . . . . . . . . . . . 17
Quantum cryptography could well be the ¬rst application C Single-photon detection . . . . . . . . . 18
of quantum mechanics at the individual quanta level. The
1 Photon counting at wavelengths be-
very fast progress in both theory and experiments over the
low 1.1 µm . . . . . . . . . . . . . . 19
recent years are reviewed, with emphasis on open questions
2 Photon counting at telecommunica-
and technological issues.
tion wavelengths . . . . . . . . . . . 19
arXiv:quant-ph/0101098 v2 18 Sep 2001




D Quantum random number generators . 20
E Quantum repeaters . . . . . . . . . . . 20
Contents
IV Experimental quantum cryptography
I Introduction 2 with Faint laser pulses 21
A Quantum Bit Error Rate . . . . . . . . 22
II A beautiful idea 2 B Polarization coding . . . . . . . . . . . 23
A The intuition . . . . . . . . . . . . . . . 2 C Phase coding . . . . . . . . . . . . . . . 24
B Classical cryptography . . . . . . . . . 3 1 The double Mach-Zehnder imple-
1 Asymmetrical (public-key) cryp- mentation . . . . . . . . . . . . . . 25
tosystems . . . . . . . . . . . . . . . 3 2 The “Plug-&-Play” systems . . . . 26
2 Symmetrical (secret-key) cryptosys- D Frequency coding . . . . . . . . . . . . 28
tems . . . . . . . . . . . . . . . . . 4 E Free space line-of-sight applications . . 29
3 The one-time-pad as “classical tele- F Multi-users implementations . . . . . . 30
portation” . . . . . . . . . . . . . . 5
C The example of the BB84 protocol . . . 5 V Experimental quantum cryptography
1 Principle . . . . . . . . . . . . . . . 5 with photon pairs 31
2 No cloning theorem . . . . . . . . . 6 A Polarization entanglement . . . . . . . 32
3 Intercept-resend strategy . . . . . . 6 B Energy-time entanglement . . . . . . . 33
4 Error correction, privacy ampli¬ca- 1 Phase-coding . . . . . . . . . . . . . 33
tion and quantum secret growing . . 6 2 Phase-time coding . . . . . . . . . . 34
5 Advantage distillation . . . . . . . . 8 3 Quantum secret sharing . . . . . . . 35
D Other protocols . . . . . . . . . . . . . 8
1 2-state protocol . . . . . . . . . . . 8 VI Eavesdropping 35
2 6-state protocol . . . . . . . . . . . 9 A Problems and Objectives . . . . . . . . 35
3 EPR protocol . . . . . . . . . . . . 9 B Idealized versus real implementation . . 36
4 Other variations . . . . . . . . . . . 10 C Individual, joint and collective attacks 36
E Quantum teleportation as “Quantum D Simple individual attacks: intercept-
one-time-pad” . . . . . . . . . . . . . . 10 resend, measurement in the intermedi-
F Optical ampli¬cation, quantum non- ate basis . . . . . . . . . . . . . . . . . 37
demolition measurements and optimal E Symmetric individual attacks . . . . . . 37
quantum cloning . . . . . . . . . . . . . 10 F Connection to Bell inequality . . . . . . 40
G Ultimate security proofs . . . . . . . . 40
III Technological challenges 12 H Photon number measurements, lossless
A Photon sources . . . . . . . . . . . . . . 12 channels . . . . . . . . . . . . . . . . . 42
1 Faint laser pulses . . . . . . . . . . 12 I A realistic beamsplitter attack . . . . . 43
2 Photon pairs generated by paramet- J Multi-photon pulses and passive choice
ric downconversion . . . . . . . . . 13 of states . . . . . . . . . . . . . . . . . 43
3 Photon guns . . . . . . . . . . . . . 14 K Trojan Horse Attacks . . . . . . . . . . 43
B Quantum channels . . . . . . . . . . . . 14 L Real security: technology, cost and
1 Singlemode ¬bers . . . . . . . . . . 14 complexity . . . . . . . . . . . . . . . . 44
2 Polarization e¬ects in singlemode
¬bers . . . . . . . . . . . . . . . . . 15 VII Conclusion 44
3 Chromatic dispersion e¬ects in sin-
glemode ¬bers . . . . . . . . . . . . 16


1
a way that they can be read independently.
I. INTRODUCTION

Electrodynamics was discovered and formalized in the
II. A BEAUTIFUL IDEA
19th century. The 20th century was then profoundly af-
fected by its applications. A similar adventure is pos-
The idea of QC was ¬rst proposed only in the 1970™s
sibly happening for quantum mechanics, discovered and
by Wiesner2 (1983) and by Charles H. Bennett from
formalized during the last century. Indeed, although the
IBM and Gilles Brassard from Montr´al University (1984,
e
laser and semiconductors are already common, applica-
3
1985) . However, this idea is so simple that actually ev-
tions of the most radical predictions of quantum mechan-
ery ¬rst year student since the infancy of quantum me-
ics have been thought of only recently and their full power
chanics could have discovered it! Nevertheless, it is only
remains a fresh gold mine for the physicists and engineers
of the 21st century. nowadays that the matter is mature and information se-
curity important enough, and “ interestingly “ only nowa-
The most peculiar characteristics of quantum mechan-
days that physicists are ready to consider quantum me-
ics are the existence of indivisible quanta and of entan-
chanics, not only as a strange theory good for paradoxes,
gled systems. Both of these are at the root of Quantum
but also as a tool for new engineering. Apparently, infor-
Cryptography (QC) which could very well be the ¬rst
mation theory, classical cryptography, quantum physics
commercial application of quantum physics at the indi-
and quantum optics had ¬rst to develop into mature sci-
vidual quantum level. In addition to quantum mechan-
ics, the 20th century has been marked by two other major ences. It is certainly not a coincidence that QC and, more
generally, quantum information has been developed by a
scienti¬c revolutions: the theory of information and rel-
community including many computer scientists and more
ativity. The status of the latter is well recognized. It
mathematics oriented young physicists. A broader inter-
is less known that the concept of information, nowadays
est than traditional physics was needed.
measured in bits, and the formalization of probabilities is
quite recent1 , although they have a tremendous impact
on our daily life. It is fascinating to realize that QC lies at
A. The intuition
the intersection of quantum mechanics and information
theory and that, moreover, the tension between quan-
tum mechanics and relativity “ the famous EPR paradox Quantum Physics is well-known for being counter-
(Einsteinet al.1935) “ is closely connected to the security intuitive, or even bizarre. We teach students that Quan-
of QC. Let us add a further point for the young physicists. tum Physics establishes a set of negative rules stating
Contrary to laser and semiconductor physics, which are things that cannot be done. For example:
manifestations of quantum physics at the ensemble level
1. Every measurement perturbs the system.
and can thus be described by semi-classical models, QC,
and even much more quantum computers, require a full
2. One cannot determine simultaneously the position
quantum mechanical description (this may o¬er interest-
and the momentum of a particle with arbitrary high
ing jobs for physicists well trained in the subtleties of
accuracy.
their science).
This review article has several objectives. First we 3. One cannot measure the polarization of a photon in
present the basic intuition behind QC. Indeed the basic the vertical-horizontal basis and simultaneously in
idea is so beautiful and simple that every physicist and the diagonal basis.
every student should be given the pleasure to enjoy it.
The general principle is then set in the broader context of
modern cryptology (section II B) and made more precise
(section II C). Chapter III discusses the main technologi- 2
Stephen Wiesner, then at Columbia University, was the
cal challenges. Then, chapters IV and V present the most ¬rst one to propose ideas closely related to QC, already in
common implementation of QC using weak laser pulses the 1970™s. However, his revolutionary paper appeared only a
and photon pairs, respectively. Finally, the important decade later. Since it is di¬cult to ¬nd, let us mention his ab-
and di¬cult problems of eavesdropping and of security stract: The uncertainty principle imposes restrictions on the
proofs are discussed in chapter VI, where the emphasis is capacity of certain types of communication channels. This pa-
more on the variety of questions than on technical issues. per will show that in compensation for this “quantum noise”,
We tried to write the di¬erent parts of this review in such quantum mechanics allows us novel forms of coding without
analogue in communication channels adequately described by
classical physics.
3
Artur Ekert (1991) from Oxford University discovered QC
independently, though from a di¬erent perspective (see para-
1
The Russian mathematician A.N. Kolmogorow (1956) is
graph II D 3).
credited with being the ¬rst to have consistently formulated
a mathematical theory of probabilities in the 1940™s.



2
4. One cannot draw pictures of individual quantum channel to transmit information, but only to transmit a
random sequence of bits, i.e. a key. Now, if the key is
processes.
unperturbed, then Quantum Physics guarantees that no
5. One cannot duplicate an unknown quantum state. one got any information about this key by eavesdropping
(i.e. measuring) the quantum communication channel.
This negative viewpoint on Quantum Physics, due to
In this case, Alice and Bob can safely use this key to
its contrast to classical physics, has only recently been
encode messages. If, on the contrary, the key turns out
turned positive and QC is one of the best illustrations
to be perturbed, then Alice and Bob simply disregard it;
of this psychological revolution. Actually, one could car-
since the key does not contain any information, they did
icature Quantum Information Processing as the science
not lose any.
of turning Quantum conundrums into potentially useful
Let us make this general idea somewhat more pre-
applications.
cise, anticipating section II C. In practice, the individual
Let us illustrate this for QC. One of the basic negative
quanta used by Alice and Bob, often called qubits (for
statement of Quantum Physics reads:
quantum bits), are encoded in individual photons. For
example, vertical and horizontal polarization code for bit
Every measurement perturbs the system (1)
value zero and one, respectively. The second basis, can
then be the diagonal one (±45o linear polarization), with
(except if the quantum state is compatible with the mea-
+45o for bit 1 and ’45o for bit 0, respectively (see Fig.
surement). The positive side of this axiom can be seen
1). Alternatively, the circular polarization basis could
when applied to a communication between Alice and
be used as second basis. For photons the quantum com-
Bob (the conventional names of the sender and receiver,
munication channel can either be free space (see section
respectively), provided the communication is quantum.
IV E) or optical ¬bers “ special ¬bers or the ones used in
The latter means that the support of information are
standard telecommunication “ (section III B). The com-
quantum systems, like, for example, individual photons.
munication channel is thus not really quantum. What is
Indeed, then axiom (1) applies also to the eavesdroppers,
quantum are the information carriers.
i.e. to a malicious Eve (the conventional name given to
But before continuing, we need to see how QC could
the adversary in cryptology). Hence, Eve cannot get any
¬t in the existing cryptosystems. For this purpose the
information about the communication without introduc-
next section brie¬‚y surveys some of the main aspects of
ing perturbations which would reveal her presence.
modern cryptology.
To make this intuition more precise, imagine that Alice
codes information in individual photons which she sends
to Bob. If Bob receives the photons unperturbed, then,
B. Classical cryptography
by the basic axiom (1), the photons were not measured.
No measurement implies that Eve did not get any in-
formation about the photons (note that acquiring infor- Cryptography is the art of rendering a message un-
mation is synonymous to carrying out measurements). intelligible to any unauthorized party. It is part of the
Consequently, after exchanging the photons, Alice and broader ¬eld of cryptology, which also includes crypto-
Bob can check whether someone “was listening”: they analysis, the art of code breaking (for a historical per-
simply compare a randomly chosen subset of their data spective, see Singh 1999). To achieve this goal, an algo-
using a public channel. If Bob received the randomly rithm (also called a cryptosystem or cipher) is used to
chosen subset unperturbed then the logic goes as follows: combine a message with some additional information “
known as the “key” “ and produce a cryptogram. This
technique is known as “encryption”. For a cryptosystem
N o perturbation ’ N o measurement to be secure, it should be impossible to unlock the cryp-
’ N o eavesdropping (2) togram without the key. In practice, this demand is often
softened so that the system is just extremely di¬cult to
It is as simple as that! crack. The idea is that the message should remain pro-
tected at least as long as the information it contains is
Actually, there are two more points to add. First, in valuable. Although con¬dentiality is the traditional ap-
order to ensure that axiom (1) applies, Alice encodes her plication of cryptography, it is used nowadays to achieve
information in non-orthogonal states (we shall illustrate broader objectives, such as authentication, digital signa-
this in the sections II C and II D). Second, as we have tures and non-repudiation (Brassard 1988).
presented it so far, Alice and Bob could discover any
eavesdropper, but only after they exchanged their mes-
sage. It would of course be much better to ensure the 1. Asymmetrical (public-key) cryptosystems
privacy in advance, and not afterwards! To achieve this,
Alice and Bob complement the above simple idea with a Cryptosytems come in two main classes “ depending on
second idea, again a very simple one, and one which is whether Alice and Bob use the same key. Asymmetrical
entirely classical. Alice and Bob do not use the quantum

3
systems involve the use of di¬erent keys for encryption ers.
and decryption. They are commonly known as public-key Similarly, all public-key cryptosystems rely on un-
cryptosystems. Their principle was ¬rst proposed in 1976 proven assumptions for their security, which could them-
by Whit¬eld Di¬e and Martin Hellman, who were then selves be weakened or suppressed by theoretical or prac-
at Stanford University in the US. The ¬rst actual im- tical advances. So far, no one has proved the existence of
plementation was then developed by Ronald Rivest, Adi any one-way function with a trapdoor. In other words,
Shamir,and Leonard Adleman of the Massachusetts In- the existence of secure asymmetric cryptosystems is not
stitute of Technology in 19784. It is known as RSA and is proven. This casts an intolerable threat on these cryp-
still widely used. If Bob wants to be able to receive mes- tosystems.
sages encrypted with a public key cryptosystem, he must In a society where information and secure communi-
¬rst choose a “private” key, which he keeps secret. Then, cation is of utmost importance, as in ours, one cannot
he computes from this private key a “public” key, which tolerate such a threat. Think, for instance, that an
he discloses to any interested party. Alice uses this public overnight breakthrough in mathematics could make elec-
key to encrypt her message. She transmits the encrypted tronic money instantaneously worthless. To limit such
message to Bob, who decrypts it with the private key. economical and social risks, there is no possibility but
Public-key cryptosystems are convenient and they have to turn to symmetrical cryptosystems. QC has a role to
thus become very popular over the last 20 years. The play in such alternative systems.
security of the internet, for example, is partially based
on such systems. They can be thought of as a mailbox,
where anybody can insert a letter. Only the legitimate 2. Symmetrical (secret-key) cryptosystems
owner can then recover it, by opening it with his private
key. Symmetrical ciphers require the use of a single key for
The security of public key cryptosystems is based on both encryption and decryption. These systems can be
computational complexity. The idea is to use mathemat- thought of as a safe, where the message is locked by Al-
ical objects called one-way functions. By de¬nition, it ice with a key. Bob in turns uses a copy of this key to
is easy to compute the function f (x) given the variable unlock the safe. The “one-time pad”, ¬rst proposed by
x, but di¬cult to reverse the calculation and compute x Gilbert Vernam of AT&T in 1926, belongs to this cate-
from f (x). In the context of computational complexity, gory. In this scheme, Alice encrypts her message, a string
the word “di¬cult” means that the time to do a task of bits denoted by the binary number m1 , using a ran-
grows exponentially with the number of bits in the in- domly generated key k. She simply adds each bit of the
put, while “easy” means that it grows polynomially. In- message with the corresponding bit of the key to obtain
tuitively, it is easy to understand that it only takes a few the scrambled text (s = m1 • k, where • denotes the
seconds to work out 67 — 71, but it takes much longer binary addition modulo 2 without carry). It is then sent
to ¬nd the prime factors of 4757. However, factoring has to Bob, who decrypts the message by subtracting the key
a “trapdoor”, which means that it is easy to do the cal- (s–k = m1 •k –k = m1 ). Because the bits of the scram-
culation in the di¬cult direction provided that you have bled text are as random as those of the key, they do not
some additional information. For example, if you were contain any information. This cryptosystem is thus prov-
told that 67 was one of the prime factors of 4757, the ably secure in the sense of information theory (Shannon
calculation would be relatively simple. The security of 1949). Actually, this is today the only provably secure
RSA is actually based on the factorization of large inte- cryptosystem!
gers. Although perfectly secure, the problem with this sys-
In spite of its elegance su¬ers from a major ¬‚aw. tem is that it is essential for Alice and Bob to possess a
Whether factoring is “di¬cult” or not could never be common secret key, which must be at least as long as the
proven. This implies that the existence of a fast algo- message itself. They can only use the key for a single en-
rithm for factorization cannot be ruled out. In addi- cryption “ hence the name “one-time pad”. If they used
tion, the discovery in 1994 by Peter Shor of a polynomial the key more than once, Eve could record all of the scram-
algorithm allowing fast factorization of integers with a bled messages and start to build up a picture of the plain
quantum computer puts additional doubts on the non- texts and thus also of the key. (If Eve recorded two di¬er-
existence of a polynomial algorithm for classical comput- ent messages encrypted with the same key, she could add
the scrambled text to obtain the sum of the plain texts:
s1 • s2 = m 1 • k • m 2 • k = m 1 • m 2 • k • k = m 1 • m 2 ,
where we used the fact that • is commutative.) Fur-
4
thermore, the key has to be transmitted by some trusted
According to the British Government, public key cryptog-
means, such as a courier, or through a personal meeting
raphy was originally invented at the Government Communica-
between Alice and Bob. This procedure can be complex
tions Headquarters in Cheltenham as early as in 1973. For an
historical account, see for example the book by Simon Singh and expensive, and may even amount to a loophole in
(1999). the system.


4
and conventions5. The interdisciplinary character of QC
Because of the problem of distributing long sequences
of key bits, the one-time pad is currently used only for the is the probable reason for its relatively slow start, but
most critical applications. The symmetrical cryptosys- it certainly contributes crucially to the vast and fast ex-
tems in use for routine applications such as e-commerce pansion over the recent years.
employ rather short keys. In the case of the Data En- We shall explain the BB84 protocol using the language
1
cryption Standard (also known as DES, promoted by the of spin 2 , but clearly any 2-level quantum system would
United States™ National Institute of Standards and Tech- do. The protocol uses 4 quantum states that constitute
nology), a 56 bits key is combined with the plain text 2 bases, think of the states up | ‘ , down | “ , left | ←
divided in blocks in a rather complicated way, involving and right | ’ . The bases are maximally conjugate in
permutations and non-linear functions to produce the ci- the sense that any pair of vectors, one from each basis,
1
has the same overlap, e.g. | ‘ | ← |2 = 2 . Convention-
pher text blocks (see Stallings 1999 for a didactic pre-
sentation). Other cryptosystems (e.g. IDEA or AES) ally, one attributes the binary value 0 to states | ‘ and
follow similar principles. Like asymmetrical cryptosys- | ’ and the value 1 to the other two states, and calls
tems, they o¬er only computational security. However the states qubits (for quantum bits). In the ¬rst step,
for a given key length, symmetrical systems are more se- Alice sends individual spins to Bob in states chosen at
cure than their asymmetrical counterparts. random among the 4 basic states (in Fig. 1 the spin
In practical implementations, asymmetrical algorithms states | ‘ ,| “ , | ’ and | ← are identi¬ed with the
polarization states “horizontal”, “verical”, “+45o” and
are not so much used for encryption, because of their
“-45o”, respectively). How she “chooses at random” is
slowness, but to distribute session keys for symmetrical
cryptosystems such as DES. Because the security of those a delicate problem in practice (see section III D), but in
algorithms is not proven (see paragraph II B 1), the secu- principle she could use her free will. The individual spins
rity of the whole implementation can be compromised. If could be sent all at once, or one after the other (much
they were broken by mathematical advances, QC would more practical); the only restriction being that Alice and
constitute the only way to solve the key distribution Bob can establish a one-to-one correspondence between
problem. the transmitted and the received spins. Next, Bob mea-
sures the incoming spins in one of the two bases, chosen
at random (using a random number generator indepen-
dent from that of Alice). At this point, whenever they
3. The one-time-pad as “classical teleportation”
used the same basis, they get perfectly correlated results.
However, whenever they used di¬erent basis, they get
The one-time-pad has an interesting characteristic.
uncorrelated results. Hence, on average, Bob obtains a
Assume that Alice aims at transferring to Bob a faithful
string of bits with 25% errors, called the raw key. This er-
copy of a classical system, without giving any informa-
ror rate is so large that standard error correction schemes
tion to Eve about this system. For this purpose Alice
would fail. But in this protocol, as we shall see, Alice and
and Bob have only access to an insecure classical chan-
Bob know which bits are perfectly correlated (the ones for
nel. This is possible provided they share an arbitrary
which Alice and Bob used the same basis) and which ones
long secret key. Indeed, in principle Alice can measure
are completely uncorrelated (all the other ones). Hence,
the state of her classical system with arbitrary high pre-
a straightforward error correction scheme is possible: For
cision and then use the one-time-pad to securely commu-
each bit Bob announces publicly in which basis he mea-
nicate this information to Bob who can then, in principle,
sured the corresponding qubit (but he does not tell the
reconstruct (a copy of) the classical system. This some-
result he obtained). Alice then only tells whether or not
what arti¬cial use of the one-time-pad has an interesting
the state in which she encoded that qubit is compatible
quantum relative, (see section II E).
with the basis announced by Bob. If the state is com-
patible, they keep the bit, if not they disregard it. In
this way about 50% of the bit string is discarded. This
C. The example of the BB84 protocol
shorter key obtained after bases reconciliation is called
the sifted key6 . The fact that Alice and Bob use a public
1. Principle
channel at some stage of their protocol is very common
The ¬rst protocol for QC has been proposed in 1984
by Charles H. Bennett, from IBM New-York, and Gilles
Brassard, from the University of Montreal, hence the 5
For instance, it is amusing to note that physicists must
name BB84 under which this protocol is recognized nowa-
publish in reputed journals while conference proceedings are
days. They published their work in a conference in In-
of secondary importance. For computer science, on the con-
dia, totally unknown to physicists. This underlines at
trary, the proceedings of the best conferences are considered
once that QC needs the collaboration between di¬erent
as the top, while journals are secondary!
communities, with di¬erent jargons and di¬erent habits 6
This terminology has been introduced by Ekert and Hut-
tner in 1994.


5
in crypto-protocols. This channel does not have to be But the latter state di¬ers from the ideal copy | ’, ’
con¬dential, but has to be authentic. Hence, any ad- , f’ , whatever the states |fψ are.
versary Eve can listen to all the communication on the Consequently, Eve can™t keep a perfect quantum copy,
public channel, but she can™t modify it. In practice Al- because perfect quantum copy machines can™t exist. The
ice and Bob may use the same transmission channel to possibility to copy classical information is probably one
implement both the quantum and the classical channels. of the most characteristic features of information in the
Note that neither Alice nor Bob can decide which key every day sense. The fact that quantum states, nowadays
results from the protocol7 . Indeed, it is the conjunction often called quantum information, can™t be copied is cer-

. 1
( : 11)



. . >>