Shostack + Friends Blog Archive

P != NP and Security

There’s been a lot of discussion about the paper written by mathematician Vinay Deolalikar on this interesting problem.

The P!=NP problem is so interesting that there’s a million-dollar prize for solving it. It might even be interesting because there’s a million-dollar prize for solving it. It might also have some applicability to computer science and even cryptography. The August 11 edition of Deolalikar’s paper can be found here.

Because this is an interesting problem, there’s a lot of pressure on domain experts and pseudo-experts to comment. I classify myself as more pseudo-expert than expert, so color your filters accordingly.

Among the real experts, my favorite is Scott Aaronson, who is an expert in complexity theory and quantum information science. If you aren’t completely clear on the whole thing, his essay, “P vs. NP for Dummies” is a good place to start.

His essay, “Putting my money where my mouth isn’t,” is a marvelous snap response. In it, he says that he’s willing to contribute his on $200,000 to the million-dollar prize, should this proof be right. He gives some great reasons for his own snap commentary and his own decision not to cancel his vacation to look at the paper.

Aaronson also points to his own essay from 2008, “Ten Signs a Claimed Mathematical Breakthrough is Wrong,” which you should be reading before you read anything about Deolalikar’s paper. It’s not about Deolalikar, it’s about the general issue of breakthrough papers of any sort.

But getting back to this particular paper, there’s a lot of skepticism, and a good summary of the skepticism comes from Terence Tao.

I’ll add in my own raised eyebrow along with my own general discussion of P!=NP. I have three points:

1. P!=NP really isn’t interesting.
2. Most comments about the whole P vs. NP don’t understand the ramifications of it, especially when dealing with practical disciplines like computer science and cryptography.
3. The reason I have a raised eyebrow centers around those two above.

So here we go.

P!=NP really isn’t interesting. What would be interesting would be if someone proved that P=NP. We all expect that P!=NP, we act as if it’s true. On the one hand, that means I’m far more likely to believe Deolalikar because he’s proving that which we expect to be true. On the other hand, that means it’s harder evaluate his proof because it is proving something we all think is true.

Understanding P vs. NP. Conventional wisdom about P and NP often includes thoughts such as, “The implications of this [P=NP] on applications such as cryptography, and on the general philosophical question of whether human creativity can be automated, would be profound.” I disagree. I think that if it turns out to the shock of everyone that P=NP, it will be a yawn.

Let’s suppose that P=NP, which means that a large class of problems have solutions in polynomial time. Great. That doesn’t mean they’re easy to solve. It doesn’t mean that the solutions are even useful.

Here’s an example. A few years ago, we got a polynomial time primality test algorithm, the AKS test (named for its authors, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena). Originally, it was an x¹² algorithm, and everyone needing primality testing ignored it, because that’s too slow. It’s been improved to x⁶, which is still too slow. It’s polynomial, but that doesn’t matter.

In practical terms for cryptography, let’s suppose you want to generate a 2048-bit RSA key. For that, you need two 1024-bit primes. Right now, the tests that we use are “probabilistic.” I put quotes around it because while there’s no guarantee that the number that passes the probabilistic test is actually prime, no one has ever (knowingly) found a number that passed the probabilistic test and was not actually prime. In fact, if you found such a number, it would be a result worthy of publication. Thus, the risk of the inexact test is very low. But the cost of the exact test is 1024⁶ which is a very large number, 1,152,921,504,606,846,976, and we can’t really afford that.

Thus, for this function that’s useful for crypto, primality testing, we know that there is a P solution, x⁶ is too large a P. The fact that it is P turns out to be uninteresting.

For the purposes of cryptography, even x³ is probably not good enough. Some time ago, I harumphed about quantum computers doing factoring, and much of my harumphing boils down this observation — that even a low power polynomial like a cubic may leave the advantage to the code-maker over the code-breaker.

This is why I think that if P=NP, it could still be a yawn. If you find a polynomial solution with an exponent of somewhere in the 3-10 range, they are so hard so fast that the fact that the solution is polynomial is a merely a factoid. It seems a good bet that if there were a quadratic-scale algorithm for factoring, we’d know it.

This is a subtle point, so I’ll make it one more time. If P=NP, it’s only interesting if the polynomial is of low order. Polynomial-time problems can easily be intractable.

If it turns out that a bunch of cryptographic problems are polynomial, but order x⁶ or more, then the cryptographers aren’t going to lose a lot of sleep. In fact, they’ll have a good reason to get everyone to upgrade all their software, and that will be pretty much the end of it.

On the flip side of this, most NP-complete problems we know about are not as hard as we’re led to believe. The most famous NP-complete is the Traveling Salesman Problem. While it is indeed very hard to come up with the shortest solution for arbitrary problems, it’s actually very easy to come up with acceptable solutions for reasonable problems. Heck, it’s not like actual traveling salesmen have lots of problems covering their routes. There is even a nice web page that computes routes on Google Maps. I think a good way to put this in perspective with the P vs. NP problem is to note that there is a prize for solving a 100,000 city problem, and that prize is $100.

Most of the genuine hard problems we have are only hard to solve on edge conditions. There are many attempts to create cryptosystems out of real NP-complete problems, and their track record is pitiful. We really don’t have any of them. I say “really” because we have one — lattice cryptography — and it still has issues. It’s slow, big, and complicated with intellectual property. Worse, some forms of lattice cryptography have had problems similar to the Traveling Salesman Problem. The GGH cryptosystem has the flaw that all ciphertexts leak information about the plaintext. Oops.

The bottom line here is that many problems that we know to be hard are easy in most cases and that “easy” problems might still be hard enough that they’re useful for protecting secrets. Whether P=NP or P!=NP is something that is interesting to mathematicians and philosophers far more than to scientists and engineers.

Raised eyebrow department. Now I get to why I’m so far skeptical. The quote that I gave above about what it would mean if P=NP comes from Deolalikar’s paper. Perhaps naïvely, I expect an expert on complexity theory to go beyond the usual science-reporting ooo-ahhs. I expect a complexity theorist to understand that complexity is complex, or at least subtle. I’m not a complexity theorist, I’m a mere complexity practitioner and I understand that complexity is hard to understand.

However, he’s right. If P=NP, it would be a deep discovery and have philosophical import. However, however, he’s proved the opposite, and so discussion about what it would mean if his proof were out of phase with what it actually proves seems weird.

Fine, fine. Everyone’s entitled to their soapbox, particularly when they do something significant. But reading through the proof there’s something missing. In brief, his proof has to prove that something that everyone thinks is hard is in fact actually hard. Ironically, this is harder than proving that it’s actually easy (which is again the proof of the opposite thing). Part of proving that something is hard ought to include showing that a related problem is easy.

In the P vs. NP world he’s chosen, he is showing that 3SAT is hard. 3SAT, to oversimplify, looks at the combinations of three boolean operations, such as A or B and C. 2SAT (combinations of two boolean operations) is known not to be hard. Had Deolalikar shown that 3SAT is hard and 2SAT is easy, I think we’d all be wowed. With only half of that, we’re left hanging and scratching our heads. Since we expect 3SAT to be hard, there needs to be some contrast against a related known easy problem for contrast. Without that contrast, it’s very hard to value the proof.

Worse, if one were to take his proof mechanism and apply it to 2SAT and come up with a conclusion that 2SAT is also hard, then there’s a huge hole in the proof. If I were analyzing the proof, I would in fact start by seeing how it applies to a few known-P problems. If it proves they are NP, we have a problem.

To sum up, I bet the proof doesn’t hold up because it only addresses the wheat, not the chaff. Any prover of P!=NP has to deal with the problem that we expect that to be true and that it’s hard to prove that something we think is hard actually is hard. Disproving it is easier in the sense that if you come up with an easy solution to something everyone thinks is hard, it is — um, well — hard to argue with that. Without some contrast, any proof of P!=NP looks on its surface as if you’re saying, “Hey everyone, you know that problem no one can easily solve? I can’t easily solve it, either!” That lacks intellectual force.

Nonetheless, maybe he has it. Maybe in a few months we’ll all be wowed, once it sinks in. Heck, maybe he doesn’t have it this summer, but next summer a revised proof will have us all cheering. Only time will tell. But right now, it’s interesting but unconvincing.

My personal bet, which I have no proof for, is that P!=NP is true but unprovable. I’m holding out for the proof that it’s unprovable.

Originally published by mordaxus on 17 Aug 2010
Last modified on 17 Aug 2010
Categories:   history   Uncategorized