The End of Encryption?

An anonymous reader writes "The encryption algorithms that make virtually all electronic commerce possible work only because certain mathematical problems are very, very hard to solve. But some mathematicians are trying to prove that there's really no difference between 'hard' and 'not hard' problems--known in the math biz as P and NP. In an article on TechnologyReview.com, Simson Garfinkel spells out the real-world consequences of this mathematical conundrum."

Comments

Nope, wrong, invalid.. nothing to see here.

[Ckwop]

No no no no no. How many more times? Cryptography has absolutely nothing to do with the question of P?=NP.

P?=NP refers to the asymptotic complexity as the problem. i.e. as the input size goes to infinity. It quite possible to have a problem whos complexity is approximately linear at the 100-1000-bit range and still NP-Complete. Conversely, it's possible to have a p-time algorithm for solving a problem that has a O(n^100) so it's still difficult to solve. While resolving P?=NP might bring new tricks to the table it's difficult to legislate for these tricks. There might not even be any we don't already know.

Another point, p?=np has no bearing on the security proof of the one-time pad or quantum mechanical key exchange. The latter will become practical over large distances to enable the former long before p?np is resolved. Cryptography will die when the last human draws its breath.

Simon.

Re:Nope, wrong, invalid.. nothing to see here.

[Geiger581]

What you say is very true, but there are two big exceptions to note:
1) 1TP/QKE require as much storage/bandwidth for the key as for the message, and the key can never be resused. These are both severe drawbacks.
2) Crypto is useful for more than just hiding information. Digital signatures/integrity hashes are both very important and impossible to achieve -reuseably- with either of the schemes mentioned above.

More than Just P=NP

[SparafucileMan]

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

Which is not exactly true. It could be true but not provable. It could be false but not provable. It could be provably true, or provably false. Or, it could be neither true nor false.

It's still a "what if" piece...

[bersl2]

So far as we know, P != NP.

And that's it. And I haven't seen a shred of evidence to the contrary.

Yes, the article is somewhat truthful, in that if P == NP, the world will have been turned on its head, but the same thing is true about thousands of scientific and/or mathematical assertions, each of which is more likely to be overturned than P != NP.

Re:Could be argued

[Christopher Thomas]

It can well be argued that absolutely nothing is in fact random. From coin flips to roulette anything can eventually be learned and predicted on some level.

Even in a purely classical universe, sensitivity to starting conditions makes things like coin tosses and die rolls impossible to predict if set up carefully. This is that whole "chaos" topic you may have heard about in the press in the 1980s. You'd have to have excruciatingly accurate knowledge of the state of everything in the past light-cone of the event you're trying to predict, as of the time of prediction, for it to work with perfect reliability.

In our quantum universe, the uncertainty principle makes it impossible even in principle to measure starting state to the required precision, for the schemes that are used for true random number generation in electronic systems. Additionally, if quantum processes are accepted as truly random, they inject enough noise to taint macroscopic events with true randomness if the consequences of the noise are given enough time to propagate.

In summary, true randomness exists as a very fundamental result of the laws of nature, and won't go away no matter how good our measurements get.