2
$\begingroup$

I've seen two definitions of a universal hash family, and my questions is if those are equivalent, i think they are and will explain why but i'm not sure if it is.

Definition 1:

$H$ is a universal hash family if and only if $$\mathbb{Pr_{h \in H}}[h(k) = h(l)] = 1/m$$

where $k \neq l$ and $k,l\in Key$ and $m$ is the Size of the Hashtable

Definition 2:

The same as above just substitute the equals sign with a less or equal sign.

Well, i think those definitions are equivalent, because i think the probability for a collision can't possibly be strictly less than 1/m or am i missing something?

P.S. I'm assuming that the cardinality of Key is bigger than the size of the hashtable m

$\endgroup$
1
$\begingroup$

I'm assuming that the cardinality of Key is bigger than the size of the hashtable m

There are still families with collision probability less than $1/m$, e.g., with three keys and two buckets,

$$\{(2, 1, 1), (1, 2, 1), (1, 1, 2)\}$$

has collision probability $1/3 < 1/2$, and there are other counterexamples for all other parameter settings. The most plausible path to your intuition being true would be if $h(k)$ and $h(l)$ were necessarily independent, but they're not and can in fact be anti-correlated.

$\endgroup$
0
$\begingroup$

There not the same. For example the identity hash table $h(x)=x$ you have: $$\mathbb{Pr}_{h \in H}[h(k) = h(l)] = 0$$ which answer definition 2 but not 1.

[Edit] A more interesting answer I hope :)

Let $H_n$ be the set of all functions of $\{1..n\}\to \{1..m\}$.

For $s\in \{1 .. m\}, i\in \{1..n\}$ we have $$\mathbb{Pr}_{h\in H_n}[h(i)=s]=\frac{\text{nbr of function s.t. }h(i)=s}{\text{total number of function}}=\frac{m^{n-1}}{m^n}=\frac{1}{m}$$ also for $s_1,s_2\in \{1 .. m\}, i,j\in \{1..n\},i\neq j$ we have $$\mathbb{Pr}_{h\in H_n}[h(i)=s_1\wedge h(j)=s_2]=\frac{\text{nbr of function s.t. }h(i)=s_1\wedge h(j)=s_2}{\text{total number of function}}=\frac{m^{n-2}}{m^n}=\frac{1}{m^2}=\mathbb{Pr}_{h\in H_n}[h(i)=s_1]\mathbb{Pr}_{h\in H_n}[h(j)=s_2]$$

It follows that $\forall i,j\in \{1..n\},i\neq j$ $$\mathbb{Pr}_{h\in H_n}[h(i)=h(j)]=\sum_{s=1}^m \mathbb{Pr}_{h\in H_n}[h(i)=s\wedge h(j)=s]=\sum_{s=1}^m\mathbb{Pr}_{h\in H_n}[h(i)=s]\mathbb{Pr}_{h\in H_n}[h(j)=s]=\frac{1}{m} $$

Hence $H_n$ is universal in the sense of definition 1.

Let $H_n'$ be the set of all function of $h:\{0..n\}\to \{1..m\}$ such that $h(0)=h(1)+1 \mod m$.

We the same proof as above it is obvious that $\forall i,j\in\{1,n\},i\neq j$ $$\mathbb{Pr}_{h\in H_n}[h(i)=h(j)]=\frac{1}{m}$$ and that $\forall j\in\{2..n\}$ $$\mathbb{Pr}_{h\in H_n}[h(0)=h(j)]=\sum_{s=1}^m \mathbb{Pr}_{h\in H_n}[h(0)=s\wedge h(j)=s]=\sum_{s=1}^m \mathbb{Pr}_{h\in H_n}[h(1)=s-1\mod m\wedge h(j)=s]=\sum_{s=1}^m\mathbb{Pr}_{h\in H_n}[h(0)=s-1\mod m]\mathbb{Pr}_{h\in H_n}[h(j)=s]=\frac{1}{m} $$

BUT $$\mathbb{Pr}_{h\in H_n}[h(0)=h(1)]=0$$

Hence $H_n'$ is universal in the sense of definition 2 but not definition 1.

Sorry for the long answer. I hope I didn't made a mistake ...

$\endgroup$
  • 1
    $\begingroup$ But the cardinality of Key is much bigger than m (in general), so there has to be collisions $\endgroup$ – Rob May 21 '13 at 16:45
  • $\begingroup$ Hu? why did I get a down vote? The question was were the definition equivalent I gave one example where they are not. You made an edit adding conditions on size of Key and m an I made an edit for a counter example whatever the sizes are ... $\endgroup$ – wece May 22 '13 at 9:51
0
$\begingroup$

No they are not equivalent. As a matter of fact, they are not definitions the same thing. The one with the less than or equal sign is called "universal hashing" and the one with the equal sign is called "pairwise independent hashing". Pairwise independent hashing is strictly stronger than universal hashing, and so both definitions are not equivalent.

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