# Finding if two points on elliptic curve are related

On a given elliptic curve I have some points that are defined like this: Where $$A=a*G$$ $$B=b*G$$ $$C=(a+b)*G$$ $$D=d*G$$ $$E=(a+d)*G$$ So finally I have two equations like below: $$A+B=C$$ $$A+D=E$$

Given the values $(C,E,A)$, is there any way I can prove that point $A$ is common in both the points $C$ and $E$?

Or can I also prove that point $A$ is part of the $C$ and $E$?

• Hint: Could you do it with normal numbers? – SEJPM Aug 18 '17 at 11:26
• @SEJPM, okay got it, I'm trying but I couldn't able to figure it out, I don't think this is any unsolvable problem, I feel there exists some solution for this. – sg777 Aug 18 '17 at 11:37

No you can't.

I'll make the argument over the integers, it directly transfers to ECC points.

Suppose you have two integers $c,e\in\mathbb Z$. You can now prove for every $a\in\mathbb Z$ that $c$ and $e$ have $a$ "in common".

For this you simply pick $b=c-a$ and $d=e-a$ and now you have the "proof" that both have $a$ in common. Note how no restrictions whatsoever have been placed on $a,c,e$ so it works with all triples.

• I may wrongly presented the question, now I made some edits and made the question much clear. – sg777 Aug 18 '17 at 12:23
• @SaratG yes it is more clear, but my answer still stays valid :p – SEJPM Aug 18 '17 at 12:24
• thank you for inputs, but here the situation is I have control over only C, E and A. I have restrictions over in picking up the values B and D. – sg777 Aug 18 '17 at 12:29
• @SaratG ahh, you didn't specify that. So are $d,b$ fixed by any means? Because if they are not and shall be recovered "on-the-fly", then my answer "literally" talks about the same $a,b,c,d,e$ as your question does. – SEJPM Aug 18 '17 at 12:34
• @SaratG OK, so while they are fixed only <some-other-party> has knowledge of them, so only they can verify your guess for $a$. As stated in the answer, in theory you could come up with $d,b$ to convince yourself that $a$ is right, for every choice of $a$. – SEJPM Aug 18 '17 at 13:15

Sometimes you can

Actually, SEJPM has it mostly right; given a triplet $(cG, eG, aG)$, there will always be a possible $B, D$ such that $aG + B = cG$ and $aG + D = eG$.

However, they does leave open the question, given a triplet $(C, E, A)$, is it representable as $(cG, eG, aG)$? If not, the first 5 equations cannot hold, and so we can know that the $C, E, A$ values we were given were not formed as specified.

A simple analogy in $\mathbb{Z}$ (the integers) would be if $G=2$, and we were given the triple $(4, 2, 7)$. Even though there are values $B, D$ that are consistent with that triplet, we can also see that there are no sets of values $a, b, d$ that make $A$ odd (as $aG$ is always even; remember, $a$ cannot be a fraction), and so we can reject that.

So, the obvious question is: can that sort of thing happen with elliptic curves? Well, the answer to that is "perhaps" (depending on the elliptic curve and whether you know the value $G$).

• There are elliptic curves that don't allow you to reject any triplet (as long as you know that $G$ is not the 'identity element')

• There are elliptic curves that, if you know what $G$ is, may allow you to reject some triplets (depending on what the value $G$ is).

• There are elliptic curves, that, even if you don't know what $G$ is, will allow you to reject some.

However, unless the elliptic curve was especially crafted, a random triplet has a good possibility of being accepted by any of the above tests.

• Shouldn't the isomorphism between $(E(\mathbb F_p),+,G)$ and $(\mathbb Z_p,+,0)$ (where we map each point to its discrete log with respect to G) prevent that we can exclude any points / integers? – SEJPM Aug 18 '17 at 14:24
• @SEJPM: there need not be any such isomorphism (at least, which extends over the entire group; of course, there will be an isomorphism if we consider only the subgroup generated by $G$); not all elliptic curve groups are cyclic. – poncho Aug 18 '17 at 14:44
• @poncho, the curve here is closed and cyclic. – sg777 Aug 18 '17 at 16:46
• @SaratG: if the curve is cyclic (that is, there exists a point $G$ such that all points can be represented as $xG$, for some $x$), and has prime order, then it's the first case I gave ("you can't reject anything"); if it's cyclic but has a composite order (typically stated as cofactor > 1), then it's the second case I gave ("you might reject some things, depending on what $G$ is") – poncho Aug 18 '17 at 17:34