1
$\begingroup$

If $P$ and $Q$ are two points on an elliptic curve of large prime order, given $P, Q$, and a point $R$ which is either (a) $nP$ or (b) $nQ$, is it possible to determine if $R$ is of form (a) or form (b)? Here $n$ is a secret.

$\endgroup$

2 Answers 2

4
$\begingroup$

As there exist both $n_1$ and $n_2$ such that $R=n_1P$ and $R=n_2Q$, $R$ is of form both a) and b). In general all elements of a cyclic group of prime order are generators and so all elements are multiples of all other elements (if the group operation is written additively).

$\endgroup$
4
  • $\begingroup$ I don't claim that my answer is covering the distinguishing, however, I don't see how this does? $\endgroup$
    – kelalaka
    May 23 at 19:26
  • 1
    $\begingroup$ It shows that distinguishing is impossible because both derivations are equally possible. $\endgroup$
    – Daniel S
    May 24 at 3:12
  • $\begingroup$ Actually, the point coordinates are not random, which is not close to claiming with a simple argument. $\endgroup$
    – kelalaka
    May 24 at 6:34
  • 1
    $\begingroup$ At no point do I claim that the point coordinates are random. $\endgroup$
    – Daniel S
    May 24 at 6:37
0
$\begingroup$

If anybody can find out $n$ given $R$ and $[n]P$ or $[n]Q$ then they can break the discrete logarithm on this curve. To solve the DLog, just provide them $(R,[n]P, [n]P)$ and you solved DLog. So, this is equivalent to DLog.

One can distinguish weather $R = [n]P$ or $R = [n]Q$ ( i.e. determines that $R$ is from generator point $P$ or $Q$ ) if they are able solve the Dlog. The reverse reduction is not clear yet!.

$\endgroup$
1
  • 2
    $\begingroup$ The question is not asking if you can find $n$, it is asking if you can distinguish which generator point was used $\endgroup$ May 22 at 19:18

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.