Beating the odds on the Diffie-Hellman decision problem

There are a couple 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 where 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 the 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^a and g^b.

To compute g^ab we apparently 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^a and g^b and would want to compute g^ab. This the 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]. But 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 c with 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 which 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, and so 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.

Related posts

• Distribution of quadratic residues
• RSA implementation flaws
• What is an elliptic curve?

[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.