IND-CPA PKE ⇒ IND-CCA KEM (Fujisaki–Okamoto)

Fully-black-box reduction · random oracle model · FO99, HHK17 · security loss: additive in the random-oracle model from IND-CPA: a constant multiple of the IND-CPA advantage plus terms of order $q\delta$ and $q/|\mathcal{M}|$ for $q$ random-oracle queries, and $q_D{2}^{-\gamma }$ for $q_D$ decapsulation queries with explicit rejection; from one-wayness, a factor $O(q)$

Statement

Let $\mathsf{PKE}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ be a PKE scheme with message space $\mathcal{M}$ that is $\delta$-correct for negligible $\delta$ (the decryption-failure probability, maximized over $m\in \mathcal{M}$ and then averaged over $(\mathsf{pk},\mathsf{sk})\leftarrow \mathsf{KeyGen}(1^{\lambda })$, is at most $\delta$), and let $G$ and $H$ be random oracles. The Fujisaki–Okamoto KEM encapsulates by sampling $m\stackrel{\$}{\leftarrow }\mathcal{M}$, encrypting it as $c=\mathsf{Enc}(\mathsf{pk},m;G(m))$ and outputting the key $H(m,c)$; decapsulation decrypts $c$ to $m^{\prime }$, re-encrypts under $G(m^{\prime })$, and returns $H(m^{\prime },c)$ if the result equals $c$, and otherwise rejects, explicitly with $\perp$ or implicitly with $H(s,c)$ for a uniform seed $s\in \mathcal{M}$ kept in the secret key. If $\mathsf{PKE}$ is IND-CPA-secure, or merely one-way, the KEM is IND-CCA-secure in the random-oracle model; explicit rejection additionally needs $\mathsf{PKE}$ to have $\gamma$-spread ciphertexts. FO99 introduced the transform, for hybrid encryption with a symmetric scheme; HHK17 decompose it into a derandomization step and a key-derivation step, covering explicit and implicit rejection, with concrete bounds for a $\delta$-correct base scheme.

Sketch

Derandomizing encryption with $G(m)$ makes ciphertexts checkable by re-encryption, so the reduction answers decapsulation queries by searching the adversary’s $G$ and $H$ queries for a message that re-encrypts to the queried ciphertext. An adversary that never queries $H$ at the challenge message $m^{\ast }$ has no information on $H(m^{\ast },c^{\ast })$; from one that does, the reduction reads off $m^{\ast }$, inverting the base encryption.

Notes

• KEM-specific versions of the transform, proved IND-CCA in the random-oracle model from a one-way PKE — Den03.