Elliptic Curve - distinguish between two points after multiplication

Robert M

9/22/23, 6:08 PM

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.

295

0 + 0

elliptic-curves

Score:4

Crypto

Daniel S

9/22/23, 8:08 PM

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

0 + 0

kelalaka

9/23/23, 7:26 PM

I don't claim that my answer is covering the distinguishing, however, I don't see how this does?

Daniel S

9/24/23, 3:12 AM

It shows that distinguishing is impossible because both derivations are equally possible.

kelalaka

9/24/23, 6:34 AM

Actually, the point coordinates are not random, which is not close to claiming with a simple argument.

Daniel S

9/24/23, 6:37 AM

At no point do I claim that the point coordinates are random.

Score:1

Crypto

kelalaka

9/22/23, 6:16 PM

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

0 + 0

meshcollider

9/22/23, 7:18 PM

The question is not asking if you can find $n$, it is asking if you can distinguish which generator point was used

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Elliptic Curve - distinguish between two points after multiplication

TH: Elliptic Curve - แยกความแตกต่างระหว่างสองจุดหลังการคูณ

RO: Curba eliptică - distinge între două puncte după înmulțire

RU: Эллиптическая кривая - различать две точки после умножения

VI: Elliptic Curve - phân biệt giữa hai điểm sau khi nhân

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.