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-