# If it is proved that P=NP, what happens to crypto? [duplicate]

If various PKC is shown to be not NP=Hard, what happens to crypto? More importantly, what happens to crypto wallets? If it is shown that P=NP for many currently assumed to be hard problems, but finding the easy solution is itself hard, does the original problem remain NP=Hard?

• Nov 27, 2023 at 21:13

If P=NP and the polynomial complexity is not unreachable (a sufficiently high constant can still render polynomial time impractical) then all non-information-theoretically secure cryptography is impossible in principle.

The reason being is that any computationally-bound cryptography can be represented as a circuit. And solved by solving an NP problem such as boolean satisfiability.

• Ok. Which problems would satisfy P=NP with regard to cryptography, if polynomial time answers are found? Nov 28, 2023 at 3:15
• Would direct methods for factoring and discrete log (modular math) qualify? Nov 28, 2023 at 3:16
• If a method of finding factors, or the "secret" number in a mod operation takes only 5-10x the amount of computation as running the original function, would that qualify as answering the problems as being easy? Nov 28, 2023 at 3:27

First of all, $$P\neq NP$$ has to do with worst-case complexity not average case, so it's really not a good basis for developing cryptosystems in the positive direction. Systems based on problems which are NP-hard were broken. You want your cryptosystem to be hard to break on average.

Even breaking a supposedly one-way function with a polynomial factor of extra complexity would be easy. So if the reverse direction can be computed within $$f(n)\times (n)$$ where $$f(n)$$ is a polynomial and $$C_f(n)$$ is the complexity of the forward computation, this would be enough to be considered a break. We want $$f(n)$$ to be exponential in $$n$$ for security.