how-to block ads
|
|
Share Topic
 |
 |
|
|
 vpokoPremium
join:2003-07-03
Boston, MA | reply to DataRiker
Re: Wasting more $$$ 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. | |
|
