If someone finds an efficient way (ridiculous or not) to turn NP into P (such as creating multiple universes, saving the one with the correct answer), would we have any good algorithms for encryption, hashing and so on that are still secure? What other algorithms would become way more efficient? Constant-time sorting? Constant-time SHA256-cracking?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ There's a universe (in fact an infinite number of them) where someone guesses your AES key on the first go. $\endgroup$– rathJun 4, 2014 at 1:53
-
$\begingroup$ Sorting is already polynomial time, so $P = NP$ shouldn't matter for that. $\endgroup$– otusJun 4, 2014 at 5:46
-
$\begingroup$ SHA-256-cracking (preimage/collision search) is already constant time, too. The implications of P=NP for symmetric primitives are quite complicated. $\endgroup$– Dmitry KhovratovichJun 4, 2014 at 7:52
Add a comment
|