Results 1 to 6 of 6

Math Help - Hash functions.

  1. #1
    Newbie
    Joined
    Dec 2011
    Posts
    16

    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.

        If anyone can figure this out please help!

        Note: B = {0,1}.
    Last edited by mr fantastic; December 8th 2011 at 11:30 AM. Reason: Restored deleted question.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2011
    Posts
    127

    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2011
    Posts
    16

    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|.
    Last edited by mr fantastic; December 8th 2011 at 11:32 AM. Reason: Restored deleted post.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2011
    Posts
    127

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2011
    Posts
    16

    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}?
    Last edited by mr fantastic; December 8th 2011 at 11:34 AM. Reason: Restored deleted reply.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Dec 2011
    Posts
    16

    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
    Last edited by mr fantastic; December 8th 2011 at 11:35 AM. Reason: Restored deleted reply.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question on randomized algorithm/hash function.
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: December 11th 2011, 07:46 AM
  2. why should a hash table be prime number length?
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: May 7th 2010, 04:30 PM
  3. Replies: 3
    Last Post: February 23rd 2010, 04:54 PM
  4. a strongly universal (p,p)-hash family
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 3rd 2009, 02:47 PM
  5. Hash values: Weak and strong collision resistance
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 6th 2008, 06:14 AM

Search Tags


/mathhelpforum @mathhelpforum