Skip to main content
Engineering LibreTexts

14.2: Diffie-Hellman Key Agreement

  • Page ID
    86468
  • \( \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}}\)

    Key agreement refers to the problem of establishing a private channel using public communication. Suppose Alice & Bob have never spoken before and have no shared secrets. By exchanging public messages (i.e., that can be seen by any external observer), they would like to establish a secret that is known only to the two of them.

    The Diffie-Hellman protocol is such a key-agreement protocol, and it was the first published instance of public-key cryptography:

    Construction \(14.3\) (Diffie-Hellman)

    Both parties agree (publicly) on a cyclic group \(\mathbb{G}\) with generator g. Let \(n=|\mathbb{G}|\). All exponen tiations are with respect to the group operation in \(\mathbb{G}\).

    1. Alice chooses \(a \leftarrow \mathbb{Z}_{n}\). She sends \(A=g^{a}\) to Bob.
    2. Bob chooses \(b \leftarrow \mathbb{Z}_{n}\). He sends \(B=g^{b}\) to Alice.
    3. Bob locally outputs \(K:=A^{b}\). Alice locally outputs \(K:=B^{a}\).
    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    By substituting and applying standard rules of exponents, we see that both parties output a common value, namely \(K=g^{a b} \in \mathbb{G}\).

    Defining Security for Key Agreement

    Executing a key agreement protocol leaves two artifacts behind. First, we have the collection of messages that are exchanged between the two parties. We call this collection a transcript. We envision two parties executing a key agreement protocol in the presence of an eavesdropper, and hence we imagine that the transcript is public. Second, we have the key that is output by the parties, which is private.

    To define security of key agreement, we would like to require that the transcript leaks no (useful) information to the eavesdropper about the key. There are a few ways to approach the definition:

    • We could require that it is hard to compute the key given the transcript. However, this turns out to be a rather weak definition. For example, it does not rule out the possibility that an eavesdropper could guess the first half of the bits of the key.
    • We could require that the key is pseudorandom given the transcript. This is a better definition, and the one we use. To formalize this idea, we define two libraries. In both libraries the adversary / calling program can obtain the transcript of an execution of the key agreement protocol. In one library the adversary obtains the key that resulted from the protocol execution, while in the other library the adversary obtains a totally unrelated key (chosen uniformly from the set \(\Sigma\). \(K\) of possible keys).
    Definition \(14.4\)

    Let \(\Sigma\) be a key-agreement protocol. We write \(\sum\). \(\mathcal{K}\) for the keyspace of the protocol (i.e., the (KA security) set of possible keys it produces). We write \((t, K) \leftarrow\) EXECPROT( \(\Sigma\) ) to denote the process of executing the protocol between two honest parties, where t denotes the resulting transcript, and \(K\) is resulting key. Note that this process is randomized, and that \(K\) is presumably correlated to \(t\).

    We say that \(\Sigma\) is secure if \(\mathcal{L}_{\mathrm{ka}-\mathrm{real}}^{\Sigma} \approx \mathcal{L}_{\mathrm{ka}-\mathrm{rand}}^{\Sigma}\), where:

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

    This page titled 14.2: Diffie-Hellman Key Agreement 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?