4 edits | reply to PToN
Re: Wasting more $$$ Sorry, I was using a little historical reference.
One time pads were often termed "short ciphers' because during the cold war diplomats carried the keys in a envelope thus the both the message and the cipher had to be "short"
Surprised an expert like your didn't know that. But I guess that's the difference of learning something in a classroom vs Wikipedia 
Further more, about factoring. There is overwhelming statistical evidence that there is indeed no pattern to larger prime numbers which would be a requirement for the premise. ( think about why that is )
I don't know of any literature that does not concede this point. Similar to the evidence of Fermat's last theorem being true. Just because we lack a formal proof doesn't mean that we don't have a pretty good idea of the answer. ( and Fermat's last theorem was indeed proven true, which was an almost certainty given its statistical evidence and lack of a simple counter example ) |
|
|
|
 vpokoPremium
join:2003-07-03
Boston, MA | From the sounds of it, I don't think you've ever studied this in a classroom, you're just regurgitating incomplete ideas that you read without understanding. First you said that current ciphers are mathematically proven to be secure, now you're saying, "Just because we don't have a formal proof..." You can't have it both ways. Again, the only current cipher that's provably secure is the one time pad. |
|
4 edits | Once again, the idea that P=NP is so universally rejected that I can only assume your trying to troll or are very ignorant and simply don't read the literature.
Also on a very related topic, you blissfully unaware that every piece of modern literature suggest with almost certainty that there is no pattern to the larger prime numbers.
That doesn't bode well for P = NP does it?
Lastly, I can forgive not knowing my dated term "short cipher" since beyond a few old books I have I bet its NEVER used since it can be confused with a literal short cipher.
Now, who was the one talking out of their ass again?  |
|
vpokoPremium
join:2003-07-03
Boston, MA | I take back the part about you talking out of your ass, I think you do know what you're talking about but we're just talking past each other.
No, I don't think that P=NP (though some respected computer scientists, like Richard Lipton, do). I was using it as an example of why current ciphers are not provably secure. In math, provable has a very precise meaning. If there is no formal proof, then it's not proven. Again, I'm not trying to patronize you since I'm guessing you understand this and were just using a more colloquial definition for the word proof, but that definition should never be combined with the word "mathematical" since now you're in real proof territory.
I'm also far from convinced that RSA is actually 100% secure, even in practice (I'm mentioning RSA since we're talking about factoring, even though the article is about AES). This is for much more pedestrian reasons than the tiny possibility that P=NP. For one, once a quantum computer with enough qubits is built, RSA will have been broken. Another reason is that RSA depends on the trapdoor one-way function assumption (that functions exist which are easy to calculate but hard to invert, unless a piece of information called a trapdoor is known). Russel Impagliazzo breaks out the possibilities nicely in his "Five Worlds" paper.
Again, from a practical point of view - whether dealing with asymmetric ciphers like RSA or symmetric ciphers like AES - I would not advise encrypting something with the expectation that it stay unbreakable forever. This is precisely because these ciphers are not provably secure and we have no idea what new mathematical techniques could be invented (or already exist without our knowledge) to break them. |
|
4 edits | said by vpoko: In math, provable has a very precise meaning.
The N=NP problem might not even be provable one way or the other.
Read Godel's work on incompleteness if your curious. ( If remember correctly, Godel himself doubted that an equivalent problem had a solution as early the 1950's)
Which brings up the reason for my last reply. knowing this, at what point would you feel comfortable saying the N=NP is false?
Should we refrain from saying Mathematically secure forever?
|
|
vpokoPremium
join:2003-07-03
Boston, MA
1 edit | said by DataRiker:said by vpoko: In math, provable has a very precise meaning.
The N=NP problem might not even be provable one way or the other. Read Godel's work on incompleteness if your curious. ( If remember correctly, Godel himself doubted that an equivalent problem had a solution as early the 1950's) Which brings up the reason for my last reply. knowing this, at what point would you feel comfortable saying the N=NP is false? Should we refrain from saying Mathematically secure forever? It's possible that P vs. NP is independent of a particular set of axioms (like ZF set theory), though I don't know of any convincing arguments for that being true. Interestingly enough, if it's independent, there may actually be a proof of its independence (such as the proofs of independence that exist for the axiom of choice and continuum hypothesis), or the proof may itself be independent (ad infinitum). It's also possible that only a non-constructive proof exists, for example showing that P=NP but without giving us an algorithm for solving an NP-complete problem like 3SAT. Both of those options would be incredibly unsatisfying. Scott Aaronson, currently a computer science professor at MIT specializing in computational complexity theory, wrote a great survey article on the possibility of formal independence for the P vs. NP problem. It that can be found here: »www.scottaaronson.com/papers/pnp.pdf.
As far as verbiage, yes, in the absence of a formal proof I would refrain from calling something mathematically proven. That's not to say that I wouldn't use the ciphers in practice, and even assume that they're probably secure, but math isn't like physics - in math, a formal proof is the only kind of proof. Incidentally, it's said that the legendary Richard Feynman refused to even accept P vs. NP as an open problem because it was so obvious that they were not equal. But after all, Richard Feynman was a physicist. |
|
