Diffie-Hellman Key Exchange

Diffie-Hellman (DH) is a cryptographic protocol that allows two parties to establish a shared secret over an insecure channel. It relies on the computational difficulty of the Discrete Logarithm Problem (DLP) in a cyclic group.

Protocol Mechanism

Given a public cyclic group $⟨g⟩=G$ where the DLP is hard:

1. Alice samples a private integer $a$ and sends public value $A=g^a$.
2. Bob samples a private integer $b$ and sends public value $B=g^b$.
3. Key derivation: Both parties compute the shared secret $K=g^{ab}$.
   • Alice computes: $K=B^a=(g^b{)}^a=g^{ab}$
   • Bob computes: $K=A^b=(g^a{)}^b=g^{ab}$

Security Properties

• Hardness Assumption: An attacker observing $g^a$ and $g^a$ cannot compute $g^{ab}$ without solving the Computational Diffie-Hellman (CDH) problem, which is related to the Discrete Logarithm Problem.
• Perfect Forward Secrecy (PFS): If the private exponents $a$ and $b$ are ephemeral (generated on the fly for each session and then discarded), a compromise of long-term keys in the future will not compromise past session keys.

Critical Limitation

• Lack of Authentication: Basic DH is anonymous. It is vulnerable to Man-in-the-Middle (MITM) attacks because neither party verifies the identity of the other.
• Mitigation: The exchange must be authenticated (e.g., using Digital Signature Schemes or public key infrastructure) to prevent an attacker from intercepting and replacing values.

---

Relevant Note(s):