Slashdot Mirror
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."
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.
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.
OTP will always remain a viable means of private key cryptography. When you interleave signal with noise, the result will always have the properties of noise.
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.
Ask Slashdot dealt with this issue three years ago! When it comes to uninformed, idle speculation, this site is way ahead of MIT!
What I'm listening to now on Pandora...
The whole thing is a bunch of alarmist speculation.
"The market alone cannot provide sufficient constraints on corporation's penchant to cause harm." -- Joel Bakan
Bruce
Bruce Perens.
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.
I'm surprised that Simson made this elementary mistake.
Factoring has *not* been proved to belong to either P or NP. It's an "open problem".
DNA is a Turing machine. You, however, being dynamic and emergent, are not.
Digital Fortress was a complete piece of shit. Please don't base anything off that rag. It was written with the express purpose of capitalizing off of Dan Brown's momentum being made into a movie. The "visuals" described fit Hollywood nicely -- meaning they have no basis in reality.
It is easy for a person to come up with an algorithm that THEY can't crack. Most are painfully obvious to outsiders with any experience.
Other than proper implementation of a one-time pad, you'll probably find any encryption will eventually fall.
Learning HOW to think is more important than learning WHAT to think.
Randomness is not a human construct, I am not sure where you are getting this idea from. There are certain events that are PROVABLY unpredictable, e.g. radioactive decay and certain quantum effects.
Wrong. Sorry. Physics cannot prove things. They can only show that things are very likely and they can have theories that predict things. Often this works, but from time to time it fails. All physical deductions relating to reality are derived from experiments. Experiments are allways imprecise and frequently deliver wrong results.
Ask any physicist. They know that they just have a best guess, but no hard facts.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
By "prove" we mean to some disgusting (like 20) number of sigma. The odds of us all dying of a stroke on the same day is greater than the odds of us being wrong about that.
The odds aren't ever zero, but they're usually close enough.
Because factoring is not known to be NP-complete, there might turn out to be a polynomial-time algorithm for factoring, but no polynomial-time algorithm for NP-complete problems. If this were true, RSA might be broken, but other public-key algorithms might still be strong enough.