Let $E$ be an elliptic curve over a prime or a binary extension field $GF(2^m)$, and let $G(x_g,y_g)$ be a generator point on the curve. Let $Q$ be an arbitrary point $Q = r*G$, with $r$ scalar, and $Q$ an element from the group of generator $G$ of order $n$.

I have read in some sources (e.g. here for curves over binary extension fields) that, if an actor can distinguish whether the doubling of $Q$ is accompanied by reduction (modulo $n$), then it mathematically follows that he/she can distiguish between utilizing the algorithm of division (0) or subtraction-division to reverse the sought-for number $2^l G$ or $(2^l + 1) G$, which requires no more than $log_2n$ divisions and thus reverse the elliptic curve multiplication and solve the DLP for binary elliptic curves.

Yet, I do not follow why knowledge of whether a doubling is reduced mod $n$ or not provides enough information to solve the DLP. Can someone elaborate?

  • $\begingroup$ Similar to first image of this answer. This is why we need a completeness $\endgroup$
    – kelalaka
    May 6 at 20:26
  • $\begingroup$ Is there a particular reason you're not including curves over other extension fields? $\endgroup$ May 6 at 20:43
  • $\begingroup$ @kelalaka both a point addition and a multiplication can result to reduction mod n, I do not see the connection to measuring the power usage and determine exponent bits to the question at hand. $\endgroup$ May 6 at 20:46
  • 1
    $\begingroup$ @AmanGrewal not particularly, just because of the cases I am working on, in case it makes a difference (although I can't think of any). Possibly I should generalise the question. $\endgroup$ May 6 at 20:46
  • 1
    $\begingroup$ It is not about the mod, it is about different formulas of double and add... $\endgroup$
    – kelalaka
    May 6 at 20:49


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.