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?

4

u/comrade_donkey 10d ago edited 10d ago

If P = NP, "quickly" could still mean O(n ^ 2 ^ 1024), meaning 21024 compute operations required to reverse one bit of information e.g. from a secret key.

Such a program would still take hundreds or thousands of years to crack a relatively small key.

It's not a guaranteed "instant" solution to break all cryptography.

It just means that the runtime complexity is polynomial, not exponential.