Universal hash function is defined as follow:

$f_{(k_0,k_1)}(x) = (k_0\cdot x + k_1) \mod p$, where $p$ is prime

In Wikipedia, it is mentioned that the above function is pairwise independent. Pairwise independence is defined here

I wonder what are the random variables in $f$ and what pairwise independence means here.

  • $\begingroup$ Could you give the link for the definition? $\endgroup$ – kelalaka Oct 6 '19 at 19:06
  • $\begingroup$ @kelalaka the link is in the text, but here is in plain en.wikipedia.org/wiki/Pairwise_independence $\endgroup$ – Reza Oct 6 '19 at 19:11
  • $\begingroup$ This is in Universal_hashing . Carter and Wegman; $h_{a,b}(x) = ((a \cdot x +b) \bmod p) \bmod m $ where $a , b$ are randomly chosen integers modulo $p$ with $a \neq 0$. $\endgroup$ – kelalaka Oct 6 '19 at 19:18
  • $\begingroup$ please include the definition in the question itself for improved readability. after all you are asking others to put in an effort to answer your question. $\endgroup$ – kodlu Oct 6 '19 at 21:26

The random variables are $k_0$ and $k_1$, typically taken to be uniformly distributed in $\mathbb Z/p\mathbb Z$ in this context.

(Sometimes we take $k_0$ to be uniform in $(\mathbb Z/p\mathbb Z)^\times$ instead, i.e. exclude $k_0 = 0$, but as long as $p \gg 2^{100}$ this is not important.)

| improve this answer | |
  • $\begingroup$ Thanks! Why do not you consider the $x$ as a random variable? $\endgroup$ – Reza Oct 6 '19 at 19:49
  • 1
    $\begingroup$ The defining property of a universal hash family is a bound on the collision probability $\Pr[H(x) = H(y)]$ for all $x \ne y$. That is, there's a for all quantifier on $x$ and $y$, but a probability quantifier on the hash function $H$ (or, equivalently, over the internal parameters $k_0$ and $k_1$). $\endgroup$ – Squeamish Ossifrage Oct 6 '19 at 19:51
  • $\begingroup$ So, why $f_{(k_0,k_1)}(x) = (k_0\cdot x + k_1) \mod p$ is a pairwise independent but $f_{(k_0,k_1)}(x) = (k_0\cdot x \cdot k_1)$ is not? $\endgroup$ – Reza Oct 6 '19 at 20:36
  • $\begingroup$ @Reza $f_{(k_0,k_1)}(x) = (k_0 \cdot x \cdot k_1) \bmod p$ is equivalent to $g_{k_0\cdot k_1}$ where $g_k(x) = k\cdot x \bmod p$. Suppose you know what $g_k(x)$ is; can you deduce, then, what $g_k(y)$ is? If you can, is it possible for $g$ to be pairwise independent? (Remember what the definition of pairwise independence is!) $\endgroup$ – Squeamish Ossifrage Oct 6 '19 at 21:24

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.