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?

Re: Boolean hash function

- Okay so I have proved that $\displaystyle h$ is strongly 2-universal, so it is also 2-universal, that means for $\displaystyle A \in \mathbb{B}^{m\times n}, b\in \mathbb{B}^m$ chosen independently and uniformly at random, and for any $\displaystyle x\in\mathbb{B}^n$, we have that $\displaystyle Pr(h(x) = 0) \leq 2^{-m}$.

Because of this, we can deduce the following:

$\displaystyle 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: $\displaystyle Pr(|T| \geq 2E[|T|]) \leq \frac{E[|T|]}{2E[|T|]} $

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

Of course this is not the answer they want, but I'm not able to get a tighter bound on $\displaystyle |T|$.

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.

Re: Boolean hash function

- Okay I think I might have another idea. Here it is:

$\displaystyle 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 $\displaystyle y \in \mathbb{B}^m$ and $\displaystyle y \neq 0$

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

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

Now do you know any probability bound I can use to get the result $\displaystyle 1 \leq |T| \leq 24$ with probability at least $\displaystyle \frac{1}{2}$?

Re: Boolean hash function

- 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