Let $Y = xG$ be a point on an elliptic curve, $G$ the generator point and $x$ a scalar. Without knowing $x$, is it possible to calculate $x^nG$, being $n$ a natural number?

  • 1
    $\begingroup$ Computing $xnG$ (without exponentiation) would be easy, but I think computing $x^nG$ is not possible w/o knowing $x$ because you only have addition available as operation which only allows you to compute scalar multiplication which would require you to know $x^{n-1}$. $\endgroup$
    – SEJPM
    Commented Dec 6, 2019 at 11:59

2 Answers 2


It is believed to be hard. In fact, even given $G, xG, x^2G,\dots,x^{n-1}G,x^{n+1}G,\dots,x^{2n}G$, you still can't compute $x^nG$; this is called the Generalized Diffie-Hellman Exponent assumption (see Fig. 1 here).


Actually, it can be proven that the problem "given $G, xG$, compute $x^nG$ is equivalent to the CDH problem (for small $n>1$, and assuming that none of the subgroups have a size divisible by $n$). In particular, given an oracle that can compute $x^nG$, you can, given $xG$ and $yG$ and with $3(n-1)$ queries to the oracle (and a handful of point additions), compute $xyG$.

Here's how it works, for $n=2$, we have:

$$2xyG = (x+y)^2G-x^2G - y^2G$$

Hence, three calls to the Oracle, and a point halving gives the answer.

For $n>2$, we compute $x^2G$ by constructing:

$(x+0)^nG = x^nG$

$(x+1)^nG = \binom{n}{0}x^nG + \binom{n}{1}x^{n-1}G+ … + \binom{n}{n}x^0G$

$(x+n-2)^nG = \binom{n}{0}(n-2)^0 {x^nG} + \binom{n}{1}(n-2)^1 x^{n-1}G+ … + \binom{n}{n}(n-2)^n x^0G$

We can treat this as $n-1$ linear equations in $n-1$ unknowns $(x^nG, x^{n-1}G, …, x^2G$, with $x^1G$ being known), and so can solve for $x^2G$.

Then, using the previous technique, we can compute $xyG$ by computing three squares.

We assume that the CDH problem is hard, hence we must assume that the $x^nG$ problem is hard as well...

  • $\begingroup$ Nice, That was I was looking for. $\endgroup$
    – kelalaka
    Commented Dec 6, 2019 at 19:41

Your Answer

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

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