For generator point $G$ in the secp256k1 curve, I want to find a value $k$ such that: $$h\equiv(k\,G)_X\,(k-d)\pmod n$$ where $n$ is the group order, and $(k\,G)_X$ indicates the x-coordinate (mod n) of the resulting point after the multiplication by $k$. Assume $h$ and $d$ are fixed scalar values that I've been given.

Is it possible to calculate $k$?

Without the multiplication by $(k - d)$, this would just be the ECC discrete log problem. Does having that extra multiplication make it easier to calculate some $k$, or is there a way to show that it still reduces to the discrete log problem?

In my experiments with smaller fields, it appears that no such $k$ value exists about 35% of the time.

  • $\begingroup$ I'd be surprised is this was sizably easier than the DLP, and would not be surprised if it was much harder: I fail to think of a $\mathcal O(\sqrt n\,\ln(n)\ln(\ln(n)))$ algorithm to solve this, when there are for the DLP. $\endgroup$
    – fgrieu
    Aug 1 at 20:06
  • $\begingroup$ @fgrieu I was actually hoping as much. It would be nice to have a proof that it's at least as hard, but it certainly makes sense intuition-wise. Thanks. $\endgroup$ Aug 1 at 20:29
  • $\begingroup$ cross-posted math.se $\endgroup$
    – kelalaka
    Aug 3 at 23:03


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.