13 Quantum Random Oracle Model (QROM)

We will first need to define the suitable assumption for the hash functions $G$ and $H$ in the post-quantum security scenario, in order to prove security of the FO transform. Hash functions, however, are difficult to mathematically reason about, and even though the outputs of the hash function should look random, they are entirely deterministic. This makes it much harder to prove security definitions of protocols that rely on hash functions.

Instead of trying to give mathematical definitions of individual desirable properties of hash functions, we just pretend that $H$ is actually a uniformly random function. This is the so-called (ROM/QROM). It leaves us with a heuristic for giving security proofs:

Step 1: Prove security under the randomness assumption,
Step 2: Heuristically assume that the original scheme is secure using the real hash function.

Though this heuristic is mathematically false, the counterexamples are really hard to get in practice, so it can be used for nearly all real world cases. The ROM/QROM assumption usually makes schemes much more practical, and their security proofs, in turn, more tractable.

For a practical example, consider the following Encaps and Decaps functions:

Encaps($pk$): Decaps($sk,c$):

Theorem

: If Enc is IND-CPA PKE and $H$ a quantum random oracle, then Decaps is OW-CPA KEM.

There is a cyclic dependency between the arguments, which can be broken with QROM.

Definition 13.1 (($t,q$)-OW-CPA) (Keygen, Encaps, Decaps) is ($t,\epsilon$)-OW-CPA iff for each $t$-time adversary $A$:

\[ \Pr[k'=k:\color{red}H\xleftarrow{\$}(\mathcal{M}\rightarrow\mathcal{R}) \color{black}, (pk,sk)\leftarrow\textrm{KeyGen}, k,c\leftarrow\textrm{Encaps}(pk), k'\leftarrow A^{\color{red}H\color{black}}(pk,c)]\leq\epsilon \]

All oracles are available as superposition query oracles (A has access to $U_H:|x,y\rangle\rightarrow|x,y\oplus H(x)\rangle$).

In summary, to use the QROM, you first need to pick a uniformly random $H$ in every game in the definition, and give oracle access to both the adversary and the honest algorithm. To prove things in the QROM, the two most important techniques are the one-way to hiding (O2H) theorem, which we will present below, and compressed oracles, which are beyond the scope of this lecture.

The basic idea of O2H is that, if you have access to a function $H$, and it is changed at position $m$, then you cannot notice the difference unless you query $H(m)$. This is trickier in the quantum setting, since the adversary can query all $H(x)$ in superposition, though the result for given $m$ has exponentially small amplitude.

Theorem

(O2H): Let $A$ be a $q$-query algorithm, let Init be an arbitrary classical algorithm that computes: Consider the following games:

Then $\lvert\Pr[b=1: \textrm{Game 1}]-\Pr[b=1: \textrm{Game 2}]\rvert\leq\mathcal{O}(q\sqrt{\Pr[m'=m:\textrm{Guess}]})$.

13.1 Optimality of Grover

We will now apply the O2H theorem to prove the optimality of the quadratic speed-up of Grover’s algorithm. We consider the following setting:

We will show that $\Pr[m'=m]\leq\mathcal{O}(q\sqrt{2^{-n}})$ in this game. Note that this shows that one cannot find $m$ in substantially less than $\sim\sqrt{2^n}$ queries; thus it shows optimality of Grover’s algorithm.

Let $X:=\{0,1\}^n$, and restate the game as follows:

Game 1: $G\xleftarrow{\$}(X\rightarrow Y)$, $m\xleftarrow{\$}X$, $k\leftarrow G(m)$, $m'\xleftarrow{\$}A^G(k)$

Rewriting this into a form useful for O2H:

Where $H(m:=k)$ is the function that equals $H$ for all inputs except $m$, where the function returns $k$. We have that $\Pr[m'=m:\textrm{Game 1}]=\Pr[b=1:\textrm{Game 2}]$. We now apply O2H:

Game 3: ($G, H, m, \textrm{stuff}$) $\leftarrow$ Init, $b\leftarrow B^H(\textrm{stuff})$.

By O2H, $\lvert \Pr[b=2:\textrm{Game 2}]-\Pr[b=1:\textrm{Game 3}]\rvert\leq\mathcal{O}(q\sqrt{\Pr[m'=m:\textrm{Game 4}]})$, where Game 4 is the guessing game:

Game 4: ($G, H, m, \textrm{stuff}$) $\leftarrow$ Init, $i\xleftarrow{\$}\{1,\ldots, q\}$, run $B^H(\textrm{stuff})$ untill the $i$-th query, and measure $X$ to obtain $m'$.

Unpack Game 3 to get:

Game 5: $m\xleftarrow{\$}X$, $H\xleftarrow{\$}(X\rightarrow Y)$, $k\xleftarrow{\$}k$, $G:=H(m:=k)$, $m'\leftarrow A^H(k)$, $b:=[m'=m]$

In Game 5, $A^H(k)$ only gets information independent of $m$, so $\Pr[b=1:\textrm{Game 3}]\leq 2^{-n}$. Similarly, unpack Game 4:

Game 6: $m\xleftarrow{\$}X$, $H\xleftarrow{\$}(X\rightarrow Y)$, $k\xleftarrow{\$}k$, $G:=H(m:=k)$, $i\xleftarrow{\$}\{1,\ldots, q\}$, run $A^H(\textrm{stuff})$ untill the $i$-th query, and measure the query register to obtain $m'$.

Then $\Pr[m'=m: \textrm{Game 4}]\leq 2^{-n}$. In summary, we have:

\[\begin{equation} \begin{split} \Pr[b=1:\textrm{Game 1}]=\Pr[b=1:\textrm{Game 2}] & \leq \\ \Pr[b=1:\textrm{Game 3}] + \mathcal{O}(q\sqrt{\Pr[m'=m:\textrm{Game 4}]}) & \leq \\ 2^{-n}+\mathcal{O}(q\sqrt{2^{-n}}) & = \\ \mathcal{O}(q\sqrt{2^{-n}}) & \\ \end{split} \end{equation}\]

13.2 Proof of Fujisaki-Okamoto (toy version)

We will now use the O2H theorem to prove the security of the FO transform. Instead of working with the full FO transform, we will work with a simpler ``toy version” of it:

Theorem

: If Enc is IND-CPA and $|\mathcal{M}|$ is large enough and $G$ is a random oracle, then $\textrm{Encaps}'$ is an OW-CPA-secure KEM.

: Fix a $q$-query adversary $A$.

Our goal is to show that $\Pr[m'=m:\textrm{Game 1}]\leq\epsilon$ for suitable $\epsilon$. Let’s first unwrap the definitions:

Then $\Pr[m'=m:\textrm{Game 1}]=\Pr[m'=m:\textrm{Game 2}]$. We now prepare for applying O2H, defining: and its counterpart: We now define the guess game:

By O2H, $\lvert\Pr[b=1:\textrm{Game 3}]-\Pr[b=1:\textrm{Game 4}]\rvert\leq\mathcal{O}(q\sqrt{\Pr[m'=m:\textrm{Game 5}]})$. Now define:

so $\Pr[b=1:\textrm{Game 6}]=\Pr[b=1:\textrm{Game 4}]$. Also, define a variant of this game where we encrypt 0.

By the definition of IND-CPA, $\lvert\Pr[b=1:\textrm{Game 6}]-\Pr[b=1:\textrm{Game 7}]\rvert\leq\delta$ for suitable $\delta$. Since we do not use $m$ in Game 7, we have that $\Pr[b=1:\textrm{Game 7}]\leq\frac{1}{|\mathcal{M}|}$.

Let Game 8, Game 9 be like Game 6, Game 7, except saying ``run $\ldots$ run $A^H(pk,c)$ untill the $i$-th query measure $m'$. “” VERIFY

Then, similar to the analysis of Game 6, 7, we have: $\Pr[b=1:\textrm{Game 5}]=\Pr[b=1:\textrm{Game 8}]$ and $\lvert \Pr[b=1:\textrm{Game 8}]-\Pr[b=1:\textrm{Game 9}] \rvert\leq \delta$ and $\Pr[b=1:\textrm{Game 9}]\leq\frac{1}{|\mathcal{M}|}$.

Running through the whole chain of games, we conclude that $\Pr[b=1:\textrm{Game 1}]\leq\mathcal{O}\left(q\sqrt{\delta+\frac{1}{|\mathcal{M}|}}\right)$.

13.3 Security proof of the FO transform

For the following theorem, recall the definition of the FO transform with implicit rejection in Definition 12.4.

Theorem

: If $F: \mathcal{K}_F \times \mathcal{C}\rightarrow\mathcal{K}$ is a pseudo-random function (PRF) Enc is IND-CPA $\forall m$, $\Pr[\textrm{Dec}(sk,\textrm{Enc}(pk,m))=m: pk,sk\leftarrow\textrm{KeyGen}]=1$ $G,H$ are quantum random oracles $|\mathcal{M}|$ is sufficiently large, then Encaps$_{FO}$ (implicit rejection) is IND-CCA.

: Fix $t$-time, $q$-query adversary $A$. Game 0 is just the IND-CCA game with $A$, with the definitions unfolded:

By the definition of IND-CCA, $\Pr[b'=b:\textrm{Game 0}]=\frac{1}{2}\pm\epsilon$ for suitable $\epsilon$.

Game 1: Change from Game 0: pick $H_r\xleftarrow{\$}\mathcal{C}\rightarrow\mathcal{K}$. Use $H_r(c)$ instead of $F(k_F, c)$.

So $\Pr[b'=b:\textrm{Game 0}]\approx\Pr[b'=b:\textrm{Game 1}]$ because $F$ is PRF.

Game 2: Change from Game 1: Pick $m^*$ as $m^*\xleftarrow{\$}\mathcal{M}\setminus\{0\}$

So $\Pr[b'=b:\textrm{Game 2}]\approx\Pr[b'=b:\textrm{Game 1}]$.

Game 3: Change from Game 2: $H$ is redefined as a composition of two functions. We restate the complete game here:

Note that we also replaced $H(m)$ by $H_q(c)$ in the decryption oracle because in that place, $c=\textrm{Enc}(pk,m;G(m))$ and thus $H_q(c)=H(m)$.

Suppose you know $c=\textrm{Enc}(pk,m;G(m))$ and you want $H(m)$, without having $sk$. $H(m)=H_q(\textrm{Enc}(pk,m;G(m)))=H_q(c)$. This switch of $H$ can’t be noticed because $m\mapsto\textrm{Enc}(pk,m;G(m))$ is injective and the composition of a random function with an injective function is also a random function. Therefore, $\Pr[b'=b:\textrm{Game 3}]=\Pr[b'=b:\textrm{Game 2}]$

Game 4: Change from Game 3: Replace $H_q$ by $H_r$ in decryption oracle and in the definition of $H$.

Then $\Pr[b'=b:\textrm{Game 4}]=\Pr[b'=b:\textrm{Game 3}]$. This uses that $H_q$ and $H_r$ are never queried on the same inputs. Continuing, we define:

Game 5: Replace $c^*=\textrm{Enc}(pk,m^*;G(m))$ by $c^*\leftarrow\textrm{Enc}(pk,0)$.

$\Pr[b'=b:\textrm{Game 5}]\approx\Pr[b'=b:\textrm{Game 4}]$. This is a whole subproof using the IND-CCA property but essentially is the same proof as the $\lvert\Pr[b=1:\textrm{Game 2}]-\Pr[b=1:\textrm{Game 7}]\rvert$ in Section 13.2.

Note that now, the decryption oracle returns $H_r(c)$ in both if-branches, so we can state it as: $D(c):$ return $H_r(c)$.

Game 6: Replace $H_q(c^*)$ by random since $H_q$ not used elsewhere.

$\Pr[b'=b:\textrm{Game 6}]=\Pr[b'=b:\textrm{Game 5}]$. $b$ only switches two identical lines, so $\Pr[b'=b: \textrm{Game 6}]=\frac{1}{2}$. Putting everything together, $\Pr[b'=b:\textrm{Game 1}]\approx\frac{1}{2}$.