Formal proof of theorem concerning the Random Oracle Model

Question

Reading a book on cryptography by Douglas R. Stinson I've met the following theorem, which is stated without proof (see here).

Thereby, $\mathcal{F^{X,Y}}$ denotes the set of all functions from $\mathcal{X}$ to $\mathcal{Y}$ and $|\mathcal{Y}|=M$.

Is no proof given because it is hard, or because the proof is obvious ? Nothing is said about whether the message space $\mathcal X$ is finite or infinite. I guess, I could see informally that the probability must be constant if this space is finite.

Could someone show the formal proof or lead the way ?

Answer 1

As @K.G pointed out in the comments - the proof is obvious.

I'll explain:

• We sample the function $h$ from the set of all possible functions that maps from the set $\mathcal{X}$ to the set $\mathcal{Y}$, where the size of the set $\mathcal{Y}$ is $M$. We denote the set of all possible functions from $\mathcal{X}$ to $\mathcal{Y}$ by $\mathcal{F}^{\mathcal{X}\rightarrow \mathcal{Y}}$.
• Note that it doesn't matter whether $\mathcal{X}$ is finite or infinite, as far as every function in $\mathcal{F}^{\mathcal{X}\rightarrow \mathcal{Y}}$ is defined on every value in $\mathcal{X}$ (which is the case, of course, by the definition of $\mathcal{F}^{\mathcal{X}\rightarrow \mathcal{Y}}$). Then, if $|\mathcal{X}|$ is infinite, your question is in place: how can we hold such an $h$ (its size is infinite while our memory is finite)? The answer is that we can determine $h$ on-the-fly, whenever $h$ is being queries on $x$ first check whether $h$ was queried on $x$ beforehand, if so, there is an entry $(x,y)$ in $\mathcal{x}_0$ and we return $y$. Otherwise, if $h$ was not queried on $x$ before then we sample a uniformly random element $y$ from $\mathcal{Y}$ and add $(x,y)$ to $\mathcal{X}_0$.

• Also note, that although the author only mentioned that

  $h\in \mathcal{F}^{\mathcal{X}\rightarrow \mathcal{Y}}$ is chosen randomly

  he actually meant that $h$ is chosen randomly from a uniform distribution over $\mathcal{F}^{\mathcal{X}\rightarrow \mathcal{Y}}$ (otherwise the theorem is incorrect).

• Now, take some $x\notin\mathcal{X}_0$, i.e. $h$ wasn't queried on $x$ before (thus, we don't know its answer to such query yet). Since $h$ was chosen uniformly at random from all possible functions it means that for every query $x\in\mathcal{X}$ $h$ would answer with a uniformly random element from $\mathcal{Y}$ and since $|\mathcal{Y}|=M$ every $y\in\mathcal{Y}$ has the same probability to be chosen as the answer for the query $x$. This probability is simply $Pr[h(x)=y]=1/M$.

• Note that the above probability depends only on $M=|\mathcal{Y}|$ and not on $|\mathcal{X}|$ because the result of $h$ when applied to the query $x$ is an element which is chosen randomly from a uniform distribution over $\mathcal{Y}$, thus, every element $y\in\mathcal{Y}$ has the same probability to be chosen.