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.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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).
-
$\begingroup$ I don't claim that my answer is covering the distinguishing, however, I don't see how this does? $\endgroup$– kelalakaMay 23 at 19:26
-
1$\begingroup$ It shows that distinguishing is impossible because both derivations are equally possible. $\endgroup$– Daniel SMay 24 at 3:12
-
$\begingroup$ Actually, the point coordinates are not random, which is not close to claiming with a simple argument. $\endgroup$– kelalakaMay 24 at 6:34
-
1$\begingroup$ At no point do I claim that the point coordinates are random. $\endgroup$– Daniel SMay 24 at 6:37
$\begingroup$
$\endgroup$
1
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!.
-
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