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?


4 Answers 4


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.

  • 7
    $\begingroup$ 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). $\endgroup$ Dec 25, 2011 at 23:27
  • $\begingroup$ @Thomas Pornin both the "plausible reasons" and the "fervent hope" to which you refer concern only those particular (i.e., pairing-equipped) groups, yes? In other words, it may perfectly well still be the case that CDH and DDH are equivalent in more generic (e.g., standard elliptic curve) groups. $\endgroup$
    – BD107
    Jan 12, 2020 at 23:52
  • $\begingroup$ @BD107 there is no such thing as a "more generic group". If they are equivalent "in a generic group", there is a generic reduction from one to the other (i.e. which doesn't use special knowledge of the group structure). If that exists, it works in all groups. As we suppose this doesn't exist (see Thomas' examples), they are not generically equivalent. They might be equivalent in some special groups, though. $\endgroup$ Jan 15, 2020 at 23:14
  • $\begingroup$ I see. So in other words, it remains possible that CDH and DDH are both easy in all groups, but not that they're both hard in all groups (as the pairing case shows). Is that correct? $\endgroup$
    – BD107
    Jan 16, 2020 at 21:01

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.

  • $\begingroup$ Actually, Maurer and Wolf proved in The Relationship Between Breaking the Diffie--Hellman Protocol and Computing Discrete Logarithms the equivalence of the two in the uniform sense based on some assumptions on the order of the group. $\endgroup$
    – Jalaj
    Dec 16, 2011 at 21:11
  • $\begingroup$ @Jalaj: if you go through the summary, it applies only to groups "where all the multiple prime factors of |G| are polynomial in log|G|"; this is not true in general for well-chosen $p$ values. $\endgroup$
    – poncho
    Jan 24, 2014 at 16:51

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 agree to our terms of service, privacy policy and cookie policy

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