Key encapsulation mechanism

A key encapsulation mechanism (KEM) is a public-key primitive that allows a sender to encapsulate a fresh uniformly random symmetric key $k$ into a ciphertext $c$ using a public key $\mathsf{pk}$, such that only the holder of the secret key $\mathsf{sk}$ can recover $k$ by decapsulation. Combined with a symmetric-key data encapsulation mechanism (DEM, i.e., SKE), KEMs give the KEM-DEM paradigm for hybrid encryption — the standard approach to asymmetric encryption in practice.

Syntax

A KEM is a tuple of efficient algorithms $(\mathsf{KeyGen},\mathsf{Encap},\mathsf{Decap})$ with key space $\mathcal{K}$:

• $\mathsf{KeyGen}(1^{\lambda })\to (\mathsf{pk},\mathsf{sk}),$ is a randomized algorithm that generates a public/secret key pair.
• $\mathsf{Encap}(\mathsf{pk})\to (c,k),$ is a randomized algorithm that takes a public key and outputs a ciphertext $c$ and a symmetric key $k\in \mathcal{K}$.
• $\mathsf{Decap}(\mathsf{sk},c)\to k,$ is a deterministic algorithm that recovers the symmetric key from the ciphertext.

Properties

Correctness

For all $\lambda \in \mathbb{N}$ and $(\mathsf{pk},\mathsf{sk})\leftarrow \mathsf{KeyGen}(1^{\lambda })$: $\mathrm{Pr}[(c,k)\leftarrow \mathsf{Encap}(\mathsf{pk}):\mathsf{Decap}(\mathsf{sk},c)=k]=1.$

IND-CCA security

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{cca}}_{\mathrm{KEM},\calA}(\secpar)$}
\begin{algorithmic}
\State $(\pk, \sk) \gets \KeyGen(1^\secpar)$
\State $(c^*, k_0) \gets \Encap(\pk)$
\State $k_1 \getsr \calK$
\State $b \getsr \bits$
\State $b' \gets \calA^{\Decap(\sk, \cdot)}(\pk, c^*, k_b)$
\Comment{$\calA$ may not query $\Decap$ on $c^*$}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A KEM is IND-CCA secure if for all efficient $\mathcal{A}$,

${\mathbf{Adv}}_{\mathrm{KEM},\mathcal{A}}^{\mathrm{cca}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathrm{KEM},\mathcal{A}}^{\mathrm{cca}}(\lambda )=1\right]-1\right|$

is negligible. The adversary cannot query the decapsulation oracle on the challenge ciphertext $c^{\ast }$, since that would trivially reveal $b$.

KEM-DEM hybrid encryption

Given an IND-CCA KEM and a one-time IND-CCA SKE (DEM), the following construction achieves IND-CCA PKE:

• $\mathsf{Enc}(\mathsf{pk},m)$: run $(c_1,k)\leftarrow \mathsf{Encap}(\mathsf{pk})$; run $c_2\leftarrow \mathsf{SKE}.\mathsf{Enc}(k,m)$; output $(c_1,c_2)$.
• $\mathsf{Dec}(\mathsf{sk},(c_1,c_2))$: run $k\leftarrow \mathsf{Decap}(\mathsf{sk},c_1)$; output $\mathsf{SKE}.\mathsf{Dec}(k,c_2)$.

This achieves IND-CCA security as long as the KEM is IND-CCA secure and the DEM is one-time IND-CCA secure — CS03. An IND-CPA DEM does not suffice: with CTR mode as DEM, $\mathcal{A}$ flips a bit in the masked part of $c_2^{\ast }$, queries $\mathsf{Dec}$ on $(c_1^{\ast },c_2^{\prime })$ for the result $c_2^{\prime }\ne c_2^{\ast }$, and receives $m_b$ with that bit flipped; HHK10 study which KEM/DEM notion pairs suffice.

Variations

IND-CPA KEM

A weaker KEM where the adversary has no decapsulation oracle. Sufficient for passive adversaries.

Lattice-based KEM (Kyber / ML-KEM)

Kyber is an IND-CCA KEM based on Module LWE (module rank 2, 3, 4 over ${\mathbb{Z}}_q[X]/(X^{256}+1)$ for Kyber-512, -768, -1024) — BDK+18. Standardized by NIST as ML-KEM (FIPS 203). Uses the Fujisaki-Okamoto transform to achieve IND-CCA security from an IND-CPA base scheme.

RSA-KEM / RSAES-OAEP

RSA-KEM samples $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_N$, sends $c=r^e\mathrm{mod}N$ with no padding, and derives $k=\mathsf{H}(r)$; it is IND-CCA secure under RSA in the random oracle model — Sho01b. RSAES-OAEP is a PKE, not a KEM; it is IND-CCA secure under RSA in the random oracle model — FOPS01.

Other results

• PKE ⇒ KEM
• IND-CPA PKE ⇒ IND-CCA KEM (Fujisaki–Okamoto)
• KEM + SKE ⇒ PKE
• The KEM-DEM paradigm is standardized as HPKE (RFC 9180) — BBLW22
• KEM ⇒ KE

Participates in

Builds on Key encapsulation mechanism

• IND-CCA security ⇒ IND-CPA KEM (via IND-CCA security)
• KEM + SKE ⇒ PKE
• KEM ⇒ KE

Produces Key encapsulation mechanism

• IND-CCA security ⇒ IND-CPA KEM (via IND-CPA KEM)
• IND-CPA PKE ⇒ IND-CCA KEM (Fujisaki–Okamoto) (via IND-CCA security)
• Module LWE ⇒ IND-CCA KEM (via IND-CCA security)
• NTRU ⇒ IND-CCA KEM (via IND-CCA security)
• PKE ⇒ KEM
• RSA ⇒ IND-CCA KEM (via IND-CCA security)