What is the relation between Discrete Log, Computational Diffie-Hellman and Decisional Diffie-Hellman?

Question

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?

Answer 1

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.

Answer 2

It means that if you have an oracle access to CDH, then you can solve DDH, but we do not know if there exists a reduction the other way round.

Technically, suppose $\mathsf{CDH}$ is an oracle that finds $g^{xy}$, given $(g^x,g^y)$, then for a DDH instance, say $(a,b,c)$, you can feed $\mathsf{CDH}$ with $(a,b)$ and output $1$ if output of $\mathsf{CDH}$ equals $c$, else output $0$. There is no such reduction known that solves CDH given an analogous oracle $\mathsf{DDH}$.

I found a discussion on Hard problem Relationship between CDH and Discrete Log in mathematics' stack-exchange with almost similar type of question and the answer is more comprehensive. You might find the reference therein more useful.

Answer 3

In addition to Jalaj's correct answer, I also want to dispute one of your statements:

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

Actually, that's not the case. Now, if you can solve the DL problem, the CDH problem is easy (and so the CDH problem is no harder than the DL problem). However, there's no known reduction the other way; given an oracle that solves the CDH problem, there's no known way to use it to solve the DL problem. Hence, the CDH assumption is a stronger assumption than the DL assumption.

Now, in practice, with the multiplicative group $Z^*/p$, the only known way to attack the CDH problem is to attempt to rederive one of the secret exponents (by solving the DL problem); however, there may be some other way to attack the CDH problem that no one has happened to think of.

Answer 4

This paper describes theoretical boosters that help to achieve a reduction of the Discrete Log problem to the Computational Diffie-Hellman problem.

Since the "holy grail" of a polynomial time reduction from Discrete Logarithm to Diffie-Hellman seems a long way off, it is interesting to investigate what types of additional features might bridge this gap. There are several possible ways to relax the problem: one can ask for only a subexponential-time, rather than polynomial-time reduction; one can give the discrete-logarithm solver access to powerful oracles, such as a one-prime-not-p or any-prime-but-p discrete-logarithm solver, an oracle that answers yes-or-no questions, or an oracle that factors integers; and one can assume certain number-theoretic conjectures, in other words, one can be satisfied with a heuristic complexity analysis.

The references trace other significant efforts.