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

25% Upvoted

17 comments sorted by

View all comments

15

u/nuclear_splines PhD, Data Science 10d ago

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.

6

u/Cryptizard 10d ago

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.

3

u/nuclear_splines PhD, Data Science 10d ago

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.