Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

4 Answers

up vote 11 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.

share|improve this answer
3  
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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. –  Jalaj Dec 16 '11 at 21:11
    
@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. –  poncho Jan 24 at 16:51
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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