1



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