Join Log in
Score:2
Rory avatar Crypto

Breaking CDH also breaks DHI

mp flag
Rory

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.

83
0 + 0
Score:3
Ievgeni avatar Crypto
cn flag
Ievgeni

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.

0 + 0
kelalaka avatar
in flag
kelalaka
I think the easiest way is to show that DHI is equivalent to Square DH...
0
Reply
poncho avatar
my flag
poncho
@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$
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.