# 14.3: Decisional Diffie-Hellman Problem

- Page ID
- 7406

The Diffie-Hellman protocol is parameterized by the choice of cyclic group ? (and generator *g*). Transcripts in the protocol consist of (*g ^{a},g^{b}*), where

*a*and

*b*are chosen uniformly. The key corresponding to such a transcript is

*g*. The set of possible keys is the cyclic group ?.

^{ab}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 (*g ^{a},g^{b}*) along with the corresponding “correct” key

*g*. The response in ℒ

^{ab}_{dh-real}corresponds to a DHKA transcript along with a completely independent random key

*g*.

^{c}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 **false*in ℤ^{∗}_{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

*g*, Euler’s criterion says that it is possible to determine the

^{x}*parity of x*(

*i.e.*, whether

*x*is even or odd) given

*g*.

^{x}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* = *g*^{ab} where *a *and *b* are chosen uniformly. Hence *ab* will be even with probability 3/4. When linked to ℒ_{dh-rand}, *C* = *g ^{c}* 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 *g ^{ab}* will never be uniformly distributed. See the exercises for a slightly better attack which correlates the key to the transcript.

**Quadratic Residues.**

Several better choices of cyclic groups have been proposed in the literature. Arguably the simplest one is based on the following definition:

Definition \(\PageIndex{2}\)

*A number X* ∈ ℤ^{∗}_{n}*is a quadratic residue modulo n if there exists some integer Y such that Y^{2}* ≡

*.*

_{n}X*That is, if X can be obtained by squaring a number mod n. Let*ℚℝ

^{∗}

*⊆ ℤ*

_{n}^{∗}

_{n}denote the set of quadratic residues mod n.For our purposes it is enough to know that, when *p* is prime, ℚℝ^{∗}_{p} is a cyclic group with (*p* − 1)/2 elements (see the exercises). When both *p* and (*p* − 1)/2 are prime, we call *p* a **safe prime** (and call (*p* − 1)/2 a *Sophie Germain prime*). To the best of our knowledge the DDH assumption is true in ℚℝ^{∗}* _{p}* when

*p*is a safe prime.