[Math] If k-universal hash family then (k-1)-universal hash family

hash functionprobability

A family of hash functions $H = \{h: U \rightarrow \{1, \ldots , m\}\}$ is called k-universal (or k-independent) if for every distinct $\{x_1, \ldots, x_k \} \in U$ keys and for every $\{i_1, \ldots, i_k\} \in \{1,\ldots,m \}$ values (not necessarily distinct) we have that for a randomly chosen $h \in H$, we get $Pr[h(x_1) = i_1 \land \cdots \land h(x_k)=i_k] = \frac{1}{m^k}$.

Prove that a k universal hash family is also (k-1) universal.

Best Answer

We'll prove that every $k$-universal family is $k-1$-universal. We'll notice that \begin{align} Pr[h(x_1) = i_1 &\land \cdots \land h(x_{k-1}) = i_{k-1}] \\&= Pr[h(x_1)=i_1 \land \cdots \land h(x_{k-1})=i_{k-1}\land h(x_k)=1] \\&+ Pr[h(x_1)=i_1 \land \cdots \land h(x_{k-1})=i_{k-1}\land h(x_k)=2]+\ldots \\&+Pr[ h(x_1)=i_1 \land \cdots \land h(x_{k-1})=i_{k-1}\land h(x_k)=m] \\&= \frac{1}{m^k}+\frac{1}{m^k}+\ldots +\frac{1}{m^k}=\frac{m}{m^k}=\frac{1}{m^{k-1}} \end{align}

The last equality is because the family is $k$-universal.

Related Question