§14 Key-Exchange Protocols and Diffie-Hellman Key-Exchange

Key-Exchange Protocols

Key-Exchange experiment $\mathrm{KE}_{\mathscr{A}, \Pi}^{\mathrm{eav}}(n)$

• Fix a Key-Exchange protocol $\Pi$ and an attacker (passive eavesdropper) $\mathscr{A}$. Define the experiment $\mathrm{KE}_{\mathscr{A}, \Pi}^{\mathrm{eav}}(n)$:
  1. Two parties holding $1^n$ execute protocol $\Pi$. This results in a transcript $\texttt{trans}$ containing all the messages sent by the parties, and a key $k \in \{0,1\}^n$ output by each of the parties.
  2. A uniform bit $b \in \{0,1\}$ is chosen. If $b = 0$, set $k' := k$. If $b = 1$, choose $k' \leftarrow \{0,1\}^n$ uniformly at random.
  3. Attacker $\mathscr{A}$ is given $\texttt{trans}$ and $k'$. $\mathscr A$ then outputs a bit $b'$.
  4. $\mathscr A$ succeeds and the experiment evaluates to $1$ if and only if $b' = b$.

Key-Exchange Security

• Definition. The Key-Exchange Protocol $\Pi$ is secure in the presence of an eavesdropper, if for all probabilistic, polynomial-time adversaries $\mathscr A$, there is a negligible function $\epsilon(n)$ such that

  $$\Pr[\mathrm{KE}_{\mathscr{A}, \Pi}^{\mathrm{eav}}(n) = 1] \le \frac{1}{2} + \epsilon(n)$$

Diffie-Hellman Key-Exchange Protocol

• The Diffie-Hellman key-exchange protocol for the common input consisting of security parameter $1^n$ is formally described as follows:
  1. Alice runs $\mathscr{G}(1^n)$ to obtain $(\mathbb{G}, q, g)$.
  2. Alice chooses a uniform $x \in \mathbb{Z}_q$, and computes $h_A := g^x$.
  3. Alice sends $(\mathbb{G}, q, g, h_A)$ to Bob.
  4. Bob receives $(\mathbb{G}, q, g, h_A)$. Bob chooses uniform $y \in \mathbb{Z}_q$, and computes $h_B := g^y$. Bob sends $h_B$ to Alice, and outputs the key $k_B := h^y_A$.
  5. Alice receives $h_B$ and outputs the key $k_A := h^x_B$.

Diffie-Hellman Key-Exchange Protocol: Security

• Theorem. If the Decisional Diffie-Hellman problem is hard relative to $\mathscr G$, then the Diffie-Hellman key-exchange protocol $\Pi$ is secure in the presence of an eavesdropper (with respect to $\widehat{\mathrm{KE}}_{\mathscr{A}, \Pi}^{\mathrm{eav}}$ ).

— Mar 24, 2023

§14 Key-Exchange Protocols and Diffie-Hellman Key-Exchange by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.