Code conquers computer snoops

With electronic privacy becoming more difficult to attain for everyone from governments to lovers, the need for an unbreakable code is rising rapidly toward the top of many “most wanted” lists. Michael Rabin, the Thomas J. Watson Sr. Professor of Computer Science at Harvard University, says he has come up with the solution: a code that cannot be deciphered even by those who have both the key and unlimited computer power.

“The ingenuity of man cannot invent a code that the ingenuity of man cannot break,” wrote storyteller Edgar Allan Poe, who was also an amateur cryptographer. But this is no longer true, according to Rabin. “All existing codes cannot be proven to be unbreakable, but for the first time we have a mathematical proof that an encryption method is [unbreakable],” he claims. “It provides everlasting security.”

Needless to say, the U.S. government is interested. One version of the coding method, developed by Rabin, Ph.D. student Yan Zong Ding, and former Harvard postdoc Yonathan Aumann, will be published soon in a special issue of the IEEE (International Electronics and Electrical Engineering) Transactions on Information Theory. “I’ve had requests for copies of the paper from government offices,” Rabin admits. The National Science Foundation funded his research, so the results are available to the U.S. government without cost.

“Some wealthy individual investors and a large venture fund have also been in touch,” Rabin continues. “But the financial aspect of this innovation takes second seat to the science.” That’s all he will say about his future plans for this system.

Rabin has his critics. Most of them question, not the mathematics, but the practicality of his system. One major way to use the method requires a satellite system which Rabin estimates will cost “a few tens of millions of dollars a year” to operate. “That’s expensive,” he admits, “but the whole world can use it, so the cost could be shared.”

For that money, government, military, financial, industrial, and other people who want to send secret messages get “to sleep soundly,” Rabin says. “No one, now or later, could decode their messages.”

Secret raisins in a public pudding

The backbone of the code consists of a device that generates a stream of random bits of information at a prodigious rate. Anyone can receive this information, but the transmission rate is so high that storing all of it is technically unfeasible. Even if it becomes feasible, the cost of storing the random bits in the hope of cracking the code later would be prohibitive.

“It would cost billions of dollars a year to store all the bits generated,” Rabin maintains, “while producing and broadcasting the bits would be a hundred to a thousand times cheaper. Encryption will always have the upper hand on decryption.”

The coded message would be enfolded in random bits picked out of the stream by the sender and receiver, like raisins plucked out of a pudding. Cryptographers usually refer to the sender-receiver pair as Alice and Bob. When Alice is the sender, she uses a secret key to select a relatively small number of bits from the huge, furiously flowing public stream. She might choose 100,000 out of trillions of bits. She then folds a message into these selected bits – the raisins in the pudding.

Bob uses the same secret key to pluck out the same raisins, then uses the selected bits to decode the message.

Sounds simple enough to do, but also simple enough to crack. All an eavesdropper, called Eve by decoders, needs to do is capture the same bits used by Alice and Bob.

That’s not possible, Rabin claims, because the bit stream goes by so fast, Eve cannot pick out the same bits Alice and Bob used because she doesn’t have the secret key at the time of transmission. And Eve can’t store all the bits then search them later for the key. She is overwhelmed by quantity.

Alice and Bob know what to pick out of the stream; Eve does not. Exactly how Alice and Bob know is, of course, the secret of the system. It is the raisin in the technology pudding that Rabin has cooked. That technology probably will involve patents, although he is not ready to talk about that yet.

Reusable keys

To date, Rabin has only explained his coding method in lectures. The written explanation is still to be published in the IEEE Transactions on Information Theory. A more recent paper, not yet published, explains how the secret code key can be used over and over again without compromising security.

If Eve managed to torture or bribe a code clerk to reveal the key, messages already sent still could not be deciphered. Neither could future messages, because Alice and Bob could simply select a different secret key.Several critics have claimed that Rabin’s “everlasting security” is impractical because it is too difficult to send long messages. The longer the message, the longer the key that’s required. Eventually, the key becomes unmanageable.

Not so, counters Rabin. You can use 1,000-byte (8,000-bit) keys to send arbitrarily long messages to 10,000 different people. Such keys would require only 10 million bytes, something you could handle on a laptop computer with 20 gigabytes (20 billion bytes) of memory.

Summing up his invention, Rabin calls it “the first efficient and provably secure coding system ever developed. It stays secure for past messages, even if the secret key becomes known because the bit stream is too large to be stored. Finally, the key can be reused again and again.”

Asked if he has given his system a practical tryout by, say, using an available satellite, Rabin answers: “There is no need to try it once you have a mathematical proof of the impossibility of breaking the code. We have that proof; so we have begun implementing the system.”