# 14.3: Decisional Diffie-Hellman Problem

The Diffie-Hellman protocol is parameterized by the choice of cyclic group ? (and generator g). Transcripts in the protocol consist of (ga,gb), where a and b are chosen uniformly. The key corresponding to such a transcript is gab. The set of possible keys is the cyclic group ?.

Let us substitute the details of the Diffie-Hellman protocol into the KA security libraries. After simplifying, we see that the security of the Diffie-Hellman protocol is equivalent to the following statement:

We have renamed the libraries to ℒdh-real and ℒdh-rand. In ℒdh-real the response to QUERY corresponds to a DHKA transcript (ga,gb) along with the corresponding “correct” key gab. The response in ℒdh-real corresponds to a DHKA transcript along with a completely independent random key gc.

Definition $$\PageIndex{1}$$

The decisional Diffie-Hellman (DDH) assumption in a cyclic group ? is that?dh-real ≋ ℒ?dh-rand (libraries defined above).

Since we have defined the DDH assumption by simply renaming the security definition for DHKA, we immediately have:

Claim 14.6:

The DHKA protocol is a secure KA protocol if and only if the DDH assumption is true for the choice of ? used in the protocol.

For Which Groups does the DDH Assumption Hold?

So far our only example of a cyclic group is ℤp, where p is a prime. Although many textbooks describe DHKA in terms of this cyclic group, it is not a good choice because the DDH assumption is demonstrably falsein ℤp. To see why, we introduce a new concept:

Claim 14.7: Euler Criterion

Note that (−1)x is 1 if x is even and −1 if x is odd. So, while in general it is hard to determine x given gx, Euler’s criterion says that it is possible to determine the parity of x (i.e., whether x is even or odd) given gx.

To see how these observations lead to an attack against the Diffie Hellman protocol, consider the following attack:

Roughly speaking, the adversary returns true whenever C can be written as g raised to an even exponent. When linked to ℒdh-real, C = gab where a and b are chosen uniformly. Hence ab will be even with probability 3/4. When linked to ℒdh-rand, C = gc for an independent random c. So c is even only with probability 1/2. Hence the adversary distinguishes the libraries with advantage 1/4.

Concretely, with this choice of group, the key gab will never be uniformly distributed. See the exercises for a slightly better attack which correlates the key to the transcript.

Definition $$\PageIndex{2}$$