# What are the random variables in Universal Hash Function?

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.

• Could you give the link for the definition? – kelalaka Oct 6 '19 at 19:06
• @kelalaka the link is in the text, but here is in plain en.wikipedia.org/wiki/Pairwise_independence – Reza Oct 6 '19 at 19:11
• 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$. – kelalaka Oct 6 '19 at 19:18
• 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. – 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.)
• Thanks! Why do not you consider the $x$ as a random variable? – Reza Oct 6 '19 at 19:49
• 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$). – Squeamish Ossifrage Oct 6 '19 at 19:51
• 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? – Reza Oct 6 '19 at 20:36
• @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!) – Squeamish Ossifrage Oct 6 '19 at 21:24