Is Encryption Doomed?

by Simson Garfinkel, September 1, 2004

But what if a fundamental breakthrough in mathematics rendered useless all of the fancy encryption that the world now depends upon?

For more than 30 years, mathematicians have sought in vain the answer to a simple problem in theoretical computer science. The problem is what's known as an open question--it's a simple equation that is either true or false. It can't be both.

The problem--independently formalized by the mathematicians Stephen Cook and Leonid Levin in 1971--remains one of the central unsolved questions of modern mathematics. It is a problem about other problems.

Cook and Levin asked whether there exist mathematical puzzles that are hard to solve, but that have solutions that are easy to verify. As the problem is commonly phrased, the mathematicians asked whether P is equal or not equal to NP.

P is the set of problems that are easy to solve. Strictly speaking, it is the set of problems that can be solved in "polynomial" time--that is, in an amount of time that is roughly proportional to the size of the problem's description. Most of these problems are so easy, in fact, that we hardly even consider them to be problems at all. For example, multiplying two numbers together is a P problem: the solution can be found in polynomial time. Another P problem is searching for a book that's lost in your house. Even if all of your books are packed away in boxes in your basement, it's still an "easy" problem to solve, at least by mathematical standards: just open up every box and look. It might take you days, but if you can do a thorough search, you will find the book.

NP problems, on the other hand, are hard problems. NP standards for "nondeterministic polynomial"--it's a formalism that describes a kind of computer that can't be built, but that can be mathematically modeled. An NP computer can simultaneously try every possible solution to a problem and recognize which one is correct.

It turns out that NP computers are really good at solving any kind of problem where the answer can be found only by searching. One of the best examples of these problems today is code breaking. Say the FBI raids a terrorist hideout and grabs a laptop with encrypted files on it. The only feasible way to decrypt the data today is to try every possible encrypt key, hoping that one will work. A small network of modern computers can try every possible 40-bit key in just a few weeks. But a technically advanced terrorist would be more likely to use 128-bit encryption. And cracking a single 128-bit key, even harnessing the power of every computer on the planet, could take thousands of billions of years. For all practical purposes, it's impossible to break such a code, because today's computers can only try one or a few keys at a time.

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."