5
$\begingroup$

Given an elliptic curve group with a generator $G$ where $G$ has a prime order, p. Given a point $P=aG$ for some unknown $a$. Is it possible to efficiently calculate $Q=a^{-1}G$ without a discrete log operation?

With a discrete log, the problem is simple: first calculate $a$, then $a^{-1} = a^{p-1} $ mod $p$.

But I can't reduce a diffie-hellman problem to this to break it. Nor do I have the background to prove it directly (I have a background in NP-complete problems).

I see that the possibility of this operations would break a tiny subset of shared secrets but this should be negligible. So unless I'm wrong the existence of this algorithm isn't inconsistent with the original proof.

$\endgroup$

1 Answer 1

2
$\begingroup$

The name of the problem is `the Inverse Diffie-Hellman problem'. It is as hard as solving the computational Diffie-Hellman problem. A proof can be found in chapter 21, p.448-449 of Mathematics of Public Key Cryptography by Steven Galbraith (2012).

Source: this stackoverflow question.

$\endgroup$

Your Answer

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

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