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).

Multiparty non-interactive key exchange

An $N$-party NIKE lets each of $N$ parties publish one message, after which each party derives, from its own secret, the $N-1$ other published values and any public parameters, a key that all $N$ parties share and that is pseudorandom to an eavesdropper. Two-party NIKE is the case $N=2$; iO and one-way functions give it for any polynomial $N$ fixed in advance, without trusted setup — BZ14.

Three-party NIKE

The case $N=3$ of multiparty NIKE, with each of three parties publishing one message.

Other results

• DDH ⇒ NIKE
• NIKE ⇒ PKE
• No relativizing reduction from OWP to KE — IR89
• No reduction from ROM to KE
• LWE ⇒ PKE
• PKE ⇒ KE

Participates in

Builds on Key exchange

• Authenticated key exchange (AKE) ⇒ KE (via Authenticated key exchange (AKE))
• KE ⇒ Multi-party key exchange
• NIKE ⇒ PKE (via Non-interactive key exchange (NIKE))
• NIKE ⇒ KE (via Non-interactive key exchange (NIKE))

Produces Key exchange

• Authenticated key exchange (AKE) ⇒ KE
• CDH ⇒ NIKE (Diffie–Hellman with a hard-core bit) (via Non-interactive key exchange (NIKE))
• DBDH ⇒ Three-party NIKE (Joux) (via Three-party NIKE)
• DDH ⇒ Non-interactive key exchange (NIKE) (via Non-interactive key exchange (NIKE))
• iO + OWF ⇒ Multiparty NIKE (Boneh–Zhandry) (via Multiparty non-interactive key exchange)
• KE ⇒ Multi-party key exchange (via Multi-party key exchange)
• KEM ⇒ KE
• NIKE ⇒ KE
• OT ⇒ KE
• PKE ⇒ KE
• SSDDH ⇒ KE

Barriers

• No relativizing reduction from KE to PKE
• No relativizing reduction from KE to TDP
• No relativizing reduction from OWP to KE
• No fully-black-box reduction from PPAD hardness + OWF to KE
• No reduction from ROM to KE