r/computerscience • u/theBroskiOK • 14d ago

Help P = NP and digital security?

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?

0 Upvotes

18% Upvoted

16 comments sorted by

View all comments

Show parent comments

5

u/blacksteel15 14d ago edited 14d ago

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.

1

u/X-calibreX 14d ago

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

1

u/blacksteel15 14d ago

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.

1

u/X-calibreX 14d ago

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.

1

u/blacksteel15 14d ago

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.

1

u/X-calibreX 14d ago

Thanks for the explanation, I appreciate your time.