# Operation on elliptic curves

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?

• 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}$. – SEJPM Dec 6 '19 at 11:59

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

• Nice, That was I was looking for. – kelalaka Dec 6 '19 at 19:41