Clarification on the intractability of the Elliptic Curve Discrete Logarithm Problem

Pedro

3/16/24, 4:33 AM

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.¹

¹ 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.

228

1 + 1

elliptic-curves

Jared Smith

3/16/24, 1:34 PM

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 ≠.

Score:4

Crypto

rozbb

3/16/24, 4:58 AM

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}$.

+ 4

fgrieu

3/16/24, 5:24 AM

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.

rozbb

3/16/24, 5:41 AM

Right, good catch. I skipped that part. It's mentioned [elsewhere](https://cs.stackexchange.com/questions/113124/is-discrete-log-a-np-hard-problem), 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.

fgrieu

3/16/24, 5:52 AM

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.

rozbb

3/16/24, 6:02 AM

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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Clarification on the intractability of the Elliptic Curve Discrete Logarithm Problem

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.