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 is strongly 2-universal, so it is also 2-universal, that means for chosen independently and uniformly at random, and for any , we have that .

Because of this, we can deduce the following:

Now using Markov's inequality:

So, with probability at least .

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

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:

,

since and

So , and

.

Now do you know any probability bound I can use to get the result with probability at least ?

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