THE military and commercial use of
ciphers
has a lengthy history, but
cryptography
only became a branch of mathematics in the 1940s, when Claude Shannon invented
**communication theory**. The main thrust of the mathematical approach
was towards error detection and correction, and the methods were algebraic
and combinatorial. The discovery of
public key
cryptosystems** **- in which methods for encrypting messages can be
made public, but decryption is virtually impossible in the absence of a secret
piece of information - introduced ideas about the efficiency of computational
methods. It is possible to go beyond classical computation, however; and
an emerging branch of the subject, known as
quantum
cryptography, does just that. Artur Ekert has now explained *(Phys.
Rev. Lett. ***67**, 661-663; 1991) how ideas based upon the Einstein-
Podolsky-Rosenberg (EPR)
'paradox'
in quantum theory can be used to guarantee secure distribution of a cryptographic
key. A forthcoming paper by Charles C. Bennett, Francois Bessette, Gilles
Brassard, Louis Salvail and John Smolin, to appear in the *Journal of
Cryptology, *involves very similar ideas, and also describes the history
of the subject.
Quantum cryptography began in
the late 1960s with unpublished work by Stephen Wiesner, who explained how
quantum effects can in principle be used to manufacture banknotes immune
to counterfeiting, and to transmit information securely. His work was eventually
published *(Sigact News ***15**, 78-88; 1983) at Bennett's instigation.
The unfakeable banknote requires the ability to store a single **polarized
photon **for several days without change of state. As Bennett *et al.
*say: "Unfortunately the impact of the CRYPTO 82 conference had left most
people under the impression that everything having to do with quantum
cryptography was doomed from the start to being unrealistic". However, in
1982 Bennett and Brassard realized that photons are not for storing information,
but for transmitting it. Quantum versions of many mainstays of cryptography
then appeared, including the self-winding reusable one-time pad,
quantum
coin-tossing, quantum oblivious transfer, zero-knowledge protocols and
**secure two-party computations**. Here I'll consider only the quantum
key distribution channel.
Security
of a cryptotext used to depend upon keeping the entire process of encryption
and decryption secret. Nowadays, the encryption and decryption procedures
can be public knowledge, provided only that a specific piece of information,
the key, is kept secret from illegitimate users or eavesdroppers. The key
can be any random
string of digits. The danger with this approach is that all eggs are
invested in one basket, the key. Before secure communication can begin, the
key must be distributed securely to users. During the Second World War one
rather amateur group of spies distributed new code keys by radio to possibly
compromised agents, using the old (equally compromised) code. This is hardly
an acceptable solution to the problem; but more subtle distribution methods
might also be open to eaves dropping.
Consider a specific example, an eavesdropper trying to monitor a communication
channel, say by tapping a telephone line. Observations of any system disturb
it and so leave traces. Legitimate users can try to guard against this by
making their own measurements on the line, to detect the effects of tapping.
However, the tappers will be safe provided they can make measurements that
produce smaller disturbances than the legitimate users can detect. In classical
(that is, nonquantum) mechanics, this kind of 'arms race' of increasingly
sensitive measurements can go on indefinitely ("big bugs have little bugs"
and so on).
In quantum mechanics it cannot, however, because of the Heisenberg uncertainty
principle. Measurements of some quantities, however delicately conducted,
may change other related quantities by significant and irreducible amounts.
In the conventional interpretation, a quantum system exists in a superposition
of possible states, until a measurement is made, forcing' it into a pure
state. This view is dramatized by the unenviable fate of Schrödinger's
cat, which lives inside an impenetrable box, and is alive if a particular
particle has positive spin, dead if it has negative spin. Until the box is
opened, the unfortunate beast is neither alive nor dead, but in a quantum
superposition of the two states.
It is here that the EPR paradox, proposed in 1935, enters. The idea was
simplified by David Bohm, and it is his version that I will describe. The
proton is a particle with spin ½. Its (spin) angular momentum, measured
in any direction, is therefore ± ½*h*, where *h *=
h/2p and *h *is Planck's constant. Begin
with a system of two protons, very close together, of total angular momentum
zero, a situation that can be realized in practice. If the angular momentum
of one proton in a given direction is ½*h, *then that of the other
must be *-*½*h; *if that of the first is *-*½*h
*then that of the second must be ½*h*. It is not necessary to
measure these quantities for this relation to hold - indeed it is important
not to, because measurements in quantum mechanics disturb the system being
measured. Assume that the protons move apart until the distance between them
is large: the relations between the angular momenta will remain valid. If
we now measure a component of angular momentum for one proton, then the result
forces a definite state of angular momentum in that direction for its distant
companion. This kind of
'action at a
distance' seemed to Einstein, Podolsky and Rosenberg to be paradoxical,
and they concluded that quantum mechanics must be an incomplete description
of reality. But John Bell subsequently derived a theoretical relationship,
Bell's inequality, that permits experiments to test the EPR paradox. The
results confirmed the predictions of quantum mechanics.
**SPIES, LIES AND BUTTERFLIES** A
new government report has revealed that the number of mistakes made by the
UK's security services when applying to tap people's phones has risen more
than six fold in the last year. Most errors involved an attempt to tap the
wrong number. With fears of terrorism loosening restrictions on what the
authorities are allowed to do, even the most law-abiding citizen could be
forgiven for feeling paranoid. However there may be help at hand. A new study
has shown that keeping calls confidential needn't involve complex technologies
such as quantum cryptography. The key is
chaos - specifically, the strange
phenomenon of the
butterfly effect...
[New Scientist 22/11/05] |
Ekert's communication channel (that of Bennett *et al. *is similar)
repeats the EPR model once per bit (binary digit's worth) of transmitted
message. It is a source that emits pairs of spin ½ particles in opposite
directions - that is, a box with a catflap at each end, which emits pairs
of perfectly anti-correlated Schrödinger's cats in a constant stream.
If one cat in a given pair is alive, then the other is dead, but until their
state is measured, we do not know which is which. At opposite ends of this
axis are two time-honoured characters in the lore of cryptography,
Alice and
Bob, who represent the legitimate users of the channel. Their task is
to extract from the sequence of EPR-linked particles a common key, and also
to monitor the channel against eavesdropping.
To this end, they each measure components of angular momentum, in orientations
which they select randomly and independently for each incoming particle,
thereby determining the conditions of their respective cats. Alice has the
choice of measuring at angles of 0°, 45° or 90° in a plane
perpendicular to the communication axis; Bob at angles of 45°, 90°0
or 135°.** **Each such measurement yields a result of + 1 or - 1
(in units of ½*h*), and potentially reveals one bit of information.
If Alice and Bob measure angular momentum in identical orientations, then
their results are totally anti-correlated: the state of Bob's cat is always
the exact opposite to that of Alice's. But if they use different orientations,
it can be shown that a particular combination *S *of correlations must
be -2Ö2.
After transmission, Alice and Bob publicly announce the sequence of orientations
they have chosen, and thus can privately divide their measurements into two
groups: those for which they used the same orientation, and those for which
they used different ones. They also announce the actual measurements they
obtained in the second group, so that they both can compute the quantity
*S*. If the channel has not been disturbed by an eavesdropper, the value
should be *S* = -2Ö2. If that is the
case, then the first group of perfectly anticorrelated measurements (whose
values are known only to Alice and Bob) can be used to establish a common
key.
The system is not secure to an eavesdropper who taps the channel only when
Alice and Bob are measuring identical directions; but because they choose
directions randomly, there is no way to achieve this without the services
of an 'oracle' - and an oracle can defeat any system far more simply, just
by intuiting the key. An eavesdropper might attempt to subvert the entire
procedure by setting up a fake source that emits three particles rather than
two, and intercept ing the third stream of particles to see which way the
cat jumps. Delayed measurements of those states, made after Alice and Bob
announce their results to the world and in particular to each other might
reveal the key to the eavesdropper. Ekert conjectures that in fact there
is no way to achieve this; and notes that in any case the eavesdropper runs
into the 'banknote problem' of storing the particles with out degradation
of state until the announcement is made.
Experimental methods designed to test Bell's inequalities, such as those
of A. Aspect, P. Grangier and G. Roger *(Phys. Rev. Lett ***49**,
91; 1982) could be used to implement this scheme (over short distances) in
a relatively practical manner. For quantum cryptography, Schrödinger's
cat is out of the bag.
*Ian Stewart is in the Mathematics
Institute,Warwick University,Coventry
CV4 7AL,UK.*
NATURE VOL 353. 3 OCTOBER
1991 |