# Breaking CDH also breaks DHI

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.

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.
• @kelalaka: however, the nice thing with the $g^{x^{q-2}}$ approach is that it works cleanly even if your Oracle is fixed to a specific $g$ Mar 24 at 20:40