Skip to main content
Engineering LibreTexts

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 (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:

    Figure14-5.jpg

    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

    Figure14-6.jpg

    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:

    Figure14-7.jpg

    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.

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