4 ms·

The decision problem for ECDLP is not known to be NP-complete, in fact it's likely not NP-complete but rather NP-hard and therefore proving that P = NP would no

by Kranar 3y ago

The decision problem for ECDLP is not known to be NP-complete, in fact it's likely not NP-complete but rather NP-hard and therefore proving that P = NP would not provide any insight into finding a polynomial time solution for it.

tromp 3y ago
Having an efficient algorithm for SAT (or any NP complete problem) immediately gives you an efficient algorithm for ALL problems in NP, including ECDLP.
- Kranar 3y ago
  It is not known if the decision problem for ECDLP is in NP, in fact it's likely not in NP. NP-hard does not mean NP, it means a problem that is ATLEAST as hard as NP. NP-hard problems that are in NP are known as NP-Complete. Finally ECDLP itself is not a decision problem, so even if the decision problem for ECDLP is in NP and P = NP, that does not mean that ECDLP itself has a polynomial time solution. NP, NP-Complete, NP-Hard etc... only refer to decision problems, not to general purpose computations.
  - tromp 3y ago
    The decision problem for ECDLP { (Curve_spec, P, x) : x is a prefix of the discrete log of point P on the specified elliptic curve } is trivially in NP.
    - Kranar 3y ago
      I think you're mixing up quite a lot of things here. For one, apart from the impreciseness of your statement of the decision problem, it wouldn't be a decision problem for ECDLP but rather for the more general discrete logarithm problem (DLP). ECDLP is assumed to be in a higher complexity class than DLP. With that said, even if the decision problem for ECDLP is in NP and P = NP, that does not mean that a solution to ECDLP is in P.
      - tgflynn 3y ago
        A decision problem as used to define the classes NP and P is of the form: does there exist an x such that F(x) = 1, where F is a P-time computable function. If you can solve that problem in P-time then you can also solve the functional version (find an x for which F(x) = 1) in P-time simply by setting each bit to a value for which the decision problem is satisfiable, one by one.
      - tromp 3y ago
        > ECDLP is assumed to be in a higher complexity class than DLP. No, it's not. All instances of DLP, including ECDLP, are just asking for an x such that b^x = a, as Wikpedia will tell you [1]. They only differ in the choice of group, but exponentiation within the group is assumed to be an efficient operation. > With that said, even if the decision problem for ECDLP is in NP, that does not mean that a solution to ECDLP is in P. It trivially does. You simply start with an empty prefix x and extend it 1 bit at a time by repeatedly asking if (Curve_spec, P, x0) is in the language. If so you continue with x0, if not you continue with x1. [1] https://en.wikipedia.org/wiki/Discrete_logarithm https://en.wikipedia.org/wiki/Discrete_logarithm

by Kranar 3y ago

tromp 3y ago

Having an efficient algorithm for SAT (or any NP complete problem) immediately gives you an efficient algorithm for ALL problems in NP, including ECDLP.

Kranar 3y ago
It is not known if the decision problem for ECDLP is in NP, in fact it's likely not in NP. NP-hard does not mean NP, it means a problem that is ATLEAST as hard as NP. NP-hard problems that are in NP are known as NP-Complete. Finally ECDLP itself is not a decision problem, so even if the decision problem for ECDLP is in NP and P = NP, that does not mean that ECDLP itself has a polynomial time solution. NP, NP-Complete, NP-Hard etc... only refer to decision problems, not to general purpose computations.
- tromp 3y ago
  The decision problem for ECDLP { (Curve_spec, P, x) : x is a prefix of the discrete log of point P on the specified elliptic curve } is trivially in NP.
  - Kranar 3y ago
    I think you're mixing up quite a lot of things here. For one, apart from the impreciseness of your statement of the decision problem, it wouldn't be a decision problem for ECDLP but rather for the more general discrete logarithm problem (DLP). ECDLP is assumed to be in a higher complexity class than DLP. With that said, even if the decision problem for ECDLP is in NP and P = NP, that does not mean that a solution to ECDLP is in P.
    - tgflynn 3y ago
      A decision problem as used to define the classes NP and P is of the form: does there exist an x such that F(x) = 1, where F is a P-time computable function. If you can solve that problem in P-time then you can also solve the functional version (find an x for which F(x) = 1) in P-time simply by setting each bit to a value for which the decision problem is satisfiable, one by one.
    - tromp 3y ago
      > ECDLP is assumed to be in a higher complexity class than DLP. No, it's not. All instances of DLP, including ECDLP, are just asking for an x such that b^x = a, as Wikpedia will tell you [1]. They only differ in the choice of group, but exponentiation within the group is assumed to be an efficient operation. > With that said, even if the decision problem for ECDLP is in NP, that does not mean that a solution to ECDLP is in P. It trivially does. You simply start with an empty prefix x and extend it 1 bit at a time by repeatedly asking if (Curve_spec, P, x0) is in the language. If so you continue with x0, if not you continue with x1. [1] https://en.wikipedia.org/wiki/Discrete_logarithm https://en.wikipedia.org/wiki/Discrete_logarithm