A Quantum Leap for Cryptography

Introduction Cryptography

Classical physics is adequate for the description of Cryptography is the art of rendering information

macroscopic objects. It applies basically to systems exchanged between two parties unintelligible to any

larger than one micron (1 micron = 1 millionth of a unauthorized person. Cryptography is an old

meter). It was developed gradually and was science. However, until the development of

basically complete by the end of the XIXth century. electronic and optical telecommunications, its scope

At that time, the fact that classical physics did not of applications remained mainly restricted to military

always provide an adequate description of physical and diplomatic purposes. In the past twenty-five

phenomena became clear. A radically new set of years, cryptography evolved, from its status of

theories, quantum physics, was consequently "classified" science and offers now solutions to

developed by physicists such as Max Planck and guarantee the secrecy of the ever-expanding civilian

Albert Einstein, during the first thirty years of the telecommunication networks. Although

XXth century. Quantum physics describes confidentiality “ the focus of this paper “ is the

adequately the microscopic world (molecules, traditional application of cryptography, it is used

atoms, elementary particles), while classical physics nowadays to achieve broader objectives, such as

remains accurate for macroscopic objects. The authentication, digital signatures and non-

repudiation1.

predictions of quantum physics drastically differ

from those of classical physics. For example, it The way cryptography works can be illustrated with

features intrinsic randomness, while classical Fig. 1. Before transmitting sensitive information, the

physics is deterministic. It also imposes limitation on sender “ traditionally called Alice “ combines the

the accuracy of the measurement that can be plain text with a secret key, using some encryption

performed on a system (Heisenberg's uncertainty algorithm, to obtain the cipher text. This scrambled

principle). message can now be sent to the recipient “ Bob “

Although quantum physics had a strong influence who reverses the process to recover the plain text

th

on the technological development of the XX by combining the cipher text with the secret key

century “ it allowed for example the invention of the using the decryption algorithm. An eavesdropper “

transistor or the laser “ its impact on the processing Eve “ cannot deduce the plain message from the

of information has only been understood recently. scrambled one, without knowing the key. To

“Quantum information processing” is a new and illustrate this principle, imagine that Alice puts her

dynamic research field at the crossroads of message in a safe and locks it with a key. Bob uses

quantum physics and computer science. It looks at in turn his key to unlock the safe.

the consequence of encoding digital bits “ the Numerous encryption algorithms exist. Their relative

elementary units of information “ on quantum security essentially depends on the length of the key

system. Does it make a difference if a bit is written they use: the more bits the key contains, the better

on a piece of paper, stored in an electronic chip, or

encoded on a single electron? Applying quantum

Alice Bob

physics to information processing yields

revolutionary properties and possibilities, without Plain text Plain text

any equivalent in conventional information theory. In

order to emphasize this difference, a digital bit is

called a quantum bit or a "qubit" in this context. With

Cipher text

the miniaturization of microprocessors, which will 53d%6(

Encryption Decryption

reach the quantum limit in the next fifteen to twenty è#%jkfs¦

"&$£¨}ffa

years, this new field will necessarily become more

and more prominent. Its ultimate goal is the

development of a fully quantum computer,

possessing massively parallel processing Key Key

capabilities.

Although this goal is still quite distant, the first Figure 1: Principle of cryptography.

applications of quantum information processing

have recently been introduced by id Quantique, a

the security. One of the most common algorithm “

spin-off company of the university of Geneva. The

the Data Encryption Standard or DES “ has a 56

first one, the generation of random numbers, will

bits key. Since it can be cracked in a few hours with

only be briefly mentioned in this paper. It exploits

powerful computers, it is not considered secure any

the fundamentally random nature of quantum

longer and will shortly be replaced by the Advanced

physics to produce high quality random numbers,

Encryption Standard “ AES “ which has a 256 bits

for cryptographic applications for example. id

key. In addition to its length, the amount of

Quantique's QRNG is the first commercial product

information encrypted with a given key also

based on this principle. The second application,

called quantum cryptography, exploits Heisenberg's

uncertainty principle to allow two remote parties to 1

“The codebook”, Simon Singh, Fourth Estate, presents

exchange a cryptographic key. It is the main focus

an excellent non-technical introduction and historical

of this paper. perspective on cryptography.

Rue Cingria 10, CH-1205 Genève

Ph: +41 (0)22 379 69 29 Fax: +41 22 781 09 80

www.idquantique.com

2

influences the confidentiality of the scheme: the computer sufficiently powerful or enough time. The

more often a key is changed, the better the security. resources necessary to crack an algorithm depend

In the very special case where the key is as long as on the length of the key, which must thus be

the plain text and used only once “ this scheme is selected carefully. One must indeed assess the

called the “one-time pad” “ it can be shown that technological progress over the course of the time

decryption is simply impossible and that the scheme span during which the data encrypted will be

is absolutely secure. valuable. Eve can indeed record communications

As one usually assumes that the encryption and wait until she can afford a computer powerful

algorithm is disclosed, the secrecy of such a enough to crack them. This assessment is

scheme basically depends on the fact that the key is straightforward when the lifetime of the information

secret. This means first that the key generation is one or two years, as in the case of credit card

process must be appropriate, in the sense that it numbers, but quite difficult when it spans a decade.

must not be possible for a third party to guess or In 1977, the three inventors of RSA “ the most

deduce it. Truly random numbers must thus be used common public key cryptography algorithm “ issued

as key. Second, it must not be possible for a third a challenge to crack a cipher encrypted with a 129

party to intercept the key during its exchange decimal digits key (428 bits). They predicted at the

between Alice and Bob. This so-called “key time that this might not occur over 40 quadrillion

distribution problem” is very central in cryptography. years. The 100$ prize was claimed in 1994 by a

group of scientists working over the internet.

Besides, it has been shown theoretically that a

quantum computer, if it existed, could, with its

One-way functions

massively parallel processing abilities, reverse one-

The most common example of a one-way function is

way functions and crack public key cryptography.

factorization. The RSA public key system is actually based

The development of the first quantum computer will

on this mathematical problem. It is relatively easy to

compute the product of two integers “ say for example 37 — consequently immediately make the exchange of a

53 = 1961, because a practical method exists. On the other key with public key algorithms insecure.

hand, reversing this calculation “ finding the prime factors The second flaw is the fact that public key

of 1961 “ is tedious and time-consuming. No efficient

cryptography is vulnerable to progress in

algorithm for factorization has ever been disclosed. It is

mathematics. In spite of tremendous efforts,

important to stress however that there is no formal proof

mathematicians have not been able yet to prove

that such an algorithm does not exist. It may not have been

that public key cryptography is secure. It is has not

discovered yet or¦ it may have been kept secret.

been possible to rule out the existence of algorithms

that allow reversing one-way functions. The

discovery of such an algorithm would make public

Key distribution

key cryptography insecure overnight. It is even more

For years, it was believed that the only possibility to

difficult to assess the rate of theoretical progress

solve this key distribution problem was for Alice to

than that of technological advances. There are

send to Bob some physical medium “ a disk for

examples in the history of mathematics where one

example “ containing the key. In the digital era, this

person was able to solve a problem, which kept

requirement is clearly unpractical. In addition, it is

busy other researchers for years of decades. It took

not possible to check whether this medium was

for example half an hour to Clifford Cocks, of the

intercepted “ and its content copied “ or not.

GCHQ, to invent all the mathematics of public key

In the late sixties and early seventies, researchers

cryptography. It is even possible that such an

of the British "Government Communication

algorithm has already been discovered, but is kept

Headquarters" (GCHQ) invented an algorithm

secret. These two threats imply that public key

solving this problem. To take an image, it is as if

cryptography cannot securely solve the key

they replaced the safe mentioned above by a

exchange problem.

padlock. Before the communication, Bob sends an

open padlock to Alice, while keeping the key. Alice Quantum Cryptography

uses it to lock the data. Bob is the only one who can

unlock the data with the key he kept. “Public key Principle

cryptography” was born. This invention however

Quantum cryptography solves the key distribution

remained classified and was independently

problem by allowing the exchange of a

rediscovered in the mid-seventies by American

cryptographic key between two remote parties with

researchers. Formally, these padlocks are

absolute security guaranteed by the laws of physics.

mathematical functions called “one-way functions”,

This key can then be used with conventional

because they are easy to compute but difficult to

cryptographic algorithms. Hence, "quantum key

reverse (see Box). As public key cryptography

distribution" is a better name for this technology.

algorithms require complex calculations, they are

Contrary to what one could expect, the basic

slow. They can thus not be used to encrypt large

principle of quantum cryptography is quite

amount of data and are exploited in practice to

straightforward. It exploits the fact, that according to

exchange between Alice and Bob a short session

quantum physics, the mere fact of observing a

key for a secret-key algorithm such as DES.

system will perturb it in an irreparable way. When

In spite of the fact that it is extremely practical, the

you read this article for example, the sheet of paper

exchange of keys using public key cryptography

must be lighted. The impact of the light particles will

however suffers from two major flaws. First, it is

slightly heat it up and hence change it. This effect is

vulnerable to technological progress. Reversing a

very small on a piece of paper, which is a

one-way function can be done, provided one has a

Rue Cingria 10, CH-1205 Genève

Ph: +41 (0)22 379 69 29 Fax: +41 22 781 09 80

www.idquantique.com

3

macroscopic object. However, the situation is optical fiber. The devices are controlled by two PC's

radically different with a microscopic object: if one through the USB port.

encodes the value of a digital bit on a single The first important characteristic of a quantum

quantum system, an interception will necessarily cryptography system is the key exchange rate. It is

translate into a perturbation, because the low compared to the bit rates common in

eavesdropper is forced to observe it. This conventional telecommunication. id Quantique's

perturbation causes errors in the sequence of bits prototype can typically exchange a thousand bits

shared by Alice and Bob. By checking the presence per second. This low bit rate is the price to pay for

of such errors, the two parties can verify whether absolute secrecy. This limitation is not as critical as

their key was intercepted or not. It is important to it may look at first. The bits exchanged using

stress that since this verification takes place after quantum cryptography constitute a key, which is

the exchange of bits, one finds out a posteriori then used to encrypt data. These data can then be

whether the communication was eavesdropped or exchanged over a conventional channel at a high

not. That is why this technology is used to exchange rate. Using quantum cryptography, a 256 bits key

a key and not valuable information. Once the key is can typically be changed four times a second. An

validated, it can be used to encrypt data. Finally, it is additional important advantage of this technology is

important to insist on the fact that it is impossible to that a key can be generated on demand when it is

intercept the key without introducing perturbations. needed, simplifying key management and making

its storage useless.

Key transmission distance: the main limitation?

The second important characteristic of a quantum

cryptography system is the transmission distance.

Optical fibers, in spite of their very high quality, are

not perfectly transparent. When propagating, a

photon will sometimes get absorbed and thus not

reach the end of the fiber. In conventional

telecommunications, one deals with this problem by

Figure 2: id Quantique's quantum cryptography

using devices called optical repeaters. They are

system.

located approximately every 80 km and amplify the

signal. In quantum cryptography, it is not possible to

In practice use such repeaters. They would indeed have the

What does it mean in practice to encode the value same effect as an eavesdropper and corrupt the key

2

of a digital bit on a quantum system? In by introducing perturbations . Consequently the key

telecommunications, light is routinely used to exchange rate decreases with distance because

exchange information. For each bit of information, a less and less photon reach the end of the fiber. The

pulse is emitted and sent down an optical fiber to fact that some photons are absorbed in the fiber

the receiver where it is registered and transformed does not constitute a problem, because they just do

back into an electronic form. These pulses typically not enter in the final key. However, eventually when

contain millions of particles of light, called photons. the distance becomes too long, the number of

In quantum cryptography, one can follow the same photons that reach the receiver end just becomes

approach, with the only difference that the pulses too small to allow a key exchange.

contain only a single photon. A single photon With present technology, the distance is thus limited

represents a very tiny amount of light (when reading to about 70 km. id Quantique's prototype was

this article your eyes register billions of photons

every second) and follows the laws of quantum

physics. In particular, it cannot be split into halves.

This means that an eavesdropper cannot take half

of a photon to measure the value of the bit it carries,

while letting the other half continue its course. If he

wants to obtain the value of the bit, he must detect

the photon and will thus interrupt the communication

and reveal its presence. A more clever strategy is

for the eavesdropper to detect the photon, register

the value of the bit and prepare a new photon

according to the obtained result to send it to the

receiver. In quantum cryptography, Alice and Bob

cooperate to prevent the Eve from doing this, by Figure 3: id Quantique's system exchanged keys

forcing her to introduce errors (see Box). over 67 km of standard optical fiber.

Real world

recently used to exchange keys over 67 km of

Does quantum cryptography work in the real world? standard installed optical fiber between the Swiss

It does. The prototype developed by id Quantique cities of Geneva and Lausanne (see Fig. 3).

(see Fig. 2) was tested over standard optical fibers

part of the network of Swisscom “ a Swiss

telecommunication company. It allows exchanging a 2

Note that if it were possible to use repeaters, an

key between two stations “ Alice and Bob “ over an

eavesdropper could exploit them. The laws of quantum

physics forbid this.

Rue Cingria 10, CH-1205 Genève

Ph: +41 (0)22 379 69 29 Fax: +41 22 781 09 80

www.idquantique.com

4

It is clear that this distance can be increased by not even in laboratories, and much research

chaining quantum cryptography links with secure “ remains to be done.

Eve should not have access to them “ secure Implementation and applications

intermediary stations. Another way to increase the

Quantum cryptography is mature enough to allow

distance is to get rid of the optical fiber. It is possible

the exchange of a key over an optical fiber between

to exchange a key using quantum cryptography

two locations separated by a distance up to about

between a terrestrial station and a low orbit satellite

70 km. This key can then be used to secure all the

(Absorption in the atmosphere takes place mainly

communications (voice and data) between these

over the first few kilometers. It can be kept very low

two sites. The distance limitation restricts, initially at

by choosing an adequate wavelength¦ provided

least, the application of this technology to

the weather is good.). Such a satellite moves with

metropolitan area networks. It can for example be

respect to the earth surface. When passing over a

used between the offices of a financial institution

second station, located thousands of kilometers

located in a downtown area and its backoffice or

away from the first one, it can retransmit the key.

archive center in the suburbs. It can also be used

The satellite is implicitly considered as a secure

between ministers and government offices within a

intermediary station. This technology is less mature

capital.

than that based on optical fibers. Research groups

have already performed preliminary tests of such a Conclusion

system, but an actual key exchange with a satellite

For the first time in history, the security of encryption

remains to be done.

technology does not depend on the computer

There are also several theoretical proposals for

resources of the adversary. It is guaranteed in an

building quantum repeaters. They would relay qubits

absolute way by the laws of quantum physics. This

without measuring and thus perturbing them. They

quantum leap in security is made possible by

could, in principle, be used to extend the key

quantum cryptography.

exchange range over arbitrarily long distances. In

practice, such quantum repeaters do not exist yet,

References are available on www.idquantique.com

Principle

Eve

The value of each bit is encoded on the

property of a photon, its polarization for

Bob

example. The polarization of a photon is

the oscillation direction of its electric

field. It can be, for example, vertical,

horizontal, or diagonal (+45° and -45°).

Alice

Alice and Bob agree that:

"0" = or

"1" = or

1 For each key bit, Alice sends a photon, whose polarization is

randomly selected. She records these orientations.

A filter can be used to distinguish

between horizontal and vertical

2 For each incoming photon, Bob chooses randomly which filter he

photons; another one between diagonal

uses. He writes down its choice as well as the value he records.

photons (+45° and -45°).

If Eve tries to spy on the photon sequence, she modifies their

When a photon passes through the

polarization.

correct filter, its polarization does not

change.

3 After all the photons have been exchanged, Bob reveals, over a

conventional channel - the phone for example - to Alice the sequence

of filters he used.

When a photon passes through the

If Eve listens to their communication, she cannot deduce the key.

incorrect filter, its polarization is

modified randomly.

4 Alice tells Bob in which cases he chose the correct filter.

or or

5 Alice and Bob now know in which cases their bits should be identical -

when Bob used the correct filter. These bits form the final key.

or

or 6 Finally, Alice and Bob check the error level of the final key to validate it.

Rue Cingria 10, CH-1205 Genève

Ph: +41 (0)22 379 69 29 Fax: +41 22 781 09 80

www.idquantique.com