I did not understand why the decisional Diffie-Hellman assumption is harder than computational Diffie-Hellman assumption, I read that there are groups where DDH is known to be easy but CDH is still assumed to be hard.
Please, could you explain this one, by using an example?
-
4$\begingroup$ I believe that you don't mean 'harder' (that is, that the dDH problem is a harder problem than the cDH problem; obviously, it isn't), instead, you mean that it is a 'stronger' assumption (that is, for dDH to be hard makes more assumptions on the group you're on than cDH would) $\endgroup$– ponchoSep 22, 2017 at 15:48
2 Answers
There are groups that allow a 'pairing' operation; that is, an efficiently computable function $e$ with the property:
$$e(x, y^a) = e(x^a, y)$$
for all group members $x, y$ and integers $a$. Actually, the pairing operation maps the pair into another group, with the additional property $e(x^a, y^b) = e(x, y)^{ab}$; that's not important here (but is important for other uses of the pairing function). We also assume that $e$ is nontrivial, that $e(x, y)$ doesn't uniformly map to the identity group member.
In any case, if we were given four values $g, g^a, g^b, g^c$, this function would allow us to check whether:
$$e(g, g^c) \stackrel{?}= e(g^a, g^b)$$
If this equation doesn't hold, then we know that $g^{ab} \ne g^c$ (and if we make some assumptions on $e$, then we can actually get equivalence).
However, this $e$ function doesn't give us any obvious way to recover the value $g^{ab}$, given $g, g^a, g^b$
CDH asks, given $g^a$ and $g^b$, to compute $g^{ab}$. DDH asks merely to obtain enough information about it to distinguish it from a random group element. For example, merely obtaining the last bit of $g^{ab}$ with probability better than $1/2$ is enough to break DDH, but not CDH.
Given the above, no example should be needed to justify the belief that breaking DDH can in certain cases be easier than breaking CDH, or in other words, that assuming the hardness of breaking DDH can be a stronger assumption than the same with CDH.
-
1$\begingroup$ I don't think this reasoning holds up; there are known problems where obtaining 1 bit of a result is provably as difficult as obtaining the entire result; for example, some instances for the DLOG problem. This bit is known as a 'hard bit' in the literature. You need to also show that the CDH lsbit is not a 'hard bit' $\endgroup$– ponchoSep 23, 2017 at 12:41
-
$\begingroup$ @poncho I said "in certain cases", and coming up with some such cases is easy (the question did not mention any particular group). $\endgroup$– fkraiemJan 18, 2018 at 19:37