By GINA KOLATA
http://www.nytimes.com/2001/02/20/science/20CODE.html?pagewanted=all
A computer science professor at Harvard says he has found a way to send coded messages
that cannot be deciphered, even by an all-powerful adversary with unlimited computing
power. And, he says, he can prove it.
If he is right, and he does have some supporters, his code may be the first that is
both practical and provably secure. While there are commercially available coding
systems that seem very hard to break, no one can prove that they cannot be cracked,
mathematicians say.
In essence, the researcher, Dr. Michael Rabin and his Ph.D. student Yan Zong Bing,
have discovered a way to make a code based on a key that vanishes even as it is used.
While they are not the first to have thought of such an idea, Dr. Rabin says that
never before has anyone been able to make it both workable and to prove mathematically
that the code cannot be broken.
"This is the first provably unbreakable code that is really efficient," Dr. Rabin
said. "We have proved that the adversary is helpless."
Dr. Richard Lipton, a computer science professor at Princeton, who is visiting this
year at the Georgia Institute of Technology, said, "It's like in the old `Mission
Impossible,' where the message blows up and disappears."
Someone who uses one of today's commercially available coding systems, Dr. Lipton
explained, uses the same key � mathematical formulas for encoding and decoding � over
and over. Eventually, they may be forced, perhaps by a court order, to give up the
key. Or the key may be stolen. But with Dr. Rabin's system, the message stays secret
forever because the code uses a stream of random numbers that are plugged into the key
for encoding and decoding. The numbers are never stored in a computer's memory, so
they essentially vanish as the message is being encrypted and decrypted.
"If someone walks into my office with a court order or if they put a gun to my head
they still could not read my conversations," Dr. Lipton said.
In a sense, say some mathematicians and computer scientists, Dr. Rabin may have solved
the ultimate problem in cryptography, one that has driven research for centuries:
finding a provably unbreakable code that is also practical. But, they say, the paradox
is that the discovery has come at a time of vigorous debate over whether such a code
will make much difference in keeping communications private.
Some say that a provably unbreakable code could have profound effects, keeping secret
messages secret forever. But others say that codes today are already so good that
there is little to be gained by making them provably, rather than just probably,
unbreakable.
For now, Dr. Rabin's idea is simply a scheme backed up by a mathematical proof that he
has been presenting to scientists at seminars. No company is lurking in the background
to sell it, and Dr. Rabin says he has no commercial interests in it.
"I never commercialize anything," Dr. Rabin said. "I am not in that business."
Instead, he said, he did the work because it was a challenge.
Dr. Rabin's idea is simplicity itself, at least in the world of encryption. Previous
coding methods rely for their security on the limitations of computing power. They
assume that if breaking a code requires enough calculations, even the best computers
will not be able to do it.
But, Dr. Rabin said, there is no proof that such codes are secure. Their security
hinges on the belief that no one will find a shortcut to doing the calculations. It is
always possible that such a shortcut exists, waiting to be discovered by a clever
mathematician.
Dr. Rabin relies instead on the limits of memory banks in computers. No matter how
powerful a computer is, no computer can store an unlimited amount of data. And yet
that is what is required for an eavesdropper to break his code.
The coding starts with a continuously generated string of random numbers, say from a
satellite put up to broadcast them or from some other source. The numbers can be
coming by at an enormous speed � 10 million million per second, for example.
The sender of a message and its recipient agree to start plucking a sequence of
numbers from that string. They may agree, for example, to send a message, encoded with
any of today's publicly available encryption systems saying "start" and giving
instructions on capturing certain of the random numbers. As they capture the numbers,
the sender uses them to encode a message, and the recipient uses the numbers to decode
it.
An eavesdropper can know the mathematical formula used to encode and decode, but
without knowing the exact sequence of random numbers that were used in the formula to
send a particular message, the eavesdropper cannot decode the message. And the only
way to have that sequence is to just happen to be storing numbers from the unending
stream at exactly the right moment.
If the eavesdropper, for example, had a secret way to decode the message saying
"start" and it took a minute to do the calculation needed to decode it, it would be
too late by the time the eavesdropper got going. The sender and recipient would
already have their string of numbers and that string of numbers, once broadcast, could
never be retrieved. It would be infeasible to store the endless string of numbers in
any computer and so they are essentially gone forever.
Often, Dr. Rabin said, eavesdroppers will capture and store encoded messages hoping to
decode them at later, either when computers have improved � making it easier to do the
calculations to break a code � or when the method for encoding and decoding is known,
perhaps because it has been stolen. But, he said, messages encoded with his system can
never be broken by these means because the random numbers used in encoding and
decoding are used once and are never stored.
"That is why I call it `everlasting security,' " he said.
Dr. Richard DeMillo, chief technology officer at Hewlett-Packard, said that what
interested him about the scheme was that it "reshuffles the policy deck."
"Normally," he explained, "agencies put the burden of wiretapping on the carrier." A
telephone company, for example, would have to allow an agency like the Federal Bureau
of Investigation to listen in on coded material. But with this system, the agency
would still have the burden of trying to capture the appropriate stream of random
numbers, a task that would be technologically infeasible.
Dr. Lipton also said the scheme could thwart law enforcement agencies.
"If I'm saying to you, `Buy 1,000 shares of I.B.M., I'm sure it's going to go up,' "
he said, "and if that was an insider trading situation, five years from now the F.B.I.
could go after you."
If the agency had the encrypted message in hand, it could demand the key to read it,
he said. But, Dr. Lipton said, if the random numbers used to encode were used once and
never stored, the agency would be hamstrung. "It changes the ground rules," he said.
Dr. Lipton added that, as a computer scientist, he appreciated the proof that the code
could not be broken. "Michael's big contribution has been the proof that the system
actually works," he said. "It's one of those things that sounds obvious but the
mathematics is quite hard."
Of course, what is good for those who want privacy may not be good for law
enforcement. Even the cryptography systems sold today are a problem for the F.B.I.
"Uncrackable encryption allows drug lords, terrorists and even violent gangs to
communicate about their criminal intentions without fear of outside intrusion," the
F.B.I. director, Louis J. Freeh, told the Senate in 1998, according to a transcript
from the Federal Document Clearing House. "This type of encryption also allows these
same people to maintain electronically stored evidence of their crimes beyond the
reach of law enforcement."
Still, some computer experts said that while it might be interesting in theory to have
a provably unbreakable code, the practical importance of Dr. Rabin's code may be
minimal.
Some, like Dr. Dorothy Denning, a computer science professor at Georgetown, and Dr.
Cipher Deavours, a professor of computer science and mathematics at Kean University in
Union, N.J., said the code was simply impractical for large messages. The larger the
message, the longer the string of random numbers needed to encode it, and the more
difficult it would be to send.
"It's a cute idea, but it's simply unmanageable," Dr. Deavours said.
Others, like Dr. Lipton, disagreed. "I think it is quite practical," he said. And Dr.
Rabin insisted that computers would have no problem with the encryption scheme, even
with long messages that were sent among a large group of people.
Beyond the question of whether the system would work in practice, some question it
because, they say, the role of cryptography in protecting privacy has been overblown.
"If you think cryptography is the answer to your problem, then you don't know what
your problem is," said Dr. Peter G. Neumann, a computer scientist at SRI International
in Menlo Park, Calif.
Dr. Neumann explained that there are always ways to get around cryptography barriers
and that these methods have nothing to do with breaking codes.
"It's like the voting machines," he said. "You'd like to have some integrity in the
electoral process and now folks are coming out of the woodwork saying, `We have this
perfect algorithm for privacy and security.' "
But, he said, while the systems may use cryptography to make sure that when someone
touches a screen to vote, that vote is transmitted with perfect security, who's to
ensure the integrity of the person who programs the computer?
"There is no guarantee that your vote actually goes into the computer the way it looks
on the touch screen," Dr. Neumann said. "What does it take to buy a computer
programmer? A couple of years' salary and a house in the Cayman Islands?"
Bruce Schneier, who is founder and chief technical officer for Counterpane Internet
Security in San Jose, said that, as a scientist, he liked the idea of a provably
secure system. "Research like this should be encouraged," he said. "But research is
different from engineering."
But in the real world, a burglar confronted by an impenetrable lock on the front door
may well go round to the back and just smash a window. "I'm a cryptographer by trade,"
Mr. Schneier said. "And a provably secure cryptosystem doesn't do me any good. We're
putting a stake in the ground and hoping the enemy runs into it and now we're arguing
about whether it should be one mile tall or two miles tall. It doesn't matter. The
enemy will walk around it," he added.
Dr. Robert Morris, a retired cryptographer who was chief scientist for the National
Security Agency, the nation's code-making and code- breaking agency, also questioned
the primacy of cryptography.
"As far as I can see, he seems to be correct � it's a provably secure method," Dr.
Morris said. "But does that mean no one can read it? Nah."
He explained: "You can still get the message, but maybe not by cryptanalysis. If
you're in this business, you go after a reasonably cheap, reliable method. It may be
one of the three B's: burglary, bribery or blackmail. Those are right up there along
with cryptanalysis in their importance."
Dr. Rabin said that just because there are other weaknesses in communications systems,
that did not mean that secure encryption was not important.
It is as though medical researchers started arguing that there is no need to find a
cure for AIDS, Dr. Rabin said. After all, many more people die of heart disease, and
if you cure people of AIDS, heart disease can still strike them.
"This is not a reason not to work on H.I.V.," Dr. Rabin said. "The problem of H.I.V.
is still important."
Dr. Morris said that even though the actual breaking of codes might not be necessary
to read encrypted messages, Dr. Rabin's method could have an effect. "In a sense, what
it does is shift the emphasis from cryptanalysis to some other sort of attack," he
said.
