1
$\begingroup$

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!

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

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.

$\endgroup$
2
  • $\begingroup$ "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 $\endgroup$ – cisnjxqu Dec 1 '20 at 21:41
  • $\begingroup$ Right, fixed, thanks! $\endgroup$ – Geoffroy Couteau Dec 1 '20 at 23:28

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.