2
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I think the easiest way is to show that DHI is equivalent to Square DH... $\endgroup$
    – kelalaka
    Mar 24 at 20:14
  • $\begingroup$ @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$ $\endgroup$
    – poncho
    Mar 24 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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