Key exchange

A key exchange (or key agreement) protocol allows two parties communicating over a public, authenticated channel to establish a shared secret key that is computationally indistinguishable from uniformly random to any eavesdropper. Unlike PKE, key exchange does not require a pre-established public key infrastructure.

Syntax

A two-party key exchange protocol is a pair of interactive algorithms $({\mathsf{KE}}_A,{\mathsf{KE}}_B)$ run between parties $A$ and $B$ over a shared transcript. Following execution, both parties output a key $k\in \mathcal{K}$. In the non-interactive setting:

• $\mathsf{KE}=(\mathsf{Gen},\mathsf{Combine})$ where $\mathsf{Gen}(1^{\lambda })\to (\mathsf{pk},\mathsf{sk})$ and each party publishes ${\mathsf{pk}}_A,{\mathsf{pk}}_B$, then computes $k=\mathsf{Combine}({\mathsf{sk}}_A,{\mathsf{pk}}_B)=\mathsf{Combine}({\mathsf{sk}}_B,{\mathsf{pk}}_A)$.

Properties

Correctness

Both parties output the same key $k$ with probability 1 (over their randomness).

Security (indistinguishability from random)

A key exchange protocol is secure if for all efficient adversaries $\mathcal{A}$ that observe the full transcript, the session key $k$ is computationally indistinguishable from a uniformly random key $k^{\prime }\stackrel{\$}{\leftarrow }\mathcal{K}$.

Variations

Non-interactive key exchange (NIKE)

A NIKE allows any two parties to derive the same shared key from each other’s public keys alone, with no interaction at all. Diffie-Hellman over a cyclic group is the canonical example: $k=g^{ab}$ given public keys $g^a$ and $g^b$.

Authenticated key exchange (AKE)

An AKE additionally guarantees that the parties authenticate each other’s identities during the protocol, preventing man-in-the-middle attacks.

Multi-party key exchange

Generalizes two-party KE to $n$ parties. Requires additional rounds or structure (e.g., Burmester-Desmedt, pairing-based constructions).

Other results

• Diffie-Hellman key exchange from DDH — DH76
• KE implies PKE (the session key can be used with a symmetric cipher) — DH76
• No black-box construction of KE from one-way permutations — standard separation (no KE from symmetric primitives)
• Any KE protocol from a random oracle requires $\Omega (n)$ queries; Merkle puzzles achieve $O(n^2)$ security and are optimal — BM09
• KE from LWE: follows as a special case of PKE from LWE — Reg05
• Communication complexity lower bounds for information-theoretic key agreement — HMO+19