Skip to main content
Engineering LibreTexts

14.3: Decisional Diffie-Hellman Problem

  • Page ID
    86469
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    The Diffie Hellman protocol is parameterized by the choice of cyclic group \(\mathbb{G}\) (and generator \(g)\). Transcripts in the protocol consist of \(\left(g^{a}, g^{b}\right)\), where \(a\) and \(b\) are chosen uniformly. The key corresponding to such a transcript is \(g^{a b}\). The set of possible keys is the cyclic group \(\mathbb{G}\).

    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:

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    We have renamed the libraries to \(\mathcal{L}_{\text {dh-real }}\) and \(\mathcal{L}_{\text {dh-rand }}\). In \(\mathcal{L}_{\text {dh-real }}\) the response to QUERY corresponds to a DHKA transcript \(\left(g^{a}, g^{b}\right)\) along with the corresponding "correct" key \(g^{a b}\). The response in \(\mathcal{L}_{\text {dh-rand }}\) corresponds to a DHKA transcript along with a completely independent random key \(g^{c}\).

    Definition \(14.5\) (DDH)

    The decisional Diffie-Hellman (DDH) assumption in a cyclic group \(\mathbb{G}\) is that \(\mathcal{L}_{\mathrm{dh}-\mathrm{G}}^{\mathbb{G}} \approx\) \((\mathrm{DDH}) \quad \mathcal{L}_{\mathrm{dh} \text {-rand }}^{\mathbb{G}}\) (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 \(\mathbb{G}\) used in the protocol.

    For Which Groups does the DDH Assumption Hold?

    So far our only example of a cyclic group is \(\mathbb{Z}_{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 \(\mathrm{DDH}\) assumption is demonstrably false in \(\mathbb{Z}_{p}^{*}\). To see why, we introduce a new concept:

    Claim \(14.7\) (Euler creterion)

    If \(p\) is a prime and \(X=g^{x} \in \mathbb{Z}_{p}^{*}\), then \(X^{\frac{p-1}{2}} \equiv_{p}(-1)^{x}\).

    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^{x}\), Euler’s criterion says that it is possible to determine the 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:

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    Roughly speaking, the adversary returns true whenever \(C\) can be written as \(g\) raised to an even exponent. When linked to \(\mathcal{L}_{\text {dh-real }}, C=g^{a b}\) where \(a\) and \(b\) are chosen uniformly. Hence \(a b\) will be even with probability \(3 / 4\). When linked to \(\mathcal{L}_{\mathrm{dh}-\mathrm{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^{a b}\) 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 \(14.8\)

    A number \(X \in \mathbb{Z}_{n}^{*}\) is a quadratic residue modulo \(n\) if there exists some integer \(Y\) such that \(Y^{2} \equiv_{n} X\). That is, if \(X\) can be obtained by squaring a number modn. Let \(\mathbb{Q R}_{n}^{*} \subseteq \mathbb{Z}_{n}^{*}\) denote the set of quadratic residues \(\bmod n\).

    For our purposes it is enough to know that, when \(p\) is prime, \(\mathbb{Q} \mathbb{R}_{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 \(\mathrm{DDH}\) assumption is true in \(\mathbb{Q R}_{p}^{*}\) when \(p\) is a safe prime.


    This page titled 14.3: Decisional Diffie-Hellman Problem is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek (Open Oregon State) .

    • Was this article helpful?