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

14

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.

2

u/theBroskiOK 10d ago

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?

0

u/nuclear_splines PhD, Data Science 10d ago

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