1
$\begingroup$

This may seem like a strange question. Lets say I have $g^x \bmod p$ and $g^{xy} \bmod p$. How can I efficiently obtain $g^y \bmod p$? I assume I must use modular inverse but I don't know where.

$\endgroup$

1 Answer 1

3
$\begingroup$

Lets say I have $g^x \bmod p$ and $g^{xy} \bmod p$. How can I efficiently obtain $g^y \bmod p$?

We hope that there is no efficient method (without using knowledge of $x$ or $y$)

Here's why: if you can solve that problem, you can solve the (computational) Diffie-Hellman problem; here's how:

  • Suppose that you did have an Oracle that, given $g, g^x, g^{xy}$, returned $g^y$

  • Then, you can use that to create an Oracle that, given $h, h^x$, returned $h^{x^{-1}}$

    Here's how, you'd call your Oracle with $g=h, g^x=h^x$ and $g^{xy} = h$. These conditions hold only if $x^{-1} = y$, and so when your Oracle returns $g^y$, that's also $h^{x^{-1}}$

  • With that Oracle, you can generate a squaring Oracle (given $h, h^x$, return $h^{x^2}$, and with that, computing DH is straight-forward.

$\endgroup$
1
  • $\begingroup$ @mathman123123: I don't see how those modifications would change my answer; with the Oracle, it would still be able to compute unmodified DH, so unless you're in a group where DH was weak, it looks impossible $\endgroup$
    – poncho
    Apr 17, 2021 at 12:35

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.