2
$\begingroup$

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$.

enter image description here

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 ?

$\endgroup$
  • 3
    $\begingroup$ It's obvious. Recall that choosing a random function is equivalent to choosing the function values independently, one at a time. $\endgroup$ – K.G. Dec 29 '14 at 23:34
  • $\begingroup$ Would you sketch the proof formally (mathematically) ? $\endgroup$ – Shuzheng Dec 31 '14 at 7:59
  • $\begingroup$ If it helps you to understand, think about the case when $\mathcal{X}$ is finite, so the cardinality of $\mathcal{F}^{\mathcal{X}, \mathcal{Y}}$ is $M^{|\mathcal{X}|}$ and the probability of picking $h$ at random s.t. $h(x) = y$ for $x$ and $y$ fix is (# of functions that relates $x$ to $y$) over (# of functions), i.e., $$\frac{M^{|\mathcal{X}|-1}}{M^{|\mathcal{X}|}} = \frac{1}{M}.$$ $\endgroup$ – Hilder Vítor Lima Pereira Sep 7 '16 at 23:02
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.