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
    Aug 19 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$ Aug 19 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
    Aug 19 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$ Aug 20 at 7:36

Your Answer

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

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