Is Encryption Doomed?

Continued from page 1

An NP computer, if one existed, could try all of the possible keys at the same time, and recognize instantly which key was correct. Code breaking is an NP problem.

Factoring is another NP problem. Although there are various techniques for factoring large numbers, all of them involve searching through large numbers of, well, numbers. But an NP computer could simultaneously try to multiply every number with every other number and somehow pick out the pair of numbers that yielded as a product the number that the computer was told to factor. The difficulty of factoring large numbers is at the basis of the RSA encryption algorithm, which is built into practically every Web browser and is the basis of most e-commerce.

As described above, NP computers seem like magical things that could never exist today. But that might not be the case. It's easy to see that there exist many NP problems, including—code breaking and factoring. But nobody has ever been able to mathematically prove that it's impossible to solve all NP problems in polynomial time on an ordinary computer—in other words, that P is not equal to NP.

Many experts now believe, however, that it's just a matter of time before the question will be resolved.

One mathematician who was willing to back that belief with gold is Michael Sipser, who this month becomes the new head of the MIT Mathematics Department. Back when he was a graduate student at the University of California, Berkeley, Sipser went so far as to bet a fellow graduate student an ounce of gold that by the end of the twentieth century, P would be found to be not equal to NP.

Sipser lost, of course.

As it turns out, the graduate student that accepted Sipser's offer was Len Adelman—the "A" in RSA. "I thought then that the problem was just not ripe for any resolution," says Adelman, explaining why he accepted Sipser's wager.

After he made the bet, Sipser ended up becoming a professor of mathematics at MIT and taught MIT's course on the theory of computation. He enjoyed the course so much that he wrote an introductory textbook that has become one of the subject's bibles. And he has published extensively on the history of the P vs. NP question.

There is a lot riding on the answer to that question. That's because what Cook and Levin realized simultaneously back in 1971 is that there exists a large number of NP problems that can be thought of as "perfect" or "complete." Each of these so-called NP-complete problems encompasses everything that it means to be an NP problem. That means that if a solution for any NP-complete problem could be found that could be solved in polynomial time, then a short-cut solution could be found for every NP problem.

In practical terms, that would spell the end of encryption as we know it. The Internet would be vulnerable to hackers and computer viruses.

As the twentieth century neared its conclusion, it became clear to Sipser that nobody was going to find a solution anytime soon. This left the matter of the bet."There was a little bit of a controversy as to when the entry of the century was," he recalls. "Was it January 1, 2000, or January 1, 2001? I decided not to quibble because it didn't look like [a solution] was imminent. So somewhere early in 2000, I bought an American Gold Eagle—I spent an extra $10 to make it a Year 2000 Gold Eagle—and I sent it to him."

Adelman had long since left his professorship at MIT and taken up residence at the University of Southern California, where he works on cryptography and DNA-based computers. Reached by e-mail, Adelman confirmed that he received the gold coin.

Today, however, there is a lot more than an ounce of gold riding on the question. Shortly after Sipser sent Adelman the coin, the Clay Mathematics Institute of Cambridge, MA, named the P and NP question as one of the Institute's seven "Millennium Problems." The institute set aside $7 million, with a $1 million prize offered to the person (or machine) that can solve each problem.

Adelman thinks that we'll be waiting for the solution for a long time. Resolving the question of P and NP, he says, "would require new and brilliant ideas and not routine incremental progress. From my perspective, we are no nearer to solving the problem now that we were when bell-bottom pants were cool."