Showing formally that DDH hardness implies CDH hardness

Question

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!

Answer 1

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.