Michael Rabin might be in for trouble. A Harvard professor of computer science, he is building a secret code machine, an Enigma for the 21st century. But this is better than Enigma. This time, there's no hope for anyone who might want to break the code's ciphers, even if they get hold of the key. Rabin's trick is to use an electronic version of vanishing ink. The people at the National Security Agency, the US government's temple of spies, aren't going to like it one bit. For this isn't some quantum code that can only run on a quantum computer-an as yet only dreamed of machine. It is something anyone, anywhere can use. And if Rabin's machine works as well as he believes it will, it could undermine the NSA's efforts to track terrorist activities. These days, maybe that's something a wise man should think twice about.
But the rewards are clear. For people whose concern is to maintain their own privacy, rather than invading someone else's, Rabin's scheme could be the ultimate cloak of secrecy.
It sidesteps a common flaw of other codes. All encryption schemes mix up your message into an unreadable mess using some kind of secret key known only by the sender and the receiver. In many schemes, the key is a string of random binary 0s and 1s that is added to the message to make it seem like gibberish. Then if an eavesdropper knows what the key is, they can subtract it to extract the message. If they don't, they can't.
Trouble is, if you use the same key for too long, eavesdroppers can analyse the coded messages and use statistical techniques to break the cipher. One remedy is to use the key only briefly then destroy it, and have a pad of many keys to be used only once-the "one-time pad". This makes it mathematically impossible for an eavesdropper, even someone with unlimited computing power, to work out the message.
That leaves you with the problem of how to keep the key out of enemy hands. The US president communicates with his Russian counterpart via a one-time pad system, using a network of trusted go-betweens to ferry the code books that contain the pads. But this is impractical for most people, and is always open to abuse from defecting agents.
A cunning way around this is public key cryptography. The kind that protects much of the world's e-commerce, for example, is called RSA, a scheme based on the difficulty of factorising large numbers. You broadcast a huge number, which is used as the key to encrypt the message. It can only be decrypted using a private key-the prime factors of that number, which only you know. Even though everyone knows the public key, they can't use it to eavesdrop without first breaking it into factors, and that's tremendously difficult.
Difficult, that is, using known mathematical techniques. What keeps e-commerce experts awake at night is the fear that someone might discover a new technique that does the job with ease. "Right now, it's perfectly possible that some smart kids down the street could figure out a way to break RSA," says Richard Lipton, a computer scientist at Georgia Institute of Technology in Atlanta.
In any case this is only a protection against unofficial snoopers. Governments could simply use the courts to make someone divulge their key, or to take a look at e-mail archives or old financial transactions. Civil liberties groups are already concerned at the measures that governments have rushed into law, with the avowed aim of tackle terrorism or organised crime, which could also be used to search and store our communications for future reference.
Rabin's scheme would change all that. Your secrets would be safe forever. And the strangest thing of all is that this acme of secrecy relies on data that anyone can tap into-the flood of digital information continuously being transmitted from TV broadcast satellites and mobile phone masts and a host of other sources. All of it is public. Given the right equipment anyone can pick up that raw digital signal and record it. And if you can pick it up, you can use it to create a key to an unbreakable code.
It works like this. The two conspirators, Alice and Bob, first have to establish a set of secret rules for picking random bits from the data. This is a potential weakness in the scheme-how do they share these rules securely? But it would only involve one meeting, say, rather than the repeated ferrying of one-time pads.
They might share a computer program that taps into the world's data stream, pulling out a certain bit from the Sky TV satellite at 12 noon precisely, a bit from the Microsoft home page half a second later, a bit from the Dow Jones index after that, and so on. The program assembles these bits into a key.
Whenever they want to communicate, Alice just tells Bob over the phone which key-say, the one their program made last Tuesday-she is using to encode the message. The eavesdropper, Eve, is sunk. Without Alice and Bob's program, she doesn't know which bits to look for. So it's a machine for generating an endless one-time pad, with no reliance on couriers.
And it's even better than that. Suppose Eve recorded the encrypted message, and then later somehow get hold of the program-by breaking into Bob's office, say. She still wouldn't be able to decode the message because the data stream that produced the key is long gone, lost in space. Lipton believes that this "everlasting security" will be a big draw. "That's a very interesting and compelling kind of cryptography that we don't currently have," he says.
It might be especially popular for corporations who want to conduct deals with each other away from prying eyes. "Everlasting security is very important here," Rabin says. The partners in a merger may want to ensure that the encrypted messages they exchanged about tactics and business strategies remain secret for a decade.
The only way to crack the code is if Eve can record the information on which Alice and Bob base their key. And she has to record almost all of it. In 1990, Ueli Maurer, a cryptography researcher at the Swiss Federal Institute of Technology in Zurich, worked out that an eavesdropper who can store up to 50 per cent of the whole data stream, and therefore snare about half of the key, can't break the code even with unlimited computing power at her disposal to make guesses about the rest of the key. Rabin has taken this further and shown that even 90 per cent isn't enough.
"This stuff is terrific," says Lipton. Even when the would-be code breaker has a computer endowed with science-fiction power, the system is secure. The only way to decode the message is to have the key in advance, or to have stored almost every 0 and 1 that's transmitted anywhere in the world.
The next question is what data to use for the key. Public data streams from satellite broadcasts, Internet activity and the like would be one option, but because they are so diverse-requiring many kinds of receiver, for example-they would be cumbersome to use. So Rabin is now working on a project to design a purpose-built system. He has teamed up with Harvard electrical engineer Woody Yang to build a beacon to transmit a stream of random bits from a satellite.
Eventually, Rabin hopes to establish a fleet of satellites that will broadcast packages of random bits at a rate that defeats anyone's storage capabilities. Instead of monitoring optical fibres, phone masts and Internet pages, users would be able to generate their keys to the vanishing code from a single source of data, making the system a worldwide resource. Rabin won't elaborate on any of the details. "It's a work in progress that I cannot discuss," he says.
Establishing this infrastructure is going to take some serious money. Rabin is aiming for 45,000 gigabits per second of random data, transmitted by a fleet of 48 low-orbit satellites. The reason for this extravagance is to drive up the costs of storing the data. Each bit will cost around 500 times more to store than transmit, Rabin believes, so a year's data from all the satellites would cost many billion dollars to store. Far too much for any corporation's espionage budget, and probably even for the NSA.
Rabin envisages a network of corporations sharing the setup cost for the advantage of being able to conduct their business securely. Smaller companies or even individuals would then be able to buy into the network once it has been built.
Not everyone is convinced that Rabin's scheme is a practical business proposition, as there are other cryptographic techniques that work well enough for everyone except the most paranoid. Maurer certainly never bothered to patent his contribution. "I didn't think this would ever be used," he says. But one thing is certain: if Rabin can turn his idea into a practical, unbreakable code machine-and he insists he can-the NSA won't be best pleased.
"What scares the NSA most is not simply unbreakable encryption, but unbreakable encryption that's easy to use," says Brad Templeton of the Electronic Frontier Foundation, a group that seeks to protect civil liberties in digital media. The NSA already enc
By Michael Brooks, New Scientist issue 5th January 2002