I'm extremely new to crypto, and very much inexperienced. Lately I've been reading about the Diffie-Hellman key-exchange methods, and specifically about the computational diffie-hellman assumption vs. decision diffie-hellman assumption. Specifically I'm referencing Dan Boneh's paper on DDH problem. However, I'm having some trouble understanding the difference between CDH and DDH. What are the differences? Similarities?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ Also have a look at What is the relation between Discrete Log, Computational Diffie-Hellman and Decisional Diffie-Hellman?. $\endgroup$– Paŭlo EbermannNov 2, 2012 at 18:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
The Computational Diffie-Hellman (CDH) problem is:
Given some group $G$ and group element $g$, and the elements $g^a$ and $g^b$, compute the value $g^{ab}$.
The Decisional Diffie-Hellman (DDH) problem is:
Given some group $G$ and group elements $g$, and the elements $g^a$, $g^b$ and $g^c$, determine whether $g^c = g^{ab}$
These are obviously related problems, the difference is that the CDH problem asks us to derive the DH shared secret, while the DDH problem just asks us to recognize it.
In addition, the CDH problem appears to be potentially harder, in this sense: if we're given an oracle to solve the CDH problem, we can easily solve the DDH problem (simply by handing $g$, $g^a$ and $g^b$ to the oracle, have it compute the value $g^{ab}$ and comparing that value to $g^c$. In contrast, there's no known generic way to solve the CDH problem given a DDH oracle.
As for why the DDH problem comes up so often (and in cases where one would naively expect the CDH problem to to appropriate), well, many protocols do a DH-type computation, and then use the value $F(g^{ab})$ (for some function $F$); breaking the protocol may allow an attacker to recover the value $F(g^{ab})$. Now, recovering this value would allow us to solve the DDH problem (by comparing that value to $F(g^c)$); hence, breaking the protocol would allow us to solve the DDH problem; or equivalently, if the DDH problem is hard, the protocol is secure. However, if the function $F$ is one-way, recovering the value $F(g^{ab})$ doesn't give us the value $g^{ab}$, and so there is no reduction of the security of the protocol to the CDH problem.
-
1$\begingroup$ what do you mean by saying "However, if the function $F$ is one-way, recovering the value $F(g^{ab})$ doesn't give us the value $g^{ab}$, and so there is no reduction of the security of the protocol to the CDH problem"? why is there no reduction of the security of the protocol to the CDH problem? thank you $\endgroup$– T.BSep 16, 2013 at 7:21
-
1$\begingroup$ @Alex: when we state "problem X can be reduced to problem Y", we mean that if we are given a solution to problem Y, we can then solve problem X (hence, X is either easier, or as difficult, as Y). In this case, if you are given a magic black box that, given $g$, $g^a$, $g^b$, gives you $F(g^{ab})$, the CDH problem remains hard; we can recover the value of $F(g^{ab})$, however there doesn't appear a way to get the full $g^{ab}$ value demanded by CDH $\endgroup$– ponchoSep 16, 2013 at 21:29