Determining the order of operations in elliptic curve cryptography: Point doubling vs point addition for obtaining x and y values of a public key

Question

I have a question regarding the operations performed on an elliptic curve, specifically related to point doubling and point addition. I am trying to understand whether it is possible to determine the order in which these calculations were performed in order to obtain the x and y values of a public key.

To provide some context, in elliptic curve cryptography, point doubling refers to the operation of taking a point on the curve and finding another point on the curve that lies on the same line. This operation involves doubling the coordinates of the point and performing some additional calculations to obtain the new coordinates.

On the other hand, point addition involves taking two points on the curve and finding a third point that lies on the same line. This operation involves adding the coordinates of the two points and performing additional calculations to obtain the new coordinates.

Now, my question is whether there is a way to determine the chronological order in which these calculations were performed based solely on the resulting x and y values of a public key. In other words, can we determine whether point doubling or point addition was performed last to obtain the given x and y values?

Any insights or references to relevant research papers or resources would be greatly appreciated. Thank you in advance for your help!

Answer 1

This is not specific to Elliptic Curve groups.

Elliptic Curve points form an additive group under point addition. This means that the group addition is associative. Which then means that any valid grouping of terms during addition give the same result since addition is well defined.

First the nontrivial case: Assuming your final term $S$ has an expression of the form $S=2A,$ there is no way to tell whether it was obtained as $$ S=A+A=2A $$ via doubling, or via $$ S=C+D $$ where $C=A-U,$ and $D=A+U,$ for any other non-identity element of the group, call it $U$.

Trivially, if the element $S$ cannot be obtained by doubling (there is no $A$ such that $S=2A,$ say $S=3G,$ where $G$ is a generator) then we know it is not obtained by doubling.

Answer 2

No, for an elliptic curve group as used in cryptography, it is not possible to determine from the coordinates $(Q_x,Q_y)$ of public key $Q$ if in it's evaluation as $dG$, the last operation was a point doubling or a point addition.

One fundamental issue is that what's asked is unspecified, because the point multiplication algorithm used to compute $dG$ from $d$ is unspecified. Several algorithms for that yielding the same $(Q_x,Q_y)$ exist, and they differ in regard to if the final operation is a point doubling or a point addition.

In particular, one of the simplest algorithm to compute $dG$ from $d$ is:

• $R:=\mathcal O$

• $S:=G$

• For each bit $d_i$ of the binary expression of $d$, starting from low-order bit

  • if $d_i=1$ then $R:=R+S$
  • $S:=2S$

• Output $R$.

  For every valid $d$ (that is $0<d<n$ where $n$ is the order of $G$), the operation $R+S$ that is conditionally performed is a true point addition (that is $R\ne S$). It follows that the final output always is obtained by point addition.

Even if we specify an algorithm such that the nature of the last operation is determined by $d\bmod2=d_0$, we believe that it's not computationally possible to guess that bit $d_0$. Argument: if that was possible, another algorithm (detailed below) can be constructed that would allow to find the private key $d$. But elliptic curves groups used in cryptography are chosen so that it's believed practically impossible to find $d$ from $Q$ by any existing mean.

---

Assume there's an algorithm that, from the coordinates $(Q_x,Q_y)$ of public key $Q$ such that $Q=dG$ with $0<d<n$ (where $n$ is the prime order of $G$), outputs bit $d_0$ of $d$.

Given $Q$ as $(Q_x,Q_y)$, test if $Q=G$, in which case $d=1$. Otherwise, compute $d_0$ with the algorithm, then $(Q'_x,Q'_y)$ for point $Q':=((n+1)/2)(Q-d_0G)$. It holds $Q'=d'G$ with $0<d'=\lfloor d/2\rfloor<n/2<n$, therefore the algorithm can be used to find the low-order bit $d'_0$ of $d'$, and that is the second-low-order bit $d_1$ of $d$.

That can be extended to find all bits of $d$, and to a probabilistic algorithm that works even if the hypothesized algorithm finds $d_0$ only for a (distinguishable, non-vanishing) subset of the $Q=dG$, and is not entirely reliable.