Hash functions.

**complexity9** · December 6th 2011, 02:43 PM

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.
  
  If anyone can figure this out please help!
  
  Note: B = {0,1}.

**Annatala** · December 6th 2011, 11:39 PM

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?

**complexity9** · December 7th 2011, 02:27 AM

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

**Annatala** · December 7th 2011, 08:34 AM

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.

**complexity9** · December 7th 2011, 09:27 AM

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}$ ?

**complexity9** · December 7th 2011, 10:27 AM

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

Thread: Hash functions.

LinkBack

Thread Tools

Display

Hash functions.

Re: Boolean hash function

Re: Boolean hash function

Re: Boolean hash function

Re: Boolean hash function

Re: Boolean hash function

Similar Math Help Forum Discussions

Question on randomized algorithm/hash function.

why should a hash table be prime number length?

Circular functions as opposed to traditionally determined trigonometric functions?

a strongly universal (p,p)-hash family

Hash values: Weak and strong collision resistance

Search Tags