2
$\begingroup$

I'm currently going through the book "Guide to Elliptic Curve Cryptography" by Darrel Hankerson, Scott Vanstone, and Alfred Menezes. In the book, the authors state that

[…] there is no mathematical proof that the ECDLP is intractable. That is, no one has proven that there does not exist an efficient algorithm for solving the ECDLP. Indeed, such a proof would be extremely surprising. For example, the non-existence of a polynomial-time algorithm for the ECDLP would imply that P ≠ NP thus settling one of the fundamental outstanding open questions in computer science.1

1 P is the complexity class of decision (YES/NO) problems with polynomial-time algorithms. NP is the complexity class of decision problems whose YES answers can be verified in polynomial-time if one is presented with an appropriate proof. While it can readily be seen that P ⊆ NP, it is not known whether P = NP.

However, I can't understand why the non-existence of a polynomial-time algorithm for the ECDLP implies that P ≠ NP.

I would like to ask for clarification on this topic and if anyone knows of any resources that could help me understand this better. I have searched online, but couldn't find much information. Any insights or resources would be greatly appreciated.

Improve this question
$\endgroup$
1
  • $\begingroup$ If you want to prove P = NP you need to prove that there exists a polynomial-time algorithm for every NP problem, if you want to show that 𝖯≠𝖭𝖯 you only need one counter example of a problem in NP with no possible polynomial-time algorithm. So an NP problem with a non-existance proof of such an algorithm would imply 𝖯≠𝖭𝖯. $\endgroup$
    – Jared Smith
    Mar 16 at 13:34

1 Answer 1

Reset to default
4
$\begingroup$

This is a simpler statement than it seems. If a language $\mathcal{L}$ is in $\mathsf{NP}$, and you prove that $\mathcal{L} \not\in \mathsf{P}$, then this is a proof that $\mathsf{P} \neq \mathsf{NP}$.

The book itself doesn't define a decision version of the ECDLP problem, so I'll define one here. Given $(\mathcal{E}, n, d, G, H)$ where $\mathcal{E}$ is an elliptic curve, $G \in \mathcal{E}$ is a point of order $n$, $d \leq n$ is an integer, and $H \in \mathcal{E}$, is there an integer $k \leq d$ such that $kG = H$?

This problem is in $\mathsf{NP}$, with the witness being $k$. It is also equivalent to the search-ECDLP problem, since you can find $k$ in logarithmically many steps by doing binary search with the choice of $d$ (there's some bookeeping necessary here, e.g., what if the adversary is fallible; this is resolved by running the reduction multiple times using the rerandomization property: you can create a fresh ECDLP problem by setting $G' = rG$ and $H' = rH$ for a uniform $r \gets \mathbb{F}$).

Since the above problem in $\mathsf{NP}$, proving it to not be in $\mathsf{P}$ implies $\mathsf{P} \neq \mathsf{NP}$.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ It's made a shortcut: the decision problem discussed is not a mere rephrasing of ECDLP. We need to prove that a polynomial number of invocations of an algorithm to solve that decision problem is enough to solve ECDLP. Or is it (here I'm leaving my comfort zone) we need to prove that a polynomial number of invocations of an algorithm to solve that decision problem with non-vanishing probability is enough to solve ECDLP with non-vanishing probability. $\endgroup$
    – fgrieu-onstrike ♦
    Mar 16 at 5:24
  • $\begingroup$ Right, good catch. I skipped that part. It's mentioned elsewhere, but you only need $\log_2$ invocations of this to solve search-ECDLP if you're allowed to pick different thresholds and not just $d/2$. You do this with binary search: is $n < d/2$? If so, it less than $d/4$? If not, is it less than $3d/4$? Etc. $\endgroup$
    – rozbb
    Mar 16 at 5:41
  • $\begingroup$ The method in the above comment has changed the decision problem from the one stated in the answer (the threshold is now a parameter, instead of being fixed to $d/2$), and sidesteps the issue of algorithms that can occasionally fail (the iterative algorithm could fail with non-vanishing probability). I see how, by using arithmetic properties of finite groups and doing extra polynomial work, we can do with the original problem IF we have an algorithm that always solve the decision problem. But the vanishing probability issue bothers me. $\endgroup$
    – fgrieu-onstrike ♦
    Mar 16 at 5:52
  • 1
    $\begingroup$ The book itself does not actually define the decision version of the problem. I picked a definition that suits the statement. If this is not the correct one, then I have no idea what the authors are talking about. I'll amend my answer to reflect this. $\endgroup$
    – rozbb
    Mar 16 at 6:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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