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.
In other words, cryptography is dust in the air?
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.
For 90% of the public, ALL math problems more complex than 2+2 are hard!
Learning HOW to think is more important than learning WHAT to think.
In an article on TechnologyReview.com, Simson Garfinkel spells out the real-world consequences of this mathematical conundrum.
Who else read that as Simon Garfunkle? Come on... I couldn't be the only person here, could I?
And besides... if you want real security, just do double encryption. use two common, off-the-shelf encryption methods, one encrypting the other's data and your data is now as safe as it can get. further encryptions in encryptions will only add to bloat and time to decrypt.
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.
When will people learn that as long as people have secrets to keep they'll find ways of keeping them? There may be advances in technology which will render certain methods of keeping the secret obsolete, but this search for a magic algorithm is silly.
I imagine one day there may be an advance that will mean a total security overhaul will be required though, and that could provide a window of chaos in the most extreme circumstances. However every advance in decryption tends to quickly lead to an advance in encryption that can beat it. At least historically that's been the way it is.
Until they can literally read the contents of my brain, I'm not too worried.
These posts express my own personal views, not those of my employer
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.
Mathematics is a 'human thought construct', man. The interesting part about it is that these ideas reliably correspond to real things. There's nothing inherent in the universe to say that three apples can't be described some other way, but mathematics describes it as '3' and if I add '2' more, I get '5'.
Realistically, I could argue "what constitutes an apple?" or "are these apples really '1' each?", but as far as mathematics goes, it's the ideals of the numbers matter.
"Random" isn't random when you're talking about coin tosses or roulette, just a very complex and physical "pseudo-random". "Random" is a mathematical ideal, just like "2" apples. While we can't generate truly random, we can get damn close, and certainly close enough to use. (Example: Via's C3 'Padlock' encryption engine takes electrical noise off the chip. Not truly random, but good enough to keep people from reading your e-mail.)
For that reason, when we're talking about one-time pads and the like, the proof of uncrackability has to do with the ideal, not the fact that we're getting our random data set from a monkey at the zoo. Obviously if your "random" data set was a monkey who sat on the "A" key for twenty minutes, that's a factor. But the ideal is what we're talking about, and if we can get close *enough*, we should be fine.
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.
Actually, I'm thinking second-to-last really. As the third-to-last person on the earth, I may choose to encrypt a document entitled "How to kill Fred and Bill" so that that the other two may not access it.
But as you'll be dead I don't think it matters to Bill and Fred anymore.
Adding 2 numbers and 25 billion numbers is really not that dissimilar in ways of difficulty, however it still takes a lot longer to do one than the other. The strength of cryptography doesn't come from how hard something is so much as how long it takes to do all that simple math.
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.
Well, "enough CPU cycles" is usually so high a number that it isn't possible to compute before the end of the universe.
The problem is, however, that the random nature of quantised states exerts some influcence on macroscopic states. It's not very big. In fact, it's posivtly tiny (other wise the quantum nature of things would have explored sooner). Let me give an example.
Light has momentum. The solar sail is the most direct application of this.
Consider a coin toss. In the average place where it takes place, there is uneven illumination. That is, as the coin is spinning, there will be time where the illumination on one side is different to the other. So far this is still accontable for.
However, some of the incoming light will be absorbed by the material of the 'coin', which will enter an excited state, and then later re-emit that light. There is a hugh amount of photochemistry which relies on this sort of behaviour.
So, as the coin is spining in the air, the momentum from reflected light is calculable. Let's ignore the effect of absorbing the light, and focus on the re-emmision which will apply some momentum. In what direction is the light re-emited?
Well, that's a tough question. Most importantly, as the coin is spinning in the air, it depends on the time between absorbtion and re-emmision. That's a quantum phenonema, and is randomly distributed in a Gaussian disribution about some mean.
So, to calculated the effect of the coin toss exactly, you need to account for all those quantum effects. Which is impossible, because they are random.
I accept my example is a little contrived, in that the effect of the differential momentum transfer by photonic processes is negligable for any real coin, compared to other factors. It is, however, not zero, and is a solid example of how the randomness of quantum events effects macroscopic observables.
Given enough time, the fuzzyness of the quantum states gradually takes over. For most things that's a long time - it is, however, non zero.
Thank you for making my point. Quantitative changes occur incrementally over time, like memory requirements. Qualitative changes, however, like the fundamental difference between quantum computers and Von Neumann computers, and the algorithms that can be executed on each, don't.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
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.
Only on Slashdot would such a comment be moderated "Insightful". I guess the reason that any comment that insults the majority of the populace gets modded up on Slashdot is the social insecurity felt by the moderators. Does it make you feel good to insult a huge portion of the populace? Does it make everyone feel so much smarter and better than all those evil "jocks" that picked on you in high school?
Grow up. Nerds, geeks, computer experts are not the only intelligent people out there.
Yeah, mod me as flamebait, whatever.
Forget the whales - save the babies.
The bottom line - no political party can be trusted to secure your privacy, civil liberties, etc. Pick your candidates on their individual stances on the issues important to you. Depressingly, most of the time the only difference between the parties (and candidates) is how much lubrication they'll use when fucking you in the ass.
Help save the critically endangered Blue Iguana
If the only humans left are you, Britney, and Christina, we might as well give up on the continuation of the human race anyway...
-- The act of censorship is always worse than whatever is being censored. Always.
Few people know that Ashcroft was once a crusader for personal freedom and privacy and took a stance against the Clipper Chip. Oh course, NOW he is a total fucktard who wipes various parts of his body with the bill of rights, I guess prolonged exposure to government does that to people.
Incidently most of the geeks I know (myself included) who voted for Bush did so because at the time he appeared to be the lesser of two evils. Al "Mr Clipper Chip" Gore certainly was no friend of the technology industry or anyone interested in privacy while he was VP.
Of course now we know that there are no lesser of two evils. Kerry and Bush will both screw over the country hard. Let's face it, nobody likes either of these two failures. They just hate the other guy enough to pretend to like one of them. It is a sad say in the US when these two are the best options we have.
Finkployd
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.
Today we use the same approach:
No. It's not the same. Holes in DES or AES arise only because of human error in creating the cipher. (And if you wanted better security, you'd be using Diffie-Hellman anyhow). They are not expected, anticipated, or unavoidable.
But in a hypothetical future with quantum computing, breaking the encryption doesn't rely on discovering a flaw, just going through the work. Fundamentally so much easier.