Quantum Cryptography

Toby Howard

This article first appeared in Personal Computer World, April 1997.

WITH THE RECENT EXPLOSION of commerce on the Internet, being able to guarantee the privacy of data has become a crucial issue. Today, none of the encryption methods currently in use on the Internet are provably watertight. They're good, and certainly extremely hard to break, but they are not unbreakable. A new technology, however, promises true security, offering codes which are impossible to crack, no matter how much computing power and ingenuity is used against them. These are codes whose unbreakability stems not from clever mathematical techniques, but from the unbending laws of physics.

When it comes to security, the Internet has more holes in it than swiss cheese. In a study conducted at the end of 1996, computer security researcher Dan Farmer found that of 2,200 Web sites he surveyed, almost a third had security weaknesses leaving them vulnerable to attack. Farmer is the author of the controversial SATAN program, which probes Unix machines on the Internet and checks them for known security lapses. Not everyone likes the idea of SATAN. Although originally designed for systems administrators to find unwanted open doors on their machines and rapidly close them, SATAN is also freely available for use by malicious hackers.

It's not only Web sites that are at risk. Email is remarkably easy to intercept, either by "sniffer" programs which monitor the Internet data passing through a system, or by unauthorised access to unencrypted email in in-box files. Rumour has it that GCHQ regularly monitors email traffic in the UK, and that in the USA the giant supercomputers of the National Security Agency scan email for hints of terrorist or anti-government activity. Those in a position to say whether this is really going on, are not telling.

Phil Zimmermann's Pretty Good Privacy (PGP) program is perhaps the best known of the more secure coding systems available on the Internet. PGP uses the RSA public-key system, which is also the basis for the secure transactions offered by Netscape Navigator and Microsoft Internet Explorer. Although public-key systems are extremely hard to break -- so don't worry, your credit card is quite safe -- they have not been mathematically proven to be unbreakable. For some applications, this isn't good enough.

There is only one kind of code which is 100% secure. This is the so-called "one-time" system. The message is encrypted mathematically using a numerical key -- a long random non-repeating sequence of digits. The recipient of the message can decipher it using the same key. Because a different, randomly selected, key is used for every message, the encrypted message cannot possibly contain any inadvertent clues to help a codebreaker crack it. It's the perfect code, used by spies for decades.

But there's a catch. Before the message itself can be transmitted, both the sender and the recipient need to know the key. How can the key be transmitted? By using a secure code, which needs a key . . . Catch 22.

Spies have traditionally solved the key distribution problem using little paper pads. Each numbered page lists a series of random digits, used as the key for a message. To send the secret message, Spy A chooses a page from his pad, encodes his message with the key, appends the page number, then sends his message to Spy B. Spy B receives the message, looks up the key page in his copy of the pad, and decodes the message. This is utterly secure, providing of course the enemy doesn't get his hands on a copy of the pad.

For computer networks, the first demonstrable solution to the key distribution problem uses a technique called quantum cryptography. It provides a method not only to send data securely, but also to monitor whether anyone has been eavesdropping on the communications channel.

With apologies to any physicists who might be reading, it works something like this. Light comes in packets of energy called photons, each of which has a wobble called its polarization. There are two kinds of polarisation: up/down and left/right. You can build a machine to read a photon's polarization, but it must be configured to read either up/down or left/right polarizations. It can't read both kinds at once. A machine set to read up/down photons will only give a meaningful result (up or down) if the photon it is reading is the up/down kind. If it's a left/right photon, the machine will give a random, and therefore meaningless, result.

Suppose Alice wishes to send a key secretly to Bob. First, Alice and Bob have to agree how to use the polarizations of photons to represent bits. Let's suppose they agree on "up" = 0, "down" = 1, "left" = 0, and "right" = 1.

Then, Alice creates a stream of photons, each with a polarization chosen at random. She records the polarization of each. The diagram shows the situation where Alice has prepared 8 photons, labelled (a) to (h). She then sends the photons, in order, to Bob. When Bob receives each photon, he randomly configures his detector ready to read either up/down or left/right photons. He notes the configuration, makes the reading, and records the result. Here's an example session:

In this example, Bob happened to choose a left/right configuration for his detector to read photon (a), so he got a random result (a 1 in this case). For photon (b), however, he happened to choose left-right, which matched the type of photon, and so correctly read the polarization of the photon, a 1. For photon (c), again the detector didn't match the photon, and so the reading was random, a 0.

When Bob has read all the photons, he then tells Alice the configuration he used to read each of the photons. He can tell her this publically, but he must keep the readings themselves secret. Alice then tells Bob which of those configurations matched the polarizations of the photons she sent him. In our example, these are (b), (d), (f) and (g). The values Bob obtained from each of the matching configurations, taken in order, spell out the secret key: 1001. All the other readings are discarded.

If during the exchange of photons, Eve (an eavesdropper) listens in on Alice and Bob's communications, the laws of quantum mechanics dictate that her attempts to read the photons in transit will actually change their polarizations. So Bob will receive photons in a different state from those sent by Alice. Alice and Bob will notice this, and will know they've been eavesdropped. They can try again. Once the key has been securely exchanged, Alice and Bob can send their message, encrypted using a one-time method.

This simple example shows the principle. In practice it is more complex, for two reasons: first, Alice and Bob will need to establish a key thousands of bits long; second, according to the one-time principles, their key is only good for encoding one message. They must repeat the entire procedure for every message they wish to send!

This all sounds like science fiction, but it has recently been demonstrated in experiments by Paul Townsend, a researcher at BT's laboratories in Ipswich. Independently, Richard Hughes of the Los Alamos National Laboratory in California has securely exchanged keys over a 14km optical fibre link. There are problems to do with noise, but the method really works. Hughes predicts the technology will be commercially available by 2000.

We reported in September 1996's Cutting Edge that computers which work on quantum mechanical principles, if they are ever built, may bring about the downfall of public-key cryptography. Perhaps quantum cryptography will take its place. The codebreakers are not going to like it.

Toby Howard teaches at the University of Manchester.