0
$\begingroup$

If we have a Diffie-Hellman oracle then given $g^x$ and $g^y$ we can construct $g^{xy}$.

Can we construct $g^{x^{-1}}$ given $g^x$?

$\endgroup$

1 Answer 1

3
$\begingroup$

If the group is of known prime order $q$ (which is usually the setting in which DH is considered), then $g^{1/x} = g^{x^{q-2}}$, and the latter can be obtained with $O(\log q)$ calls to the DH oracle.

$\endgroup$
4
  • $\begingroup$ I thought the order is 2q. $\endgroup$
    – Turbo
    Commented Aug 19, 2023 at 8:11
  • $\begingroup$ That's not a standard setting (for example DDH is trivially broken in a group of order $2q$; moreover, note that $x^{-1}$ isn't even well defined for half of the possible values of $x$), but the same approach is straightforward to extend to that case as well. $\endgroup$ Commented Aug 19, 2023 at 12:59
  • $\begingroup$ Thank you. I am curious about your comment ddh is broken trivially on a group of order 2q. Why? $\endgroup$
    – Turbo
    Commented Aug 19, 2023 at 16:09
  • 1
    $\begingroup$ Because it's easy to recognize the subgroup of order q (which contains half of the elements) and in a DDH triple $(g^x, g^y, g^z)$, the last element being in the subgroup is clearly not independent of the other two being in the subgroup. $\endgroup$ Commented Aug 20, 2023 at 7:36

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.