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?

up vote 22 down vote accepted

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 if 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 they with 50% probability 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 half-group 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 other 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 oher way around).

Thus, the hardness of DDH is a stronger assumption (is valid in less 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.

  • 6
    Just for completion, pairing-based cryptography is about using specially crafted elliptic curves where DL and CDH are assumed difficult, but DDH is easy. So we have some quite plausible reasons to believe that CDH is strictly harder than DDH (or so we fervently hope, at least). – Thomas Pornin Dec 25 '11 at 23:27

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.

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.

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.