The Fujisaki-Okamoto transform

Syntax of Encryption Schemes

Recall the syntax of asymmetric and symmetric encryption schemes, basically following [2],[3]

Asymmetric Encryption

An asymmetric (aka public-key) encryption scheme is given by a triple of algorithms, $\Pi=(\mathcal{K}, \mathcal{E}, \mathcal{D})$, where for every sufficiently large $k \in \mathbb{N}$,

• $\mathcal{K}$, the key-generation algorithm, is a probabilistic polynomial-time (in $k$ ) algorithm which on input $1^k$ outputs a pair of strings, $(p k, s k)$, called the public and secret keys, respectively. This experiment is written as $(p k, s k) \leftarrow \mathcal{K}\left(1^k\right)$.
• $\mathcal{E}$, the encryption algorithm, is a probabilistic polynomial-time (in $k$ ) algorithm that takes public key $p k$ and message $x \in$ MSP, draws coins $r$ uniformly from coin space COIN, and produces ciphertext $y:=\mathcal{E}_{p k}(x ; r)$. This experiment is written as $y \leftarrow \mathcal{E}_{p k}(x)$. The message and coin spaces, MSP and COIN, are uniquely determined by $p k$.
• $\mathcal{D}$, the decryption algorithm, is a deterministic polynomial-time (in $k$ ) algorithm that takes secret key $s k$ and ciphertext $y \in\{0,1\}^*$, and returns message $x:=\mathcal{D}_{s k}(y)$.

We require that an asymmetric encryption scheme should satisfy the following correctness condition: For every sufficiently large $k \in \mathbb{N}$, every ( $p k, s k$ ) generated by $\mathcal{K}\left(1^k\right)$ and every $x \in$ MSP, we always have $\mathcal{D}_{s k}\left(\mathcal{E}_{p k}(x)\right)=x$.

Symmetric Encryption

A symmetric (aka private-key) encryption scheme is given by a pair of algorithms, $\Pi=$ $(\mathcal{E}, \mathcal{D})$, where for every sufficiently large $k \in \mathbb{N}$,

• $\mathcal{E}$, the encryption algorithm, is a probabilistic polynomial-time (in $k$ ) algorithm that takes secret key $a \in \operatorname{KSP}$ and message $x \in$ MSP, draws coins $r$ uniformly from coin space COIN, and produces ciphertext $y:=\mathcal{E}_a(x ; r)$. This experiment is written as $y \leftarrow \mathcal{E}_a(x)$. The key, message, and coin spaces, KSP, MSP and COIN, are uniquely determined by $k$.
• $\mathcal{D}$, the decryption algorithm, is a deterministic polynomial-time (in $k$ ) algorithm that takes secret key $a \in \operatorname{KSP}$ and ciphertext $y \in\{0,1\}^*$, and outputs message $x:=$ $\mathcal{D}_a(y)$.

We require that a symmetric encryption scheme should satisfy the correctness condition: For every sufficiently large $k \in \mathbb{N}$, every $a \in \operatorname{KSP}$ and every $x \in$ MSP, we always have $\mathcal{D}_a\left(\mathcal{E}_a(x)\right)=x$

Fujisaki-Okamoto Transform

Let $\Pi^{\text {asy }}=\left(\mathcal{K}^{\text {asy }}, \mathcal{E}^{\text {asy }}, \mathcal{D}^{\text {asy }}\right)$ and $\Pi^{\text {sy }}=\left(\mathcal{E}^{\text {sy }}, \mathcal{D}^{\text {sy }}\right)$ be asymmetric and symmetric encryption schemes, respectively, $(p k, s k)$ be a pair of public and secret keys generated by $\mathcal{K}^{\text {asy }}\left(1^k\right)$, MSP $^{\text {asy }}$ and COIN ${ }^{\text {asy }}$ be the message and coin spaces of $\Pi^{\text {asy }}$ with respect to $p k$, and $\mathrm{KSP}^{\text {sy }}$ and $\mathrm{MSP}^{\text {sy }}$ be the key and message spaces of $\Pi^{\text {sy }}$ (with respect $k$ ). We define two hash functions.

$$G:\{0,1\}^* \rightarrow \operatorname{KSP}^{\text {sy }} \quad \text { and } \quad H:\{0,1\}^* \times\{0,1\}^* \rightarrow \operatorname{COIN}^{\text {asy }}$$

Given $\Pi^{\text {asy }}$ and $\Pi^{\text {sy }}$, we construct a hybrid encryption scheme $\Pi^{\text {hy }}=\left(\mathcal{K}^{\text {hy }}, \mathcal{E}^{\text {hy }}, \mathcal{D}^{\text {hy }}\right)$. We write COIN ${ }^{\text {hy }}$ and MSP ${ }^{\text {hy }}$ to denote the coin and message spaces of $\Pi^{\mathrm{hy}}$. This hybrid encryption scheme is specified as follows:

Key-generation: $\mathcal{K}^{\text {hy }}$, the key-generation algorithm, takes $1^k$ as input. It selects $(p k, s k) \leftarrow \mathcal{K}^{\text {asy }}\left(1^k\right)$ and returns $(p k, s k)$ as the output of $\mathcal{K}^{\text {hy }}\left(1^k\right)$. We write the experiment as $(p k, s k) \leftarrow \mathcal{K}^{\text {hy }}\left(1^k\right)$.

Encryption: $\mathcal{E}^{\text {hy }}$, the encryption algorithm, takes public key $p k$ and message $m \in$ $\mathrm{MSP}^{\text {hy }}\left(:=\mathrm{MSP}^{\mathrm{sy}}\right)$ as input. It selects $\sigma \leftarrow_R \operatorname{COIN}^{\text {hy }}\left(:=\mathrm{MSP}^{\text {asy }}\right)$, computes $c \leftarrow$ $\mathcal{E}_a^{\text {sy }}(m)$, where $a:=G(\sigma)$, and computes $e:=\mathcal{E}_{p k}^{\text {asy }}(\sigma ; h)$ where $h:=H(\sigma, c)$. It finally outputs $e | c$ as $\mathcal{E}_{p k}^{\text {hy }}(m ; \sigma)$. As described above, the coin and message spaces of $\Pi^{\text {hy }}$ with respect to $p k$ are defined as COIN ${ }^{\text {hy }}:=$ MSP $^{\text {asy }}$ and MSP ${ }^{\text {hy }}:=\mathrm{MSP}^{\text {sy }}$.

Decryption $\mathcal{D}^{\text {hy }}$, the decryption algorithm, takes secret key $s k$ and ciphertext $e | c \in$ $\{0,1\}^*$ as input. It runs as follows.

1. Parse $e | c$ appropriately as $(e, c)$; otherwise, output $\varepsilon$ and halt.
2. Compute $\hat{\sigma}:=\mathcal{D}_{s k}^{\text {asy }}(e)$.
3. If $\hat{\sigma} \in \operatorname{COIN}^{\mathrm{hy}}$,
   (a) then compute $\hat{a}:=G(\hat{\sigma})$.
   (b) otherwise, set $\mathcal{D}_{s k}^{\text {hy }}(e | c):=\varepsilon$ and go to Step 6.
4. Set $\hat{h}:=H(\hat{\sigma}, c)$.
5. If $e=\mathcal{E}_{p k}^{\text {asy }}(\hat{\sigma} ; \hat{h})$,
   (a) then set $\mathcal{D}_{s k}^{\mathrm{hy}}(e | c):=\mathcal{D}_{\hat{a}}^{\mathrm{sy}}(c)$.
   (b) otherwise, $\mathcal{D}_{s k}^{\mathrm{hy}}(e | c):=\varepsilon$.
6. Return $\mathcal{D}_{s k}^{\text {hy }}(e | c)$.

Well-Spread Encryption

Let $|X|$ be the infinity norm of probability space $X$ on a finite set $S$, i.e., $|X|=$ $\max _{a \in \mathcal{S}}\{\operatorname{Pr}[x \leftarrow X: x=a]\}$. The min-entropy of $X$ is $-\log |X|$.

Definition 5.2 ( $\gamma$-spread). Let $\Pi=(\mathcal{K}, \mathcal{E}, \mathcal{D})$ be an asymmetric encryption scheme. For $p k$ and $x \in$ MSP, define the min-entropy of $\mathcal{E}_{p k}(x)$ by $\gamma(p k, x)=-\log \left|\mathcal{E}_{p k}(x)\right|$, where

$$\left\|\mathcal{E}_{p k}(x)\right\|=\max _{y \in\{0,1\}^*} \operatorname{Pr}\left[h \leftarrow_R \text { COIN : } y=\mathcal{E}_{p k}(x, h)\right]$$

We say that $\Pi$ is $\gamma$-spread (for $k \in \mathbb{N}$ ), if, for every $p k$ generated by $\mathcal{K}\left(1^k\right)$ and $x \in \operatorname{MSP}$, $\gamma(p k, x) \geq \gamma$. In particular, we say that $\Pi$ is well-spread in $k$ if $\gamma=\omega(\log (k))$.

Intuition： $\gamma(p k, x)$ measures the uncertainty of the ciphertext(min-entropy) generated by $\mathcal{E}_{p k}$ on input $x$. The probability of the most possible ciphertext for all possible $x$ is at most $2^{-\gamma}$, which means any plaintext in the message space has at least $2^{\omega(\log k)}$ possible ciphertexts(called $\omega(\log k)$-spread).(other ciphertext for a fixed plaintext is less than $2^{-\gamma}$)

References

[1] Secure Integration of Asymmetric and Symmetric Encryption Schemes

[2] M. Bellare, A. Desai, D. Pointcheval, P. Rogaway, Relations among notions of security for public-key encryption schemes, in Advances in Cryptology—CRYPTO’98, ed. by H. Krawczyk. Lecture Notes in Computer Science, vol. 1462 (Springer, Berlin, 1998), pp. 26–45

[3] S. Goldwasser, S. Micali, Probabilistic encryption. J. Comput. Syst. Sci. 28, 270–299 (1984)