The Code Book (60 page)

Authors: Simon Singh

Tags: ##genre

To summarize, quantum cryptography is a system that ensures the security of a message by making it hard for Eve to read accurately a communication between Alice and Bob. Furthermore, if Eve tries to eavesdrop then Alice and Bob will be able to detect her presence. Quantum cryptography therefore allows Alice and Bob to exchange and agree upon a onetime pad in complete privacy, and thereafter they can use this as a key to encrypt a message. The procedure has five basic steps:

(1) Alice sends Bob a series of photons, and Bob measures them.

(2) Alice tells Bob on which occasions he measured them in the correct way. (Although Alice is telling Bob when he made the correct measurement, she is not telling him what the correct result should have been, so this conversation can be tapped without any risk to security.)

(3) Alice and Bob discard the measurements that Bob made incorrectly, and concentrate on those measurements he made correctly in order to create an identical pair of onetime pads.

(4) Alice and Bob check the integrity of their onetime pads by testing a few of the digits.

(5) If the verification procedure is satisfactory, they can use the onetime pad to encrypt a message; if the verification reveals errors, they know that the photons were being tapped by Eve, and they need to start all over again.

Fourteen years after Wiesner’s paper on quantum money had been rejected by the science journals, it had inspired an absolutely secure system of communication. Now living in Israel, Wiesner is relieved that, at last, his work is being recognized: “Looking back, I wonder if I couldn’t have made more of it. People have accused me of being a quitter, for not having tried harder to get my idea published—I guess they’re right in a way—but I was a young graduate student, and I didn’t have that much confidence. In any case, nobody seemed interested in quantum money.”

Cryptographers greeted Bennett and Brassard’s quantum cryptography with enthusiasm. However, many experimentalists argued that the system worked well in theory, but would fail in practice. They believed that the difficulty of dealing with individual photons would make the system impossible to implement. Despite the criticism, Bennett and Brassard were convinced that quantum cryptography could be made to work. In fact, they had so much faith in their system that they did not bother building the apparatus. As Bennett once put it, “there is no point going to the North Pole if you know it’s there.”

However, the mounting skepticism eventually goaded Bennett into proving that the system could really work. In 1988 he began accumulating the components he would need for a quantum cryptographic system, and took on a research student, John Smolin, to help assemble the apparatus. After a year of effort they were ready to attempt to send the first message ever to be protected by quantum cryptography. Late one evening they retreated into their light-tight laboratory, a pitch-black environment safe from stray photons that might interfere with the experiment. Having eaten a hearty dinner, they were well prepared for a long night of tinkering with the apparatus. They set about the task of trying to send polarized photons across the room, and then measuring them using a +-detector and a ×-detector. A computer called Alice ultimately controlled the transmission of photons, and a computer called Bob decided which detector should be used to measure each photon.

After hours of tweaking, at around 3
A.M.
, Bennett witnessed the first quantum cryptographic exchange. Alice and Bob managed to send and receive photons, they discussed the polarization schemes that Alice had used, they discarded photons measured by Bob using the wrong detector and they agreed on a onetime pad consisting of the remaining photons. “There was never any doubt that it would work,” recalls Bennett, “only that our fingers might be too clumsy to build it.” Bennett’s experiment had demonstrated that two computers, Alice and Bob, could communicate in absolute secrecy. This was a historic experiment, despite the fact that the two computers were separated by a distance of just 30 cm.

Ever since Bennett’s experiment, the challenge has been to build a quantum cryptographic system that operates over useful distances. This is not a trivial task, because photons do not travel well. If Alice transmits a photon with a particular polarization through air, the air molecules will interact with it, causing a change in its polarization, which cannot be tolerated. A more efficient medium for transmitting photons is via an optic fiber, and researchers have recently succeeded in using this technique to build quantum cryptographic systems that operate over significant distances. In 1995, researchers at the University of Geneva succeeded in implementing quantum cryptography in an optic fiber that stretched 23 km from Geneva to the town of Nyon.

More recently, a group of scientists at Los Alamos National Laboratory in New Mexico has once again begun to experiment with quantum cryptography in air. Their ultimate aim is to create a quantum cryptographic system that can operate via satellites. If this could be achieved, it would enable absolutely secure global communication. So far the Los Alamos group has succeeded in transmitting a quantum key through air over a distance of 1 km.

Security experts are now wondering how long it will be before quantum cryptography becomes a practical technology. At the moment there is no advantage in having quantum cryptography, because the RSA cipher already gives us access to effectively unbreakable encryption. However, if quantum computers were to become a reality, then RSA and all other modern ciphers would be useless, and quantum cryptography would become a necessity. So the race is on. The really important question is whether quantum cryptography will arrive in time to save us from the threat of quantum computers, or whether there will be a privacy gap, a period between the development of quantum computers and the advent of quantum cryptography. So far, quantum cryptography is the more advanced technology. The Swiss experiment with optic fibers demonstrates that it would be feasible to build a system that permits secure communication between financial institutions within a single city. Indeed, it is currently possible to build a quantum cryptography link between the White House and the Pentagon. Perhaps there already is one.

Quantum cryptography would mark the end of the battle between codemakers and codebreakers, and the codemakers emerge victorious. Quantum cryptography is an unbreakable system of encryption. This may seem a rather exaggerated assertion, particularly in the light of previous similar claims. At different times over the last two thousand years, cryptographers have believed that the monoalphabetic cipher, the polyalphabetic cipher and machine ciphers such as Enigma were all unbreakable. In each of these cases the cryptographers were eventually proved wrong, because their claims were based merely on the fact that the complexity of the ciphers outstripped the ingenuity and technology of cryptanalysts at one point in history. With hindsight, we can see that the cryptanalysts would inevitably figure out a way of breaking each cipher, or developing technology that would break it for them.

However, the claim that quantum cryptography is secure is qualitatively different from all previous claims. Quantum cryptography is not just effectively unbreakable, it is absolutely unbreakable. Quantum theory, the most successful theory in the history of physics, means that it is impossible for Eve to intercept accurately the onetime pad key established between Alice and Bob. Eve cannot even attempt to intercept the onetime pad key without Alice and Bob being warned of her eavesdropping. Indeed, if a message protected by quantum cryptography were ever to be deciphered, it would mean that quantum theory is flawed, which would have devastating implications for physicists; they would be forced to reconsider their understanding of how the universe operates at the most fundamental level.

If quantum cryptography systems can be engineered to operate over long distances, the evolution of ciphers will stop. The quest for privacy will have come to an end. The technology will be available to guarantee secure communications for governments, the military, businesses and the public. The only question remaining would be whether or not governments would allow us to use the technology. How would governments regulate quantum cryptography, so as to enrich the Information Age, without protecting criminals?

The Cipher Challenge

The Cipher Challenge is a set of ten encrypted messages, which I placed at the end of
The Code Book
when it was first published in 1999. In addition to the intellectual reward of cracking all ten messages, there was a prize of $15,000 for the first person to solve the Challenge. The Challenge was eventually solved on October 7, 2000, after one year and one month of arduous effort by codebreakers, amateur and professional, around the world.

The Cipher Challenge remains as part of this book. There is no longer a prize associated with its solution, but I would encourage readers to decipher some of the messages. The ten stages were intended to grow in difficulty, although many codebreakers have felt that stage 3 is harder than stage 4. The ciphers used in the stages differ and progress through the ages, so the early ciphers are ancient and easy to break, whereas the latter stages employ modern ciphers and require a great deal more effort. In short, stages 1 to 4 are for the amateur, stages 5 to 8 are for the real enthusiast, and 9 and 10 are for those who are dedicated codebreakers.

If you want to know more about the Cipher Challenge, you can visit my own Web site (
www.simonsingh.com
), which offers a variety of information, including a link to a report written by the Cipher Challenge winners, Fredrik Almgren, Gunnar Andersson, Torbjorn Granlund, Lars Ivansson and Staffan Ulfberg. The report makes excellent reading, but please be aware that it, and other material on the Web site, does include spoilers that you might not want to see just yet.

The main aim of the Cipher Challenge was to excite people, to get them interested in cryptography and codebreaking. The fact that thousands of people took up the challenge is tremendously satisfying. Officially the Cipher Challenge is now over, but I hope that it will continue to generate some interest among new readers who want to test their codebreaking skills.

Good luck,
Simon Singh

Stage 1: Simple Monoalphabetic Substitution Cipher