Decision Diffie-Hellman DDH and CDH

There are a couple of variations on the Diffie-Hellman problem in cryptography: the computation problem (CDH) and the decision problem (DDH). This post will explain both and give an example of how the former is hard and the latter easy.

The Diffie-Hellman Problems

The Diffie-Hellman problems are formulated for an Abelian group. The main group we have in mind is the multiplicative group of non-zero integers modulo a large prime p. But we start out more generally because Diffie-Hellman problems are harder over some groups than others, as we will see below.

Let g be the generator of a group. When we think of the group operation written as multiplication, this means that every element of the group is a power of g.

Computational Diffie-Hellman problem

Let a and b be two integers. Given g^a and g^b, the CDH problem is to compute g^ab. Note that the exponent is ab and not a+b. The latter would be easy: just multiply g^aand g^b.

To compute g^ab we need to know either a or b, which we are not given. Solving for either exponent is the discrete logarithm problem, which is impractical for some groups.

It’s conceivable that there is a way to solve CDH without solving the discrete logarithm problem, but, at this time, the most efficient attacks on CDH compute discrete logs.

Diffie-Hellman key exchange

Diffie-Hellman key exchange depends on the assumption that CDH is a hard problem.

Suppose Alice and Bob both agree on a generator, g, and select private keys a and b respectively. Alice sends Bob g^a and Bob sends Alice g^b. This doesn’t reveal their private keys because the discrete logarithm problem is (believed to be) hard. Now, both compute g^ab and use it as their shared key. Alice computes g^ab by raising g^b to the power a, and Bob computes g^ab by raising g^a to the power b.

If someone intercepted the exchange between Alice and Bob, they would possess g^aand g^b and would want to compute g^ab. This is the CDH.

When working over the integers modulo a large prime p, CDH is hard if p-1 has a large factor, such as when p – 1 = 2q for a prime q. If p-1 has only small factors, i.e. if p-1 is “smooth”, then the discrete logarithm problem is tractable via the Silver-Pohlig-Hellman algorithm [1]. If p is large and p-1 has a large prime factor, CDH is hard as far as we currently know.

Decision Diffie-Hellman Problem

The DDH problem also starts with knowledge of g^a and g^b. But instead of asking to compute g^ab it asks whether one can distinguish g^ab from g^c for a randomly chosen cwith probability better than 0.5.

Clearly, DDH is weaker than CDH because if we can solve CDH, we know the answer to the DDH question with certainty. Still, the DDH problem is believed to be hard over some groups, such as certain elliptic curves, but not over other groups, as illustrated below.

DDH for Multiplicative Group Mod p

Suppose we’re working in the multiplicative group of non-zero integers modulo a prime p. Using Legendre symbols, which are practical to compute even for very large numbers, you can determine whether g^a is a square mod p, which happens if and only if a is even. So, by computing the Legendre symbol for g^a mod p, we know the parity of a. Similarly, we can find the parity of b. As a result, we know the parity of ab. If ab is odd but g^c is a square mod p, we know that the answer to the DDH problem is no. Similarly, if ab is even but g^c is not a square mod p, we also know that the answer to the DDH problem is no.

Since half the positive integers mod p are squares, we can answer the DDH problem with certainty half the time by the parity argument above. If our parity argument is inconclusive, we have to guess. So, overall, we can answer he DDH problem correctly with probability 0.75.

[1] As is common when you have a lot of names attached to a theorem, there were multiple discoveries. Silver discovered the algorithm first, but Pohlig and Hellman discovered it independently and published first.