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