4
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
14
  • $\begingroup$ 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|}$ $\endgroup$ Dec 14, 2020 at 11:57
  • 1
    $\begingroup$ @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$. $\endgroup$
    – SEJPM
    Dec 14, 2020 at 13:25
  • 1
    $\begingroup$ The “collision” probability, that $h(x)=h(y)$, is $1/|V|$, not $1/|V|^2$. $\endgroup$ Dec 14, 2020 at 13:54
  • $\begingroup$ @ChrisPeikert yeah, I was a bit unsure and guessed wrong, woops. $\endgroup$
    – SEJPM
    Dec 14, 2020 at 13:55
  • $\begingroup$ @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? $\endgroup$ Dec 16, 2020 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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