12 Fujisaki-Okamoto transform

12.1 Hybrid encryption

In the last chapter, we have studied the IND-CCA security definition. We will now study how we can build encryption schemes that satisfy this definition, in particular by taking IND-CPA schemes and applying the (FO). Before, we need to discuss the so-called schemes.

Public key encryption (PKE) is usually slow, and typically restricts the size of the message that can be encrypted. One solution is to use $pk$ to encode not the message directly, but a one-time key $k$ that is in turn used to encrypt the message, which can be done by a more inexpensive algorithm such as a symmetric encryption scheme.

In contrast to traditional hybrid encryption, today we usually use a (KEM) instead of Enc, and a (DEM) instead of symmetric encryption. KEM consists of 3 algorithms: Keygen, Encaps, and Decaps, as illustrated below:

$\epsilon$-correctness is given by $\Pr[k'=k:pk,sk\leftarrow\textrm{KeyGen}(), c,k\leftarrow\textrm{Encaps}(pk),k'\leftarrow\textrm{Decaps}(sk,c)]\geq 1-\epsilon$ (in the best case: $\epsilon=0$, a.k.a. perfect correctness). DEM, in turn, is equivalent to a symmetric encryption scheme. The modern definition of a hybrid scheme is outlined below:

Definition 12.1 (Hybrid encyrption (modern view))

Given: where the Keyspace of DEM must match message space of KEM, construct a PKE ($\widetilde{\text{Keygen}}, \widetilde{\text{Enc}}, \widetilde{\text{Dec}}$) as:

: If KEM has $\epsilon$-correctness and DEM has correctness, then $\widetilde{\text{Enc}}$ has $\epsilon$-correctness.

: If KEM is IND-CPA and DEM is IND-CPA, then the hybrid encryption is IND-CPA.

: If KEM is IND-CCA and DEM is IND-CCA, then the hybrid encryption is IND-CCA.

12.2 Fujisaki-Okamoto transform

We now ideally want to find IND-CCA DEMs and KEMs, which is the goal of the FO transform. We need a variant of the IND-CCA definition for that.

Definition 12.2 (($t,q,\epsilon$)-IND-CCA for KEMs) For all $t$-time $q$-query adversary , $\lvert\Pr[b'=1: \textrm{Game 1}]-\Pr[b'=1: \textrm{Game 2}]\rvert\leq\epsilon$, where

Game 1: Game 2:

where $\mathcal{K}$ is the key space, and DecapsOra($c$) returns Decaps($sk,c$) if $c\neq c^*$, else returns $\perp$.

Informally, this means that an adversary cannot tell apart a randomly generated key from one output by Encaps.

Our goal now is to make an IND-CCA secure KEM out of an IND-CPA PKE. We could start by defining an Encaps as Encaps($pk)=(k,c)$, where $k\xleftarrow{\$}\mathcal{K}$ and $c\leftarrow$ Enc($pk,k$). Since Enc is only IND-CPA, it could be the case, for example, that it is possible to obtain Enc($\bar{m}$) form Enc($m$), where $\bar{m}$ is obtained by flipping all bits of $m$. If that were the case, we could define a simple attack to the KEM:

To improve this, instead of outputing $k\xleftarrow{\$}\mathcal{K}$ directly, we could build an Encaps that outputs $(k,c)$ with $k:=H(m)$ with $H$ some hash function, and $c:=\textrm{Enc}(pk,m)$ for some $m\xleftarrow{\$}\mathcal{M}$. The previous attack does not work anymore:

Given $H(\bar{m})$ and the true key $H(m)$, there is no way to tell if the hashes are of related messages, so the adversary cannot tell Game 1 from Game 2. This encryption scheme, however, is still not IND-CCA. Since Enc is randomized, Enc($m$) can output different ciphertexts for the same $m$. Assume that, given $c^*\leftarrow\textrm{Enc}(m)$, we can calculate another $\tilde{c} \leftarrow\textrm{Enc}(m)$ such that $\tilde{c} \neq c^*$ (this can be done, for example, with the LPR scheme). Then, can simply send $\tilde{c}$ to Decaps and obtain the correct key $k^*$.

Suppose now for simplicity that Enc is deterministic. It could still be the case that you could transform a ciphertext $c:=Enc(m)$ into another ciphertext $\tilde{c}\neq\textrm{Enc}(m)$ such that Dec($\tilde{c}$)=$m$, and then use $\tilde{c}$ to attack it. We can detect this case during encryption by calculating $c:=\textrm{Enc}(pk,m)$ again and comparing it to $\tilde{c}$. If they do not match, it returns $\perp$ and the attack fails.

Even though we are closer to a final form, we are now relying on the assumption that Enc is deterministic, which goes against the IND-CPA definition. To solve this, we can use a randomized Enc whose randomness is generated from the message $m$ itself. Let Enc($pk,m;r$) denote the output of Enc($pk,m$) using $r$ as randomness. We can now define the FO transform:

Definition 12.3 (Fujisaki-Okamoto transform with explicit rejection)

KeyGen$_{FO}$: Encaps$_{FO}$($pk$): Decaps$_{FO}$($sk',c$):

In the variant with implicit rejection, instead of returning $\perp$, the algorithm returns $F(m)$ for some pseudo-random function $F$.

A slight variation of this is FO with rejection:

Definition 12.4 (Fujisaki-Okamoto transform with implicit rejection)

KeyGen$_{FO}$:

Encaps$_{FO}$($pk$): unchanged

Decaps$_{FO}$($sk',c$):

Here $F$ is a pseurandom function and $\mathcal{K}_F$ its keyspace.

We have (for example) that if Enc is IND-CPA, FO is IND-CCA. Similar results exist for other variants of FO and other assumptions about Enc (instead of IND-CPA). That way we can get IND-CCA encryption from LPR, McElice, Niederreiter and many more.