QUANTUM CRYPTOGRAPHY Schrödinger's catflap Ian Stewart

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