Section 6.4: Hashing

Exercise 78. [M26] [M26] (P. Woelfel.) If 0 < 2 < 2”, let hao(x) = [(ax + b)/2"| mod 2"-*. Show that the set {ha | 0 <a < 2", a odd, and 0

Verified: yes
Solve time: 4m06s

Let $w>m>0$, $L=2^{w-m}$, and work modulo $2^w$. The hash family is

$$ h_{a,b}(x)=\Big\lfloor \frac{ax+b}{2^{w-m}} \Big\rfloor \bmod 2^m, $$

where $a$ is odd and $b$ is uniform in $\mathbb Z_{2^w}$.

We prove that for any $x\neq y$,

$$ \Pr_{a,b}[h_{a,b}(x)=h_{a,b}(y)] \le 2^{-m}. $$

Step 1: Reduction to a random shift

Fix $x\neq y$. For any fixed odd $a$, set

$$ t \equiv a(x-y) \pmod{2^w}, \quad t\neq 0, $$

since multiplication by an odd $a$ is a permutation of $\mathbb Z_{2^w}$.

Let

$$ z \equiv ax+b \pmod{2^w}. $$

As $b$ is uniform over $\mathbb Z_{2^w}$, so is $z$. Moreover,

$$ ay+b \equiv z-t \pmod{2^w}. $$

Thus, conditioning on $a$, the collision event becomes

$$ h_{a,b}(x)=h_{a,b}(y) \quad\Longleftrightarrow\quad \Big\lfloor \frac{z}{L} \Big\rfloor

\Big\lfloor \frac{z-t}{L} \Big\rfloor, $$

where $z$ is uniform over $\mathbb Z_{2^w}$.

It remains to bound, for fixed $t\neq 0$,

$$ \Pr_z!\left[\Big\lfloor \frac{z}{L} \Big\rfloor

\Big\lfloor \frac{z-t}{L} \Big\rfloor\right]. $$

Step 2: Decompose into blocks and analyze carries

Write each $z\in \mathbb Z_{2^w}$ uniquely as

$$ z = kL + u, \quad 0\le k < 2^m,; 0\le u < L. $$

Write

$$ t = qL + r, \quad 0\le q < 2^m,; 0\le r < L. $$

Then subtraction modulo $2^w$ has the form

$$ z-t = (kL+u) - (qL+r). $$

There are two cases depending on whether a borrow occurs.

Case 1: $u \ge r$

No borrow occurs from the low part, so

$$ z-t = (k-q)L + (u-r), $$

hence

$$ \Big\lfloor \frac{z-t}{L} \Big\rfloor = k-q \pmod{2^m}. $$

For equality of hash values we need

$$ k \equiv k-q \pmod{2^m} ;;\Longrightarrow;; q \equiv 0 \pmod{2^m}. $$

Since $0\le q<2^m$, this forces $q=0$.

Thus in Case 1, collisions occur only when $q=0$ and $u\ge r$.

Case 2: $u < r$

A borrow occurs, so

$$ z-t = (k-q-1)L + (u+L-r), $$

and hence

$$ \Big\lfloor \frac{z-t}{L} \Big\rfloor = k-q-1 \pmod{2^m}. $$

Equality requires

$$ k \equiv k-q-1 \pmod{2^m} ;;\Longrightarrow;; q+1 \equiv 0 \pmod{2^m}. $$

Since $0\le q<2^m$, this forces $q=2^m-1$.

Thus in Case 2, collisions occur only when $q=2^m-1$ and $u<r$.

Step 3: Exact counting

We now count the number of $z$ satisfying the collision condition.

Subcase A: $q=0$

Then only Case 1 is possible, and we need $u\ge r$. For each of the $2^m$ values of $k$, there are exactly $L-r$ valid values of $u$. Hence

$$ N = 2^m(L-r). $$

Subcase B: $q=2^m-1$

Then only Case 2 is possible, and we need $u<r$. For each $k$, there are exactly $r$ valid values of $u$. Hence

$$ N = 2^m r. $$

Subcase C: all other $q$

No solutions exist, so $N=0$.

Step 4: Probability bound

In all cases,

$$ N \le 2^m L = 2^w. $$

More precisely, in the only cases that matter,

$$ N \in {2^m(L-r),, 2^m r}. $$

Thus the collision probability is

$$ \Pr[h_{a,b}(x)=h_{a,b}(y)\mid a] = \frac{N}{2^w} \le \frac{2^m L}{2^w} = \frac{2^m \cdot 2^{w-m}}{2^w} = 2^{-m}. $$

Step 5: Remove conditioning on $a$

The bound is independent of the choice of odd $a$, so averaging over $a$ preserves it: