Describe an Explicit Universal Hash Function Family

Question

In this problem, I was given the follow mapping

 U = {0, 1, 2, 3, 4, 5, 6, 7} to {0, 1}

From this, there is an explicit universal hashing function that must be derived, with the hint that this can be done with a set of 4 functions. Unfortunately, despite searching through articles on how to do this, I am still confused. Any help in understanding how to find this hashing function and moving towards the right direction is greatly appreciated!

EDIT:

After some deliberation, this is what I came up with; would this be correct?

     0  1  2  3  4  5  6  7
---------------------------
h1 | 1  1  0  0  0  0  0  0 
h2 | 0  0  1  1  0  0  0  0
h3 | 0  0  0  0  1  1  0  0
h4 | 0  0  0  0  0  0  1  1

Answer 1

Using the definition from Wikipedia:

A family of functions H = {h: U → [m]} is called a universal family if, ∀ x,y ∈ U, x ≠ y : Pr_h∈H[h(x) = h(y)] ≤ ¹/_m.

In your case, this means that for any two values x and y in the set {0, 1, 2, 3, 4, 5, 6, 7}, at most two of your four hash functions can map them to the same bit.

Your suggestion:

     0  1  2  3  4  5  6  7
---------------------------
h1 | 1  1  0  0  0  0  0  0 
h2 | 0  0  1  1  0  0  0  0
h3 | 0  0  0  0  1  1  0  0
h4 | 0  0  0  0  0  0  1  1

does not work, because there are four pairs (x, y) — namely (0,1), (2,3), (4,5), and (6,7) — where all four hash functions map them to the same bit.

Instead, here are some options that do work:

     0  1  2  3  4  5  6  7
---------------------------
h1 | 0  0  0  0  1  1  1  1
h2 | 0  0  1  1  0  0  1  1
h3 | 0  1  0  1  0  1  0  1
h4 | 0  1  1  0  1  0  0  1

     0  1  2  3  4  5  6  7
---------------------------
h1 | 0  0  0  1  0  1  1  1
h2 | 0  0  1  0  1  0  1  1
h3 | 0  1  0  0  1  1  0  1
h4 | 1  0  0  0  1  1  1  0