= 27d567bc2d48d9f40e9ccc20ea370b15)
gwern comments on How does MIRI Know it Has a Medium Probability of Success? - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (137)
What? Why? Just because RSA would be broken? Shor's algorithm would also do so, even in a proven P!=NP world. There may be other substitutes for RSA, using different complexity classes. There are other approaches altogether. Not to mention one-time pads.
As I understand it, if P=NP in a practical sense, then almost all cryptography is destroyed as P=NP destroys one-way functions & secure hashes in general. So RSA goes down, many quantum-proof systems go down, and so on and so forth, and you're left with basically just http://en.wikipedia.org/wiki/Information-theoretic_security
http://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf discusses some of this.
And life was so happy with just one-time pads?
Really, if P=NP, then encoding your messages would be quite low on the priority list ... however we're not debating the practical impact here, but that "finding a provably secure encryption scheme is harder than proving P!=NP", which was raised as a nitpick, and is clearly not the case.
Happiness or unhappiness of life with one-time pads notwithstanding.