2
$\begingroup$

How to prove that a $k$-universal family of hash functions is $(k-1)$-universal family?

I tried to prove it by definition of k-universal family of hash functions but I didn't know how to use the definition.

If I prove it, Is it necessary that a $1$-universal family of hash function is universal family?

Definitions:

Let $U$ be a universe of keys, and let $H$ be a finite collection of hash functions mapping $U$ to $\{0,\dots,m-1\}$.

$H$ is universal if $\forall x,y\in U$ where $x\neq y$: $\Pr[h(x)=h(y)] \leq \frac{1}{m}$ where $h$ is chosen randomly from $H$.

$H$ is k-universal if $\forall x_1,x_2,\dots,x_k\in U$ distinct elements and $\forall i_1,i_2,\dots,i_k\in \{0,\dots,m-1\}$: $\Pr[h(x_1)=i_1 \land h(x_2)=i_2 \land \dots \land h(x_k)=i_k] = \frac{1}{m^k}$ where $h$ is chosen randomly from $H$.

$\endgroup$
2
$\begingroup$

For your first question, here is a hint: $$ \Pr[h(x_1) = i_1 \land \cdots \land h(x_{k-1}) = i_{k-1}] = \\ \sum_{i_k} \Pr[h(x_1) = i_1 \land \cdots \land h(x_{k-1}) = i_{k-1} \land h(x_k) = i_k]. $$

Regarding the connection between universal and $k$-universal: Consider the family consisting of all constant functions. This family is 1-universal but not universal (for $|U|>1$).

However, it turns out that every 2-universal family is universal (exercise). The converse isn't true: for example, the family of all functions $h$ such that $h(x_1) = 0$ is universal but not 2-universal (for $m>1$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.