Complexity class of Decision Problem for Cracking Private Key in Elliptic curves

UserX

6/16/24, 12:38 PM

The integer factorization decision problem (does integer N have a prime factor = k?) is known to be an NP problem. Analogous to this, can we say that the decision problem for finding the private key of an Elliptic curve (Is r the number of times base point was added to come up with target point) is also in NP, but not NP-complete?

1 + 0

elliptic-curves

computational-complexity-theory

Score:0

Crypto

poncho

6/16/24, 12:47 PM

Analogous to this, can we say that the decision problem for finding the private key of an Elliptic curve (Is r the number of times base point was added to come up with target point) is also in NP, but not NP-complete?

Actually, the decision problem for discrete log, that is, given $r, G, H$, is $rG = H$, is in P and hence is not NP-complete (unless, of course, P = NP) - we know this is because there is a known polynomial time algorithm for this decision problem

Similarly, the decision problem for factorization , that is, given $N, k$, is $k$ a prime factor of $N$, is also in $P$.

Now, all of $P$ is within $NP$, and so they are both "NP problems", but not very interesting ones.

+ 7

UserX

6/16/24, 12:56 PM

Pardon my ignorance, but what makes the Diffie Hellman algorithm hard to break if factorization is in P?

poncho

6/16/24, 1:01 PM

@UserX did you mean RSA instead of DH - DH isn't specifically close to factorization. In any case, being able to solve the decision problem as you stated isn't sufficient. The standard way to turn factorization into an NP problem is rather "given $k, N$, are there values $x, y$ such that $1 < x < k$ and $xy = N$" - that is not known to be in $P$ (and is easy to be shown to be effectively equivalent to the general integer factorization problem)

poncho

6/16/24, 1:12 PM

@UserX similarly, for elliptic curves, the standard approach to turn the discrete log into a decision problem is "given $k, G, H$, is there a value $x$ such that $0 \le x < k$ and $H = xG$"

UserX

6/16/24, 1:15 PM

Thank you, and yes, RSA would be a better example. And talking about DH, assume the discrete logarithm problem would have such a decision variant which is hard to break, where we know that its outside P but in NP?

Wilson

6/16/24, 5:34 PM

The factorization problem is typically not phrased this way (https://cs.stackexchange.com/questions/52722/why-is-factor-in-co-np) Factorization is phrased such that it's in the intersection of NP and coNP. While Discrete Log for a prime order group is a trivial language since every element must have a discrete log with respect to a non-identity base.

poncho

6/16/24, 5:41 PM

@Wilson: I'm confused by your comment; you complain that 'factorization is in the intersection of NP and coNP", but the very link you provided shows that the decision problem I cited is in coNP (and obviously it's in NP). As for the Discrete Log problem, the decisional problem I gave is equivalent to the computational Discrete Log problem (given $G, xG$, find $x$) - in crypto circles, this is known as the "Discrete Log problem"

Wilson

6/16/24, 6:13 PM

From the phrasing of factorization from that link, it is not immediate that factorization is in P. The reason is that $w=s$ (a factor) is a witness not a part of the instance $x=(N,r)$. Thus, it's not trivially in P without a polytime factorization algorithm. Furthermore, the Discrete log problem is typically phrased as the following NP relation $R_{G, \mathbb{G}}=\{(P; z) \mid P=zG \}$ (for example, Schnorr is a proof of knowledge for this relation). $z$ is a witness not a part of the statement. For any $P$ in the group there always exists a discrete log, hence it's a trivial language.

Elon Musk

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

EN: Complexity class of Decision Problem for Cracking Private Key in Elliptic curves

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.