Can we reduce Diffie-Hellman problem to "Discrete-log inversion" problem?

Question

Let $G$ be a cyclic multiplicative group of order $n$. Let $g$ be a (public) generator of $G$. The Diffie-Hellman (DH) problem asks: Given $g^x, g^y\in G$ for $x, y\in \mathbb{Z}^*_n$, to compute $g^{xy}\in G$.

Let $O$ be an oracle that works as follows: it takes as input $g^x\in G$ for any $x \in \mathbb{Z}^*_n$, it outputs $g^{1/x}\in G$. In other words, $O(g^x)=g^{1/x}$. I call this the "Discrete log inversion" oracle for lack of a better name.

Can we use $O$ to solve the DH problem. I remember reading about this somewhere but can't locate the reference.

Note: $1/x$ is defined as the inverse of $x \in\mathbb{Z}^*_n$.

EDIT: To visualize such a group, let $n=15$ and consider the subgroup of $\mathbb{Z}_{31}^*$ generated by 7, which is $\{1, 7, 18, 2, 14, 5, 4, 28, 10, 8, 25, 20, 16, 19, 9\}$, containing exactly 15 elements. In this case $G=\{7^i \bmod{31}|i \in \mathbb{Z}_{15}\}$

Answer 1

The answer is yes; see Chapter 21 of Galbraith's book. Suppose we have your Fixed-Inverse-DH oracle $O(\cdot)$, and given $g^a$ and $g^b$ we want to find $g^{ab}$. We do this in two steps. First, we use $O$ to compute $g^{a^2}$ from $g^{a}$—this is a related problem called the Square-DH problem. Then we use the quarter-squares identity to compute $g^{ab}$.

To compute $g^{a^2}$ from $g^a$ using $O$, we perform:

$$ \begin{align} x &= O(g g^a) = g^{1/(1+a) \bmod n} \\ y &= O(g / g^a) = g^{1/(1-a) \bmod n} \\ z &= O((xy)^{1/2 \bmod n}) = g^{1 - a^2} \\ w &= g / z = g^{a^2}. \end{align} $$

Let's call the above procedure $S(\cdot)$. Now, we use the quarter-squares identity

$$ (x + y)^2 - (x - y)^2 = 4xy, $$

to compute $S(g^{a}g^{b}) / S(g^{a}/g^{b}) = S(g^{a+b}) / S(g^{a - b}) = g^{(a+b)^2 - (a-b)^2} = g^{4ab}$. Exponentiate to ${1/4 \bmod n}$ and obtain $g^{ab}$.