Wed Aug 11 19:31:15 BST 2010 by Markus Kuhn
Contrary to what you can read in some recent media coverage, the P ≠ NP question is largely irrelevant to practical cryptography.
A P ≠ NP proof will not give us any assurance about the security of any commonly used ciphers. While there have historically been a few attempts to build ciphers based on NP complete problems, these have not survived the test of time.
The problem is the following. While we are very unlikely to ever find a polynomial algorithm for an "NP complete" problem (i.e. be able to show that P = NP), there exist for a lot of "NP complete" problems very efficient algorithms that do an excellent job most of the time. Not being able to find an algorithm that is guaranteed to find a solution in polynomial time every time does not mean that it is impossible to find a solution most of the time. In cryptography, however, you need problems with a very different property: namely it must be extremely unlikely that any possible algorithm will ever find even a single solution efficiently. A cipher that can be broken in a substantial fraction of cases is just no good.
Thu Aug 12 09:54:27 BST 2010 by Eric Kvaalen
Very good point. But of course, showing that P=NP would be bad news for cryptography.
Another reason that P ≠ NP is not important to cryptography is that it doesn't necessarily mean that factoring is not in P, since it's not NP-complete. It may be that there's an algorithm for factoring that always works in polynomial time.
All comments should respect the New Scientist House Rules. If you think a particular comment breaks these rules then please use the "Report" link in that comment to report it to us.
If you are having a technical problem posting a comment, please contact technical support.