This is background and a basis for a proof for the Random Oracle section [here.](https://hackmd.io/l_pnHH6gRTSyTNZxACVpUA?view)

**Theorem:**

Let $R: \mathbb{F} \rightarrow \mathbb{F}$ be a collision-resistant encoding function and $\phi: \mathbb{F} \rightarrow \mathbb{F}$ be a random oracle. Define $\mathfrak{H} = \phi \circ R$. Then $\mathfrak{H}$ is indifferentiable from a random oracle in the sense of Maurer et al [2].

**Proof strategy:**

We want to show that any probabilistic polynomial-time distinguisher $D$ cannot distinguish interactions with $\mathfrak{H}$ from interactions with a random oracle $RO$ with non-negligible advantage.

That is:

$|\Pr[D^{\mathfrak{H}} = 1] - \Pr[D^{RO} = 1]|$ is negligible.

The high-level idea is that since $\phi$ is already a random oracle, it "hides" the output of $R$ perfectly.

Specifically:

Because $R$ maps elements uniform randomly even for the same preimage by the collision resistance property, the distribution of $R(x)$ is computationally indistinguishable from uniform by a reduction argument to breaking collision resistance of $R$.

Because $\phi$ is a random oracle, $\phi(R(x))$ is therefore also indistinguishable from the uniform distribution over $\mathbb{F}$.

Thus, the view of any polynomial-time $D$ interacting with $\mathfrak{H}$ by making queries and getting back a uniform element of $\mathbb{F}$ is indistinguishable from interactions with a true random oracle.

We can formalize this via a sequence of experiments, with $Experiment\ 0$ being interactions of $D$ with $\mathfrak{H}$ and $Experiment\ 1$ being with a random oracle. Then we use the two steps above to argue computational indistinguishability of each experiment.

This completes the proof outline. Below I provide more rigorous details for the sequence of experiments.

____

**Proof:**

Let $D$ be a polynomial-time distinguisher that attempts to distinguish interactions with $\mathfrak{H}$ versus a random oracle $RO$.

Define the following experiments:

$Experiment\ 0:$ $D$ interacts with $\mathfrak{H}$.

$Experiment\ 1:$ $D$ interacts with $RO$.

We want to show that $|Pr[D^{\mathfrak{H}} = 1] - Pr[D^{RO} = 1]|$ is negligible.
Where $Pr$ stands for probability, and the inner content meaning the probability the distinguisher outputs 1.

We define hybrid experiment $H_1$:

$H_1$ internally simulates a random oracle $\phi$. When $D$ makes a query $x$: $H_1$ queries its own oracle to obtain $r \gets R(x)$, computes $y = \phi(r)$ using the internal $\phi$, and returns $y$ to $D$.

$H_1$'s oracle is either $R$ or a uniformly random function $f$.

We define two variants:

$H_1^R$: The oracle is $R$
$H_1^f$: The oracle is the random function $f$

We now make two claims:

*Claim 1: $H_1^R \equiv Experiment\ 0$*

This holds because $\phi \circ R = \mathfrak{H}$, so the view of $D$ interacting with $\mathfrak{H}$ is identical to its view interacting with $H_1^R$.

*Claim 2: $|Pr[D^{H_1^R} = 1] - Pr[D^{H_1^f} = 1]|$ is negligible*

This follows from the collision resistance of $R$ and the uniform random outputs of $\phi$.

Specifically:

Because $R$ is collision resistant, the distribution of $R(x)$ over uniform random choice of $x$ is computationally indistinguishable from uniform from the perspective of any polynomial-time algorithm.

For any fixed output $r$ of the oracle, since $\phi$ is a random oracle, $\phi(r)$ is uniform over $\mathbb{F}$.
Thus, the view of $D$ interacting with $H_1^f$ (getting uniform outputs) is computationally indistinguishable from its view interacting with $H_1^R$.

Finally, observe that $H_1^f \equiv Experiment\ 1$ since in both cases $D$ gets uniform random values over $\mathbb{F}$ in response to each query.

By the triangle inequality (Citation [1]; B Proof of Lemma 11) and Claims 1 and 2, we have:

$|Pr[D^{\mathfrak{H}} = 1] - Pr[D^{RO} = 1]|$ $\leq$ $|Pr[D^{\mathfrak{H}} = 1] - Pr[D^{H_1^R} = 1]|$ $+$ $|Pr[D^{H_1^R} = 1] - Pr[D^{H_1^f} = 1]|$ $+$ $|Pr[D^{H_1^f} = 1] - Pr[D^{RO} = 1]|$

Which is negligible.

**TODO:**

> R is collision resistent and order matter
> need proof.

---

Citation:

[1] Fujisaki, E., & Okamoto, T. (1999) [Secure integration of asymmetric and symmetric encryption schemes. CRYPTO 1999](https://courses.grainger.illinois.edu/cs598dk/fa2019/Files/fujisaki_okamoto.pdf)

[2] Maurer, U., Renner, R., Holenstein, C. (2004). [Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology](https://eprint.iacr.org/2003/161.pdf).