We need to show that the function family M is universal as long as the \(m\) chosen follows two rules.
First, \(m\) cannot be all zeroes because if that is allowed, then the 8 bit vectors you will get, will all be 0 and your numbers will all go to the same spot. Next, you have to make sure the rows of the matrix are distinct because if some rows repeat, the corresponding spots in the 8 bit number will always match up. That means you won’t be able to have your numbers go to certain spots because it would be impossible to get that number using the \(m(y)\) formula.
If \(m\) follows the above rules, it will then be universal because we can show that it is consistent and random.
Consistent: If you fix the M, the \(m(y)\) formula will give you the same value for the same number \(y\) since the formula will never change as along as you keep the same M.
Random: We need to show that if you randomly sample a number \(x\), it has an equal probability of landing at any of the indices for the hashing table. Since there are 256 different indices we need to show for any 32 bit number it has a \(\frac{1}{256}\) or \((\frac{1}{2})^8\) chance of landing at any particular spot.
The hashing function takes a 32 bit number, transforms it into an 8 bit number, and it results in 256 different 8 bit numbers. Now, we just need to show that using the \(m(y)\) formula all of the 32 bit numbers are uniformly distributed into the range of 8 bit numbers. The \(m(y)\) formula takes a randomly sampled 32 bit vector and then multiplies it to the Matrix M to make this 8 bit number. So each bit of the 8 bit vector is determined by the dot product of two 32 bit vectors and then taking \(mod2\) of that number.
So if we can show that the dot product of two random 32 bit numbers and then taking \(mod2\) of that number results in a \(\frac{1}{2}\) chance of 0, and \(\frac{1}{2}\) chance of 1, we can prove randomness. We can prove this because for each spot of the 8 bit number if there is a \(\frac{1}{2}\) chance of being 1 or 0, that means the probability of being any particular number is \((\frac{1}{2})^8\), which is what we were looking for.
Now to prove that the dot product of two random 32 bit numbers and then taking \(mod2\) of that number results in a \(\frac{1}{2}\) chance of 0 and \(\frac{1}{2}\) chance of 1.
Let us call the first 32 bit number \(x\) and we will fix that 32 bit number to be anything except 0. We will show that if you randomly select another 32 bit number (we will call y) you have a \(\frac{1}{2}\) of being 1 or 0.
The probability that \(x*y=1\) is the probability that there are an odd number of \(1*1\) during the dot product. Since we are only counting the \(1*1\) we only care about the number of bits in \(x\) that are 1. Since all the 0 bits in \(x\) will just get you 0 no matter what they value in \(y\) is. So let us say that there are a total of \(n\) bits with the value 1 in x.
Now we look at the n positions in y that line up with the 1s in x because those values will determine if the dot product is 1 or 0. If we look at those n positions in y, if an odd number of them are 1, the dot product will be 1. If an even number of them is 1 then the dot product is 0. So:
\(P(\mbox{dot product}=1) = P(\mbox{out of a total of n spots an odd number of them are 1})\)
\(P(\mbox{dot product}=1) = P(\mbox{only one 1 in n bits}) + P(\mbox{only 3 1s in n bits}) + P(\mbox{only 5 1s in n bits})...\)
\(P(\mbox{dot product}=1) = \sum_{i=0}^{\frac{n}{2}} {{n}\choose{2i+1}} * (\frac{1}{2})^n = (\frac{1}{2})^n * \sum_{i=0}^{\frac{n}{2}} {{n}\choose{2i+1}}\)
This summation is just the sum of odd index binomial coefficients.
We know that \(\sum_{i=0}^{n} {{n}\choose{i}} =2^n\)
We also know that \(\sum_{i=0}^{n} -1^i * {{n}\choose{i}} =0\)
If you subtract the second equation from the first you get:
2\(\sum_{i=0}^{n} {{n}\choose{2i+1}} =2^n\)
which implies that \(\sum_{i=0}^{n} {{n}\choose{2i+1}} =2^{n-1}\)
This means that the sum of the odd index binomial coefficients is \(2^{n-1}\)
So \(P(\mbox{dot product}=1)=(\frac{1}{2})^n \sum_{i=0}^{\frac{n}{2}} {{n}\choose{2i+1}} = (\frac{1}{2})^n * (2)^{n-1} = \frac{1}{2}\)
We have shown that the dot product between x and y results in the bit value being 1, \(\frac{1}{2}\) of the time, which means it will result in 0, the other half. This proves randomness.
\(256\) bits under above reasoning to create the (1,0) matrix M.