# Why does the hashfamily of all functions with $\{h \in H_0 | h:U \rightarrow V\}$ satisfy universal hashing?

I read in our university lecture on hashing that it would be good (even though it is way to space intensive) if we could take the set of all function from $$U \rightarrow V$$ to satisfy the following universal hashing condition: for all $$\forall x,y\in U$$ so that $$x≠y$$, we have $$Pr[h(x)=h(y)]≤\frac{1}{|V|}$$

I actually don´t understand why the set of all functions would satisfy our condition. I can definitively see that there are some function which fit this condition, but I can think of other functions which dont meet the condition. So I would have to make a statement about average probabilty over the set of all functions, but how could something like this be defined precisely?

Or am I taking something wrong here and the Set of all functions wouldn´t meet the condition, but would actually be better that the condition taking the case that h is taking randomly from H? Even if so it seems to come down to the same problem.

First note that the set of all functions $$U\to V$$ contains for every value $$u\in U$$ and every value $$v\in V$$ a function $$f$$ such that $$f(u)=v$$. Also note that if you fix a point $$u\in U$$ and take a random function from $$U\to V$$, $$f(u)$$ is uniformly distributed in $$V$$.

Now if you apply that, fix any two points $$x\neq y,\quad x,y\in U$$. Now choose $$h$$ randomly out of $$U\to V$$. Note that $$h(x)$$ is uniformly distributed and $$h(y)$$ is uniformly distributed. The probability for $$h(x)$$ and $$h(y)$$ to be equal now should be $$1/|V|$$ which implies the desired universality.

Given that the above might not be entirely clear, let's do an example: $$U=\{1,2,3\}\quad V=\{1,2,3\}$$ Clearly there are 27 functions mapping from $$U$$ to $$V$$ and clearly there are 6 pairs of unequal values $$(x,y)\in U\times U$$ for which we need to check whether the probability holds.

• $$(x,y)=(1,2):$$ There are three possible ways to map $$1$$: to either 1,2, or 3, let's denote the actual value $$h(x)$$ for the moment. There are also three possible values to map $$2$$ to: 1,2, or 3, let's denote the actual value as $$h(y)$$. Given that these two choices are independent, there are 9 cases here.

• If $$h(x)=1$$ then the tested equation only holds if $$h(y)=1$$ as well which is a 1/3 chance
• If $$h(x)=2$$ then the same argument as for $$h(x)=1$$ applies with $$h(y)=2$$
• $$h(x)=3$$ goes analogously

Now counting the cases where the equation holds for $$(x,y)=(1,2)$$ we get $$3/9\leq 1/3$$ as demanded.

If we go through the other pairs as well, a very similar argument will ensue and we'll be getting $$3/9$$ for all of them. Therefore a random function from $$U$$ to $$V$$ satisfies universality.

• Can you give me a hint how the uniform distribution can be recognized within this context and how it play into the situation of probability. Also for example what about functions like any x maps to the same v for all x in U. This would be probability of 1 for h(x) = h(y) and not $\frac{1}{|V|}$ Commented Dec 14, 2020 at 11:57
• @FelixOuttaSpace Note that the probability is taken only over the choice of the function, not over the values of x and y. As for the constant functions, there are "only" $|V|$ of them but $|V|^{|U|}$ total functions. To better understand the set of all functions, it might be helpful to realize that if $|U|=1$ then a random choice of function equals a random choice of an output value which then gets "cartesian multiplied" to larger sizes for $U$. Commented Dec 14, 2020 at 13:25
• The “collision” probability, that $h(x)=h(y)$, is $1/|V|$, not $1/|V|^2$. Commented Dec 14, 2020 at 13:54
• @ChrisPeikert yeah, I was a bit unsure and guessed wrong, woops. Commented Dec 14, 2020 at 13:55
• @SEJPM the only part I am confused with is that you say the probability is taken over the choice of the function, though the defintion states Pr[h(x)=h(y)] with the same h and not a different h within it. Wouldnt it then be $Pr[h(y)=g(x)]$ with h,g $\in H_0$ then? Commented Dec 16, 2020 at 13:09