# Hash functions.

• December 6th 2011, 03:43 PM
complexity9
Hash functions.
1. I think that I have managed to show that H_n,m is a strongly 2-universal family of hash functions. However, I'm stuck on the second part of the question. I was only able to show that |T| <= 32 with probability at least 1/2.

Note: B = {0,1}.
• December 7th 2011, 12:39 AM
Annatala
Re: Boolean hash function
It might help if you describe more about what you've done rather than just pasting the problem here. How did you prove what you've proven so far?
• December 7th 2011, 03:27 AM
complexity9
Re: Boolean hash function
1. Okay so I have proved that $h$ is strongly 2-universal, so it is also 2-universal, that means for $A \in \mathbb{B}^{m\times n}, b\in \mathbb{B}^m$ chosen independently and uniformly at random, and for any $x\in\mathbb{B}^n$, we have that $Pr(h(x) = 0) \leq 2^{-m}$.

Because of this, we can deduce the following:

$E[|T|] = E[\sum_{x\in S} 1_{ \{ h(x) = 0 \} }] = \sum_{x\in S} E[1_{ \{ h(x) = 0 \} }] = \sum_{x\in S} Pr (h(x) = 0) \leq \sum_{x\in S} 2^{-m} \leq 2^{m+4} 2^{-m} = 2^4 = 16$

Now using Markov's inequality: $Pr(|T| \geq 2E[|T|]) \leq \frac{E[|T|]}{2E[|T|]}$

So, $|T| \leq 32$ with probability at least $\frac{1}{2}$.

Of course this is not the answer they want, but I'm not able to get a tighter bound on $|T|$.
• December 7th 2011, 09:34 AM
Annatala
Re: Boolean hash function
Have you tried applying the other side of the inequality? I don't see m+3 anywhere in your work above.

I have to bow out here because although I know a great deal about hash functions (I teach them) and a little about cryptography (I've taken pretty much every database class they have at OSU), this is beyond my area of knowledge. My intuition is that you can average m+3 and m+4 to get (16 + 32) / 2 = 24, but I have nothing to back that up with.
• December 7th 2011, 10:27 AM
complexity9
Re: Boolean hash function
1. Okay I think I might have another idea. Here it is:

$2^{-m} \geq Pr(h(x) = 0) = 1 - Pr(h(x) \neq 0) = 1 - \sum_{y \neq 0} Pr(h(x) = y) \geq 1 - \sum_{y \neq 0} 2^{-m} = 1 - (2^m - 1) 2^{-m} = 2^{-m}$,

since $y \in \mathbb{B}^m$ and $y \neq 0$

So $Pr(h(x) = 0) = 2^{-m}$, and

$8 \leq E[|T|] \leq 16$.

Now do you know any probability bound I can use to get the result $1 \leq |T| \leq 24$ with probability at least $\frac{1}{2}$?
• December 7th 2011, 11:27 AM
complexity9
Re: Boolean hash function
1. Actually thanks for your suggestion Annatala, it finally lead me to the final solution. From my above post, we just continue on to find the variance of |T|, then apply Chebyshev's inequality to get the final result. If you are interested in the formal proof, I could send it to you.

Anyway, thanks again mate.

-Peter