-1
$\begingroup$

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?

$\endgroup$
1

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Ok. Which problems would satisfy P=NP with regard to cryptography, if polynomial time answers are found? $\endgroup$ Nov 28, 2023 at 3:15
  • $\begingroup$ Would direct methods for factoring and discrete log (modular math) qualify? $\endgroup$ Nov 28, 2023 at 3:16
  • $\begingroup$ 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? $\endgroup$ Nov 28, 2023 at 3:27
0
$\begingroup$

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.

With regards to your question:

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?

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.

Your other comments are unclear. What is a "direct method for factoring or DL"?

$\endgroup$
2
  • $\begingroup$ Thank you for answer. A direct method means a new process that does not require an exponential amount if time, and has few iterations; i.e., not normal factoring , in the case of finding factors. Think of it like using pi to get area of a circle, as opposed to breaking it into endless rectangles to get answer. $\endgroup$ Nov 28, 2023 at 14:50
  • $\begingroup$ I should have been more clear; DL and factoring are separate processes, but i want to know the effect of breaking either or both. $\endgroup$ Nov 28, 2023 at 14:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.