0
$\begingroup$

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$?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Hint: Could you do it with normal numbers? $\endgroup$
    – SEJPM
    Aug 18, 2017 at 11:26
  • $\begingroup$ @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. $\endgroup$
    – sg777
    Aug 18, 2017 at 11:37

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I may wrongly presented the question, now I made some edits and made the question much clear. $\endgroup$
    – sg777
    Aug 18, 2017 at 12:23
  • $\begingroup$ @SaratG yes it is more clear, but my answer still stays valid :p $\endgroup$
    – SEJPM
    Aug 18, 2017 at 12:24
  • $\begingroup$ 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. $\endgroup$
    – sg777
    Aug 18, 2017 at 12:29
  • 1
    $\begingroup$ @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. $\endgroup$
    – SEJPM
    Aug 18, 2017 at 12:34
  • 1
    $\begingroup$ @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$. $\endgroup$
    – SEJPM
    Aug 18, 2017 at 13:15
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – SEJPM
    Aug 18, 2017 at 14:24
  • $\begingroup$ @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. $\endgroup$
    – poncho
    Aug 18, 2017 at 14:44
  • $\begingroup$ @poncho, the curve here is closed and cyclic. $\endgroup$
    – sg777
    Aug 18, 2017 at 16:46
  • $\begingroup$ @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") $\endgroup$
    – poncho
    Aug 18, 2017 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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