TAOCP 6.4 Exercise 73
Let $M$ be the range of hash values $\{0,1,\dots,M-1\}$.
Exercise 73. [M26] [M26] (Carter and Wegman.) Show that part (b) of the previous exercise holds even when the h; are not completely random functions, but they have either of the following special forms: (i) Let x; be the binary number (bj(,~1) ...0j1bj0)2. Then hy(@j) = (@j(n, 1)bj(n-1) + +++ + @j1bj1 + aj0bj0) mod M, where each aj, is chosen randomly modulo M. (ii) Let M be prime and assume that 0 < 2; < M. Then hj(x;) = (a;x; + b;) mod M, where a; and b; are chosen randomly modulo M.
Verified: yes
Solve time: 1m12s
Setup
Let $M$ be the range of hash values ${0,1,\dots,M-1}$. A family $H$ of hash functions is universal if for any distinct keys $x \neq y$,
$$ \Pr_{h \in H}[h(x)=h(y)] \le \frac{1}{M}. $$
We verify this property for the two proposed constructions.
Solution
(i) Bitwise linear form
Each key $x$ is a binary vector
$$ x = (b_{n-1},\dots,b_1,b_0), \quad b_k \in {0,1}. $$
Each hash function $h_j$ is defined by random coefficients $a_{jk} \in \mathbb{Z}_M$, chosen independently and uniformly, and
$$ h_j(x) = \left(\sum_{k=0}^{n-1} a_{jk} b_k \right) \bmod M. $$
Fix two distinct keys $x \neq y$, with bit representations $b_k$ and $c_k$. Define
$$ d_k = b_k - c_k \in {-1,0,1}. $$
Since $x \neq y$, there exists at least one index $t$ such that $d_t \neq 0$.
Then
$$ h_j(x) - h_j(y) \equiv \sum_{k=0}^{n-1} a_{jk} d_k \pmod M. $$
Write this sum as
$$ \sum_{k \ne t} a_{jk} d_k + a_{jt} d_t. $$
Let
$$ C = \sum_{k \ne t} a_{jk} d_k \pmod M. $$
The value $C$ depends only on ${a_{jk} : k \ne t}$, hence is independent of $a_{jt}$. The collision condition $h_j(x)=h_j(y)$ is equivalent to
$$ a_{jt} d_t \equiv -C \pmod M. $$
Since $d_t \in {-1,1}$, multiplication by $d_t$ permutes $\mathbb{Z}M$, so this equation has exactly one solution for $a{jt}$ modulo $M$. Because $a_{jt}$ is uniform over $\mathbb{Z}_M$,
$$ \Pr[h_j(x)=h_j(y)] = \frac{1}{M}. $$
(ii) Affine functions modulo a prime
Let $M$ be prime. Each hash function is
$$ h(x) = (ax + b) \bmod M, $$
where $a,b$ are chosen independently and uniformly from ${0,1,\dots,M-1}$.
Fix $x \neq y$. The collision condition is
$$ ax + b \equiv ay + b \pmod M, $$
which reduces to
$$ a(x-y) \equiv 0 \pmod M. $$
Since $M$ is prime and $x-y \not\equiv 0 \pmod M$, the element $x-y$ is invertible modulo $M$, so the condition is equivalent to
$$ a \equiv 0 \pmod M. $$
Among the $M$ equally likely values of $a$, exactly one satisfies this condition. The choice of $b$ does not affect the equality. Hence
$$ \Pr[h(x)=h(y)] = \frac{1}{M}. $$
Verification
In (i), the collision event is reduced to a single modular linear equation in one uniformly distributed coefficient $a_{jt}$, and the remaining coefficients determine a fixed residue class. The probability is determined by the uniform distribution over $\mathbb{Z}_M$, giving exactly one favorable value among $M$.
In (ii), the difference of outputs eliminates $b$, and primality of $M$ ensures that any nonzero factor is invertible. This reduces the condition to a single constraint $a=0$, occurring with probability $1/M$.
Both constructions therefore satisfy the universality condition for every pair of distinct keys.
Conclusion
Both families of hash functions satisfy
$$ \Pr[h(x)=h(y)] \le \frac{1}{M} $$
for all distinct keys $x \neq y$, hence each defines a universal family of hash functions.
This completes the proof. ∎