Research into new ways of performing
cryptography continues. We have seen how researchers have relied on aspects of
mathematics to generate hard problems and to devise algorithms. In this
section, we look at an alternative view of how cryptography may be done in the
future. The approach we describe is not now on the market, nor is it likely to
be so in the next few years. But it illustrates the need for creative thinking
in inventing new encryption techniques. Although the science behind this
approach is very difficult, the approach itself is really quite simple.
The novel approach, quantum cryptography, is in
a way a variant of the idea behind a one-time pad. Remember from Chapter 2 that the one-time pad is the only
provably unbreakable encryption scheme. The one- time pad requires two copies
of a long string of unpredictable numbers, one copy each for the sender and
receiver. The sender combines a number with a unit of plaintext to produce the
ciphertext. If the numbers are truly unpredictable (that is, they have
absolutely no discernible pattern), the attacker cannot separate the numbers
from the ciphertext.
The difficulty with this approach is that there
are few sources of sharable strings of random numbers. There are many natural
phenomena that could yield a string of unpredictable numbers, but then we face
the problem of communicating that string to the receiver in such a way that an
interceptor cannot obtain them. Quantum cryptography addresses both problems,
generating and communicating numbers. It was first explored by Wiesner [WIE83] in the 1980s; then the idea was developed
by Bennett a decade later [BEN92a, BEN92b].
Quantum cryptography operates by sending a
stream of photons from sender to receiver. The sender uses one of the
polarizing filters to control which kind of photon is sent. The receiver uses
either filter and records the orientation of the photon received. It does not
matter if the receiver chooses the same filter the sender did; what matters is
whether the receiver happened by chance to choose the same type as did the
The most important property of quantum
cryptography is that no one can eavesdrop on a communication without affecting
the communication. With a little simple error detection coding, the sender and
receiver can easily determine the presence of an eavesdropper. Heisenberg's
uncertainty principle says that we cannot know both the speed and location of a
particle at any given time; once we measure the speed, the location has already
changed, and once we measure the location, the speed has already changed.
Because of this principle, when we measure any property of a particle, it
affects other properties. So, for example, measuring the orientation of a
photon affects the
Let us see how this unusual approach can be used for cryptography.
Cryptography with Photons
The cryptographic algorithm is very inefficient, in that more than twice the bits transmitted are not used in cryptography. The bits being transmitted are photons which, fortunately, are very highly available.
Some of those results are correct and some are incorrect, depending on the filter Ruth chose. Now Ruth sends to Sam the kind of filter she used, as shown in Figure 12-20.
Sam tells Ruth which filters were the correct
ones she used, as shown in Figure 12-21,
from which Ruth can determine which of the results obtained were correct, as
shown in Figure 12-22. In this example,
Ruth happened to choose the right filter six times out of ten, slightly
higher than expected, and so six of the ten photons transmitted were received correctly. Remembering that means 1, Ruth can convert the photons to bits, as shown in the figure. In general, only half the photons transmitted will be received correctly, and so only half the bandwidth of this communication channel carries meaningful data.
Notice that Ruth can tell Sam which filters she
used and Sam can tell Ruth which of those will yield correct results without
revealing anything about the actual bits transmitted. In this way, Sam and Ruth
can talk about their transmission without an eavesdropper's knowing what they
The theory of quantum cryptography is solid,
but some technical difficulties still must be worked out before the scheme can
be put in practice. To implement quantum cryptography, we need a source of
photons randomly but detectably oriented (for the sender) and a means of
filtering the received photons reliably. A photon gun can fire photons on
demand. Several different research teams are working to develop photon guns for
cryptography, but so far none has succeeded. The best current technology
involves pulsed lasers, but here, too, there is a problem. Occasionally the
laser emits not one but two photons, which disturbs the pattern of reception
and transmission. However, with error correcting codes on the stream of bits,
it is relatively easy to detect and correct a few erroneous bits.
On the receiving side, too, there are problems.
One device is subject to catastrophic failure in which it emits a current
surge. Although this surge is easily detected, it requires the device to be
reset, which takes time.
Experimental implementations of quantum
cryptography are still in the laboratories. The U.K. Defence Evaluation and
Research Agency in Malvern, England, demonstrated a successful communication
through the atmosphere over a distance of 2 km, and the U.S. Los Alamos
National Laboratory is testing a portable device that can operate over 45 km on
a clear night. In 2006, the U.S. National Institute for Standards and
Technology has demonstrated a quantum cryptographic system that operates over
one kilometer over glass fiber at a rate of four megabits per second. In 2004,
BBN Communications and Harvard University activated a joint network secured by
quantum encryption. The network has six servers and covers a distance of ten
kilometers. Reliable communications up to 20 kilometers have been achieved, and
some scientists expect to be able to cover 50 kilometers reliably in the near
future. (See [ELL04] for a discussion of
the potential of quantum cryptography.)
These results, all obtained within the past few
years, show significant progress as quantum cryptography moves from the
research bench to the prototype lab. Although still not ready for widespread
public adoption, quantum cryptography is becoming a real possibility for
commercial use within the next decade.