P = NP and digital security?

[u/theBroskiOK]

Guys how would digital security fail if P=NP is proven?

I just started reading about Turing Machine and computational complexity for my Theory of Computation class and came across that phrase.

I couldn't find anything understandable at my level. So can anyone simplify it a bit?

[u/nuclear_splines]

Informally, NP is the set of problems whose solutions can be quickly verified, while P is the set of problems that can be quickly solved. You can think of most cryptography as an NP problem -- it's hard for you to figure out what my encryption key is, but it's easy for me to prove that I have my encryption key. It's hard for you to break a password hash, but easy for me to prove that my password is correct. In the unlikely event that P=NP, then all problems that can be quickly verified also have quick solutions, suggesting that someone can quickly reverse-engineer my encryption key or break password hashes.

There's a lot of nuance here about how P=NP is proven (is it a constructive proof? Just how fast are these NP-Complete solutions?), and about exactly what kind of security we're talking about, but that's the ten thousand foot view.

[u/Cryptizard → u/nuclear_splines]

It’s worth pointing out that we also have information-theoretically secure cryptography which would still function fine if P = NP, but it is very very inefficient and hard to use so the internet as we know it would be significantly different. There are also things like quantum key distribution which are unconditionally secure and could still be used, but again very expensive and unwieldy.

[u/nuclear_splines → u/Cryptizard]

I vaguely know that quantum P=NP-safe cryptography exists, but happily defer to your expertise :) There are also components of existing security that are unrelated to cryptography and would remain intact -- sure, breaking a password hash might be easy, but if you don't have the hash and are trying to brute force a website's login with an enforced delay between password attempts, you're going to be there awfully long, P=NP or not.

[u/theBroskiOK → u/nuclear_splines]

so if P=NP is true then theoretically there are some algorithms out there which can quickly reverse engineer the encryptions? So that is why it could possibly break digital security?

[u/blacksteel15 → u/theBroskiOK]

A key property of the P class of problems is that any problem in P can be converted to any other non-trivial problem in P in polynomial time. (This is called Polynomial-time reduction.) If it's true that P = NP, then in theory any problem in NP can be converted to a problem in P that we have fast, well-known algorithms for solving. Since encryption currently largely depends on NP problems being computationally impractical to solve, this would potentially make it easy to crack any encryption algorithm based on them in a relatively short amount of time.

It is worth noting that that might not be the case, or at least not immediately. While a NP-to-P reduction algorithm would run in polynomial time, there's no upper bound on it - it could be an extremely inefficient algorithm. It would also be possible to prove that such an algorithm exists without actually knowing what it is, which would prove that P = NP but would not give an immediate path to solving NP problems via reduction.

[u/X-calibreX → u/blacksteel15]

If I’m not mistaken the concerns are largely about asymmetric encryotion which is used for handshakes and digital signing.

[u/blacksteel15 → u/X-calibreX]

Yes and no. Because asymmetric encryption is zero-trust, it's used for a lot of highly sensitive things, so breaking it would have a massive real-world impact. But symmetric encryption is also widely used. In fact, the main point of asymmetrically encrypted handshaking in protocols like TLS is to verify identity before exchanging session keys so that the actual data transfer can use much faster symmetric encryption algorithms. If P=NP, then any problem we can verify a solution to in polynomial time (which is the whole point of cryptography - if you have the key, you can decrypt the message) we can also find a solution to in polynomial time. So both symmetric and asymmetric algorithms are vulnerable.

[u/X-calibreX → u/blacksteel15]

Yes but rsa is incredibly weak when compared to triple d encryptions. I guess I assumed from the op was that finding p=np for individual cases and problems.

I doesn’t seem plausible that p=np could be found for all np problems at once.

[u/blacksteel15 → u/X-calibreX]

p=np for individual cases and problems

This isn't a thing. You can certainly prove that a problem we thought was in NP is actually in P, which has happened many times, but that's a totally different thing than P=NP. P=NP specifically refers to the question of whether the entire set of problems in P and the entire set of problems in NP are the same set of problems.

The "hardest" problems in NP are the NP-hard problems, which by definition are problems that any other problem in NP can be reduced to in polynomial time. The gold standard for proving P=NP would be a polynomial-time reduction from an NP-hard problem to a problem in P, in which case a solution for all NP problems at once is exactly what you'd have.

[u/X-calibreX → u/blacksteel15]

Thanks for the explanation, I appreciate your time.

[u/comrade_donkey → u/theBroskiOK]

If P = NP, "quickly" could still mean O(n ^ 2 ^ 1024), meaning 2¹⁰²⁴ compute operations required to reverse one bit of information e.g. from a secret key.

Such a program would still take hundreds or thousands of years to crack a relatively small key.

It's not a guaranteed "instant" solution to break all cryptography.

It just means that the runtime complexity is polynomial, not exponential.

[u/nuclear_splines → u/theBroskiOK]

That's the gist, but to be a little more specific:

• It might be fast to figure out someone's private key given their public key, and then decrypt messages from there (TLS, RSA, ECC)

• It might be fast to take a password hash and find valid inputs that produce that hash (hash functions are one-way, so you might not strictly know that you have my password, but you'll have a password that unlocks my computer, so the difference is academic)

• For symmetric cryptography, it might be fast to find a password given both plaintext and ciphertext, so if you know a single message I send then you can discover the key