2
$\begingroup$

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?

$\endgroup$
  • 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 Dec 6 '19 at 11:59
4
$\begingroup$

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

| improve this answer | |
$\endgroup$
4
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ Nice, That was I was looking for. $\endgroup$ – kelalaka Dec 6 '19 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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