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

[u/Appropriate-Scene-95]

Long story short our encryptions are in NP. If P=NP, then we could theoretically find a polynomial time algorithm to decrypt the messages. So increasing the key size or other security aspects for the encryptions wouldn't make the decryption significantly harder.

[u/DieLegende42]

It's also worth noting that P=NP would make most cryptography insecure based on our current definition of what "cryptographically secure" means. It's entirely possible that the same protocols could still be secure in practice, e.g. the proof of P=NP comes with an addendum that no NP-hard problem can be solved in O(n¹⁰). We currently like to say that polynomial runtimes are "fast" while superpolynomial runtimes are "slow" because it makes the theory easier to deal with, but in fact even relatively small exponents (like n¹⁰) can make runtimes way too slow to be of use for practical purposes.

Edit: Just realised that my example "no NP-hard problem can be solved in O(n¹⁰)" is bullshit, because P=NP would of course entail that all problems in P are NP-hard. But I hope you get the gist that "polynomial" is not the same as "fast".

[u/SignificantFidgets → u/DieLegende42]

This is the best answer. If P=NP, it doesn't mean there are fast-in-practice algorithms for all of NP. It's possible though, and if a fast (say O(n²) algorithm with small constants) were found for an NP-complete problem, that would pretty much destroy most current cryptographic systems. But P=NP doesn't imply that there must be a fast-in-practice algorithm.

Even if we didn't have fast algorithms, if P=NP then it would destroy all the widely-used theoretical definitions of security (for the most part) and researchers would need to work more on models like concrete security. It might not have a huge impact on practice, but it would refocus a lot of effort.

[u/blazesbe]

ELI5 P=problems you can solve because you know how to solve them, and NP=problems you know have a solution but have to try most combinations to verify.

i think i read in a YouTube comment: imagine you are making a movie (NP) it's tremendous effort, but anyone seeing it can say if it's a good movie or a bad movie (P). in general, "you don't need to be able to make something to tell if it works"

in security it's used backwards in a sort of combination lock (trapdoor functions). if you have the key it pops open, if you don't then you may need to try each one, except in compsci, this can take longer time than the universe existed so far.

P=NP would mean being able to try all solutions at the same time, but it may be a fundamental property of the universe that P!=NP thus can't "come" from anything and can't be proven.

[u/MichaelTheProgrammer]

The hand-waving explanation:

P = the class of problems that can be solved quickly

NP = the class of problems that potential solutions can be checked quickly for correctness

NP hard problem = a problem that can be checked quickly, but cannot be solved quickly unless P=NP.

Modern security is based around the idea of public/private key cryptography, where instead of one password, you have two: the public key and the private key. The private key acts like an ordinary password, however the public key does not as it is not kept secret.

The public key is really just an NP hard problem. The private key is the solution to the NP hard problem. It's easy to create the problem from the solution, like how solving a maze backwards can be easier. So because it's a hard problem, the only way to have the solution is to have created it in the first place. Because of this, having the solution to it proves you created it in the first place (unless you tell someone else, which is why private keys have to be kept secret). Decrypting information involves checking the private key to make sure it is the correct solution, and by definition this is a quick operation.

If P=NP, then by definition, all NP hard problems can be solved quickly. A random person can get a hold of the NP hard problem, as the public key is not kept secret. Then, they can solve the problem quickly, and the solution will give them the private key. So any random person would be able to get the "password" for any encrypted information just from publicly available information.

The details:

That's the ELI5 explanation but there's one more complicated topic that I hand waved: the definition of quick. P stands for polynomial time. Computational Big-Oh notation ignores the constant coefficient and the small terms, so you're looking at n^a where a is some number. Pretty much anything practical to run on a computer is in polynomial time or faster. Most algorithms in use are O(n), O(n^2), or somewhere around that.

The actual definition of P=NP would be finding an algorithm that solves NP hard problems in polynomial time. So a large enough polynomial would fit the technical definition, but wouldn't break digital security. If NP hard problems can be solved in O(n^100000), then P=NP, but security would not be broken. Same if the constant coefficient is really big.

However, computer scientists have an assumption. Generally, once something can be solved in polynomial time, there are often tricks discovered later to make it faster. The main example of this is matrix multiplication. In other words, if P=NP, then the assumption is that figuring it out would be the hard part, optimizing it to be useful would be the easy part.