0
$\begingroup$

I'm asked to prove that a family of hash functions is $2$-wise independent. I'm told that: $\mathcal{H}$ is $k$-wise independent if for any $k$ inputs $x_1,...,x_k$ and hash values $v_1,...,v_k$, $\operatorname{Pr}\limits_{h\in \mathcal{H}}\left( \bigwedge\limits_{1\le i\le k}h(x_i)=v_i \right)=m^{-k}$.

I'm just unsure what the notation $\operatorname{Pr}\limits_{h\in \mathcal{H}}$ means. Does it mean for any $h$ taken from $\mathcal{H}$, the probability must be true?

$\endgroup$

1 Answer 1

0
$\begingroup$

This notation just means that $h$ is taken uniformly at random from $\mathcal{H}$. So the expression is essentially saying, "For any $h$ taken uniformly at random from $\mathcal{H}$, the probability that .... = $m^{-k}$".

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .