0
$\begingroup$

Imagine that you are given a point $P$ so that $P=a\times G$. If you have no knowledge of $a$ is that possible to calculate point $I$ so that $I$ is the modular inverse of $P$?

We know that over prime fields each member has a modular inverse, which means for $a\in \Bbb F_n$ there exists $x$ so that $ax\equiv 1\pmod n$. Now, My question is, is that possible to calculate point $I$ on the same curve as $P$ for which the equation $I=x\times G$ holds. This is to happen with no knowledge of either $a$ or $x$.

If such algorithm exists or become discovered in future will that be considered a weakness to the security of elliptic curves?

$\endgroup$
  • 1
    $\begingroup$ Elliptic curve points do not have modular inverses. We can compute the additive inverse, $-P$, by negating the $Y$ coordinate of $P$ so that $-P + P$ is the identity element. It does not reveal anything about $a$. $\endgroup$ – user13741 Aug 2 at 17:44
2
$\begingroup$

No, this is a known variation of the computational Diffie-Hellman problem, called Inverse computational Diffie-Hellman (InvCDH), according to which on input $g$, $g^{x}$, it is difficult to find $g^{x^{-1}}$.

See section 2.2 at Variations of Diffie-Hellman Problem by Bao et al. for more info and problem reduction proofs.

$\endgroup$
  • $\begingroup$ Will that reveal $a$ or $x$ if one can compute $I$ from $P$? $\endgroup$ – PouJa Aug 2 at 19:30
  • $\begingroup$ How would you compute $I$ without the knowledge of $a$ in the first place? It's even difficult to decide if $P$ and $I$ are made from a $x$ and it's inverse $x^{-1}$, respectively, in prime-order elliptic curves with large embedding degree (like secp256r1/k1), due to the Inverse decisional Diffie-Hellman assumption. $\endgroup$ – Kostas Chalkias Aug 2 at 21:35

Your Answer

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

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