Breaking CDH also breaks DHI

Question

I am trying to show that by breaking the Computational Diffie-Hellmann (CDH) assumption one also breaks the Diffie-Hellmann inverse assumption. Unfortunately, I am a bit stuck and do not know where to go. I suspect that bilinearity property from the pairing group given by $PGGen$ is at fault, but I do not know quite sure how to approach the problem further. The definitions are as below.

With the Computational Diffie-Hellman (CDH) defined by a PPT advarsery A where: $Adv^{cdh}_{PGGen,A}(n)$ is negligible and:

$Adv^{cdh}_{PGGen,A}(n) := Pr[Z = g^{xy} \mid PG \stackrel{$}{\gets} PGGen(1^n); x, y \stackrel{$}{\gets} \mathbb{Z}_p ; Z \stackrel{$}{\gets} A(PG, g^x, g^y)]$

and the Diffie-Hellmann inverse assumption (DHI) defined by a PPT adversary A where: $Adv^{q-dhi}_{PGGen,A}(n)$ is negligible and:

$Adv^{q-dhi}_{PGGen,A}(n) := Pr[Z = g^{1/x} \mid PG \stackrel{$}{\gets} PGGen(1^n); x, y \stackrel{$}{\gets} \mathbb{Z}_p ; Z \stackrel{$}{\gets} A(PG, g^x)]$

Any and all help would be greatly appreciated.

Answer 1

If you can break CDH, it implies you can create efficiently all the $g^{x^u}$ for all $i$ positives, by combining the fast exponentiation with a CDH oracle.

$$g^{1/x} = \begin{cases} EXP(G',u) = g & \text{if } u=0 \\ EXP(CDH(G'),u/2) & \text{if } u \text{ is even}\\ CDH(G', EXP(G',u-1)) & \text{if } u \text{ is odd}\ \end{cases}$$

Then, we can compute $g^{x^{p-2}}= g^{x^{p-2} \mod p}= g^{x^{p-2}}= g^{\frac{1}{x} \mod p}$. Then you can break DHI.