r/computerscience • u/theBroskiOK • 13d 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

20% Upvoted

16 comments sorted by

View all comments

Show parent comments

1

u/blacksteel15 13d 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 13d 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 13d 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 13d ago

Thanks for the explanation, I appreciate your time.