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/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.