Question

Let$\mathbf{\left[}\mathbf{m}\mathbf{\right]}$denote the set$\mathbf{\{}\mathbf{0}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{\dots }\mathbf{,}\mathbf{m}\mathbf{-}\mathbf{1}\mathbf{\}}$. For each of the following families of hash functions, say whether or not it is universal, and determine how many random bits are needed to choose a function from the family.

(a) $\mathit{H}\mathbf{=}\mathbf{\{}{\mathbf{h}}_{{\mathbf{a}}_{\mathbf{1}}\mathbf{,}{\mathbf{a}}_{\mathbf{2}}}\mathbf{:}{\mathbf{a}}_{\mathbf{1}}\mathbf{,}{\mathbf{a}}_{\mathbf{2}}\mathbf{\in }\mathbf{\left[}\mathbf{m}\mathbf{\right]}\mathbf{\}}$, where$\mathit{m}$is a fixed prime and

${\mathit{h}}_{{\mathbf{a}}_{\mathbf{1}}}\mathbf{·}{\mathit{h}}_{{\mathbf{a}}_{\mathbf{1}}\mathbf{,}{\mathbf{a}}_{\mathbf{2}}}\mathbf{(}{\mathbf{x}}_{\mathbf{1}}\mathbf{,}{\mathbf{x}}_{\mathbf{2}}\mathbf{)}\mathbf{=}{\mathit{a}}_{\mathbf{1}}{\mathit{x}}_{\mathbf{1}}\mathbf{+}{\mathit{a}}_{\mathbf{2}}{\mathit{x}}_{\mathbf{2}}\mathit{m}\mathit{o}\mathit{d}\mathit{m}$

Notice that each of these functions has signature${\mathit{h}}_{{\mathbf{a}}_{\mathbf{1}}\mathbf{,}{\mathbf{a}}_{\mathbf{2}}}\mathbf{:}{\mathbf{\left[}\mathbf{m}\mathbf{\right]}}^{\mathbf{2}}\mathbf{\to }\mathbf{\left[}\mathbf{m}\mathbf{\right]}$that is, it maps a pair of integers in$\mathbf{\left[}\mathbf{m}\mathbf{\right]}$to a single integer in$\mathbf{\left[}\mathbf{m}\mathbf{\right]}$.

(b) $\mathit{H}$is as before, except that now$\mathit{m}\mathbf{=}{\mathbf{2}}^{\mathbf{k}}$is some fixed power of.$\mathbf{2}$

(c) $\mathit{H}$is the set of all functions$\mathit{f}\mathbf{:}\mathbf{\left[}\mathbf{m}\mathbf{\right]}\mathbf{\to }\mathbf{[}\mathbf{m}\mathbf{-}\mathbf{1}\mathbf{]}$.

Short answer

a) It is proved that given family of hash functions,$H$is universal.

b) It is required to choose two integers, the total number of random bits required to select a hash function is$2^k$bits.

c) $m\log (m-1)$bits required to choose a function from$H$.

Step-by-step solution

To prove that the family of hash function His universal

(a)

$H=\{h_{a_1,a_2}:a_1,a_2\in \left[m\right]\}$and$h_{a_1,a_2}=\underset{i=1}{\overset{2}{}}{a}_i.x_{i}modm=(a_1{x}_1+a_2{x}_{2}modm)$

Assume that$x_2\ne y_2$.

Now, to prove$H=\{h_{a_1,a_2}:a_1,a_2\in \left[m\right]\}$is universal, it is required to find the probability

$Pr[h_{a_1,a_2}(x_1,x_2)=h_{a_1,a_2}(y_1,y_2)]$

Re write the above equation as follows:

$a_1(x_1-y_1)\equiv a_2(y_2-x_2)modm$

Select$a_1$randomly from$\left[m\right]$ and assume$c=a_1(x_1-y_1)$.

Then$a_2\equiv c.{(y_2-x_2)}^{-1}\mathrm{mod}m$,

Now calculate the probability of selectingso that Equation$\left(1\right)$is true.

Thus$a_2\equiv c.{(y_2-x_2)}^{-1}\mathrm{mod}m$and obviouslycan be any one of the integers in.$\{0,1,\dots ,m-1\}$ That is$a_2$,havepossible values.

Therefore, the probability of equation $\left(1\right)$holds is$\frac{1}{m}$.

Hence it is proved that given family of hash functions,$H$is universal.

Total number of random bits required to select a hash function is2k bits

(b)

Consider a family of hash functions$H=\{h_{a_1,a_2}:a_1,a_2\left[m\right]\}$ and

$\begin{array}{c}{h}_{a_{1,}{a}_2}=\sum _{i=1}^2{a}_i.x_i\mathrm{mod}m\\ =a_1{x}_1+a_2{x}_2\mathrm{mod}m\end{array}$

Where$m=2^k$(That is,$m$is even).

From part (a)$H$,is universal and$(a_1{x}_1+a_2{x}_2)\equiv (a_1{y}_1+a_2{y}_2)\mathrm{mod}m$holds when there exists a unique inverse modulo$m$for $(y_2-x_2)$.

There will be a unique inverse modulo$m$for $(y_2-x_2)$, only if$m$is a prime number.

Since$m=2^k$and it is not a prime number (unless$k=1$), there exist no unique inverse modulo$m$for.

$(y_2-x_2)$

Thus$H$,is not universal.

In order to select a hash function randomly from,$H$ need to select two integers

$a_1$and $a_2$randomly from.$\left[m\right]$ The set $\left[m\right]$has totalintegers.

To uniquely represent each number in set,$\left[m\right]$ at most$\lceil \log m\rceil$bits are required

Where,

$\begin{array}{c}\lceil \log m\rceil bits=\lceil \log 2^k\rceil \\ =kbits\end{array}$.

Since it is required to choose two integers, the total number of random bits required to select a hash function is$2^k$ bits.

mlog(m−1)bits required to choose a function from HH

(c)

Consider a family of hash functions$f:\left[m\right]\to [m-1]$.

In order to prove the above family of hash functions is universal, it is enough to prove that the probability of colliding any two data items$x$and $y$is$\frac{1}{m}-1$, if the hash function is randomly chosen from the family of hash functions. Where$m-1$is the number of buckets.

Assume$x\ne y$and then calculate$P=\mathrm{Pr}[f\left(x\right)=f\left(y\right)]$.

The probability for$f\left(x\right)$ can be any one of integers of$[m-1]$ is$\frac{1}{m-1}$.

Similarly, the probability for$f\left(y\right)$can be any one of integers of $[m-1]$is.$\frac{1}{m-1}$

The probability for the outputs of$f\left(x\right)$and $f\left(y\right)$are same is.data-custom-editor="chemistry" $\frac{1}{m-1}\times \frac{1}{m-1}=\frac{1}{{(m-1)}^2}$

However, there are$m-1$ways to be.$f\left(x\right)=f\left(y\right)$

That is$(f\left(x\right)=0,1,2,\dots ,m-2)=(f\left(y\right)=0,1,2,\dots m-2)$,(total$m-1$ways)

Thus,$P=\sum _{i=1}^{m-1}\frac{1}{{(m-1)}^2}$

or

$\begin{array}{l}P=(m-1)\times \frac{1}{{(m-1)}^2}\\ P=\frac{1}{m-1}\end{array}$

Therefore, it is proved that$H$is universal.

Set $\left[m\right]=\{0,1,2,\dots ,m-1\}$can be mapped to set $[m-1]=\{0,1,2,\dots ,m-2\}$in${(m-1)}^m$ways such that $f$is a function.

Thus, the total number of functions $f:\left[m\right]\to [m-1]$is${(m-1)}^m$.

To uniquely represent each function in$H$, at most $\lceil \log {(m-1)}^m\rceil =m\log (m-1)$bits are required.

Therefore,$m\log (m-1)$bits required to choose a function from$H$.