# Showing formally that DDH hardness implies CDH hardness

As part of homework problem, I need to show that DDH hardness implies CDH hardness.

Assume $CDH$ is hard relative to some group generator.
The intuition is pretty clear, so I've made the trivial reduction - let $A_{CDH}$ be a PPT algorithm that computes $DH_g(h_1,h_2)$ with probability $\epsilon$, define $A_{DDH}$ as follows:
1) Given $g^x$,$g^y$ and $g^z$, return 1 iff $A_{CDH}(g^x,g^y)=g^z$

Now I look at:
$Pr[A_{DDH}(g^x,g^y,g^z) = 1]$ (the group description is given implicitly)
Where the probability is taken over independent choices of x,y and z. ($D_G$ is a description of the group, a generator $g$, and its size $q$)
I want to express the probability above in terms of $A_{CDH}$, so I've written:
$Pr[A_{DDH}(g^x,g^y,g^z) = 1]=Pr[A_{CDH}(g^x,g^y) = g^z]$
But how can I analyze it? If $g^{xy} \neq g^z$ I don't know the probability that $A_{CDH}(g^x,g^y) = g^z$, I only know that it gives (some) wrong answer with probability $1-\epsilon$
If the details aren't clear let me know, I tried to be as concise as possible. Thanks in advance!

• Hint: work out the conditional probabilities keeping in mind that the DDH challenger returns $g^z$ and $g^{xy}$ with the same probability. – Occams_Trimmer Jan 28 '17 at 12:37

## 1 Answer

Let me state the precise definition of DDH, to make it more clear: assuming a group an a generator $$g$$ are fixed, the challenger flips a coin. If he gets 0, he picks $$(x,y,z)$$ uniformly at random; if he gets 1, he picks $$(x,y)$$ uniformly at random and sets $$z = xy$$. It returns $$(g^x,g^y, g^z)$$. You win the DDH game if you can find out the coin that was flipped with non-negligible advantage over the random guess. Now, you have this adversary $$A$$ that breaks CDH with probability $$\varepsilon$$, and you would like to use it to break DDH. So, a challenger flips a coin and sends you a DDH challenge.

I've written:
$$Pr[A_{DDH}(g^x,g^y,g^z) = 1]=Pr[A_{CDH}(g^x,g^y) > = g^z]$$
But how can I analyze it? If $$g^{xy} \neq g^z$$ I don't know the probability that $$A_{CDH}(g^x,g^y) = g^z$$, I only know that it gives (some) wrong answer with probability $$1-\epsilon$$

There are two situations: either the challenger picked $$1$$, and so it holds that $$g^{xy} = g^{z}$$. As on input $$(g^x,g^y)$$, the adversary returns $$g^{xy}$$ with probability $$\varepsilon$$, in this case it returns the same $$g^z$$ that you got from the challenger with probability $$\varepsilon$$. But if the challenger picked $$0$$, then by the definition of the DDH game, $$z$$ was picked uniformly at random, and in particular, totally independently of $$x$$ and $$y$$.

So the question becomes: given $$g^x$$ and $$g^y$$, no matter how it works and how powerful it is, what are the chances that the adversary outputs $$g^z$$, which is a uniformly random group element that is not known by the adversary? You should easily convince yourself that the answer is one over the order of the group - a negligible quantity.

Hence, when the coin is $$0$$, the adversary outputs $$g^z$$ with negligible probability; when it's $$1$$, he outputs $$g^z$$ with probability $$\varepsilon$$. As the coin is flipped at random, both situations happen with probability exactly $$1/2$$ - from that, you should be able to measure the probability that you win the DDH game by answering $$0$$ when $$A$$ fails to output $$g^z$$, and $$1$$ when he succeeds.

• "adversary A that breaks CDH with probability ε, and you would like to use it to break CDH" I think you mean DDH instead of the second CDH – cisnjxqu Dec 1 '20 at 21:41
• Right, fixed, thanks! – Geoffroy Couteau Dec 1 '20 at 23:28