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