Is Encryption Doomed?

Our entire information society rests on a fragile foundation that mathematicians are racing to dismantle.

It's not often that results from conferences on mathematics make the news, but that's precisely what happened last month at the annual Crypto conference in Santa Barbara, CA when researchers from France, Israel, and China all showed that they had discovered flaws in a widely used algorithm called MD5—an algorithm that I wrote about in some detail last month. The "when life gives you lemons, make lemonade" message that came out of the conference was that this process of breaking codes and developing even stronger ones is all part of the cryptographer’s game.

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.

Story continues below

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.