What is the relation between Discrete Log, Computational Diffie-Hellman and Decisional Diffie-Hellman? How are the three problems Discrete Logarithm, Computational Diffie-Hellman and Decisional Diffie-Hellman related?

From my understanding, since the Discrete Log (DL) Problem is considered hard, then so is CDH.
And since CDH is considered hard, then so is DDH.

On the Wikipedia article for DDH it mentions that DDH is considered a stronger assumption than CDH. What does that mean?
The problems:


The Discrete Logarithm problem: Given $y$, find $x$ so that $g^x = y$.
The Computational Diffie-Hellman problem: Given $y_1 = g^{x_1}$ and $y_2 = g^{x_2}$ (but not $x_1$ and $x_2$), find $y = g^{x_1·x_2}$.
The Decisional Diffie-Hellman problem: Given $y_1, y_2, y_3$, decide whether they are of the form $y_1 = g^{x_1}$, $y_2 = g^{x_2}$ and $y_3 = g^{x_1·x_2}$ for some $x_1, x_2$ (which you don't have to find). Assume with 50% probability they are really of this form, and with 50% probability simply randomly selected, and you have to guess right with significantly better probability than 50%.


All three of these are defined in any (multiplicatively written) group, and are hard in some groups, while easy in other ones. (Actually, we don't really need a group, a semigroup with some generator $g$ is enough. But it is more interesting in groups.)

Which one is harder?

Now, if you have a machine (program, oracle) which solves (efficiently) the Discrete Logarithm Problem in some group, you can easily construct a solver for the Computational Diffie-Hellman problem (in the same group):


just compute $x_2$ from $y_2$ and calculate $y = (y_1)^{x_2}$.


There is no (generic) known way for the other direction.

If you have a solver for the Computational Diffie-Hellman problem, you can also decide the Decisional Diffie-Hellman problem:


just compute $y$ to $y_1$ and $y_2$, and checking $y = y_3$.


There is no (generic efficient) known way for the other direction.

This means, DDH is at least as easy (or even easier) as CDH, and CDH is as least as easy as DL. Or, other way around, DL is at least as hard as CDH, and CDH is at least as hard as DDH.

An even another way of looking at it is the "assumption to be hard", where "hard" is defined as "not doable for a reasonable user".


If DDH is hard, then CDH must be hard too (but not necessarily the other way around).
If CDH is hard, then DL must be hard (but not necessarily the other way around).


Thus, the hardness of DDH is a stronger assumption (is valid in fewer groups) than the hardness of CDH, which itself is still stronger than the hardness of DL.

As Thomas Pornin mentioned in a comment, there are some elliptic curve groups where DDH is easy, but CDH and DL are (assumed to be) hard, and which are used in pairing based cryptography. This is a good indication (though not yet a proof) that the DL and CDH problems are really strictly harder than DDH.