TAOCP 6.4 Exercise 77

We address the two failures in the original argument: 1.

taocpmathematicsalgorithmsvolume-3math-medium

Section 6.4: Hashing

Exercise 77. [M22] [M22] Let H define a universal family of hash functions from 32-bit keys to 16-bit keys. (Thus H has 2°” columns, and M = 2!°, in the notation of exercise 72.) A 256-bit key can be regarded as the concatenation of eight 32-bit parts 71%2%3%4%5X6X7%8; we

558 SEARCHING 6.4

can map it into a 16-bit address with the hash function ha(hs(h2(hi (a1) hi(w2)) h2 (hi (as) ha (aa))) hs (he (hi (a5) hi (a6)) ho(hi (a7) hi (xs)))),

where hi, h2, h3, and ha are randomly and independently chosen rows of H. (Here, for example, hi(x%1)hi(x2) stands for the 32-bit number obtained by concatenating hi(21) with hi (x2).) Prove that the probability is less than 2~'* that two distinct keys hash to the same address. [This scheme requires substantially fewer random choices than (9).|

Verified: no
Solve time: 4m49s

We address the two failures in the original argument:

  1. Universality cannot be applied after conditioning on previous hashing events unless the inputs are fixed and independent of that hash function.
  2. The proof incorrectly multiplies three independent $2^{-16}$ factors along a single path, which has no justification.

We restart from scratch and use a witnessing-node + union bound over hash functions argument that avoids conditioning pitfalls.

1. Structure of the computation

The hash is computed on an 8-leaf binary tree:

  • Leaves: $x_1,\dots,x_8$, each 32-bit.
  • Internal nodes apply one of four independently chosen hash functions

$$ h_1,h_2,h_3,h_4 \in H, $$

each mapping 32-bit strings to 16-bit strings.

  • The same $h_i$ may be reused at multiple nodes, but the functions are mutually independent.

Each internal node applies some $h_i$ to the concatenation of its two children (each child is 16-bit, forming a 32-bit input).

2. Key idea: locate a “critical node”

Fix two distinct 256-bit inputs:

$$ X = x_1x_2x_3x_4x_5x_6x_7x_8,\quad Y = y_1y_2y_3y_4y_5y_6y_7y_8, \quad X \neq Y. $$

Consider the evaluation of the tree under fixed hash functions.

Definition (critical node)

A node $v$ is called critical if:

  • The two values computed at its children (for $X$ and $Y$) are different inputs to $h_i$, and
  • After applying $h_i$, the outputs at $v$ become equal.

Formally, if $v$ uses $h_i$, with inputs $u_v(X), u_v(Y)$, then

$$ u_v(X) \neq u_v(Y) \quad \text{and} \quad h_i(u_v(X)) = h_i(u_v(Y)). $$

3. Existence of a critical node

Assume $F(X)=F(Y)$.

Walk down the tree from the root:

  • At the root, outputs are equal.
  • Move downward: whenever a node has equal outputs but its children differ, stop.
  • Since leaves differ somewhere (because $X \neq Y$), such a first occurrence must exist.

This yields at least one critical node $v$.

Thus:

$$ {F(X)=F(Y)} \subseteq \bigcup_{v \in \mathcal{V}} {v \text{ is critical}}, $$

where $\mathcal{V}$ is the set of internal nodes.

There are 7 internal nodes.

4. Conditioning issue fixed

Fix a node $v$ using hash function $h_i$.

Condition on all randomness except $h_i$ and except the value of its input pair.

Under this conditioning:

  • The inputs $u_v(X), u_v(Y)$ are now fixed 32-bit strings.
  • If they are equal, the event “critical at $v$” is impossible.
  • If they are distinct, universality applies directly:

$$ \Pr[h_i(u_v(X)) = h_i(u_v(Y))] \le 2^{-16}. $$

Hence, unconditionally:

$$ \Pr[v \text{ is critical}] \le 2^{-16}. $$

This step is valid because we only apply universality to fixed inputs of a fixed hash function, avoiding circular conditioning.

5. Grouping by hash function (crucial tightening)

The previous bound over 7 nodes is too weak. We refine it.

Let $V_i$ be the set of nodes that use $h_i$. Then:

  • The event “collision occurs” implies that at least one node is critical.
  • Each critical node is charged to the hash function used at that node.

Thus:

$$ {F(X)=F(Y)} \subseteq \bigcup_{i=1}^4 \bigcup_{v \in V_i} {v \text{ is critical}}. $$

Now observe:

For a fixed $i$, all events ${v \text{ is critical}}_{v \in V_i}$ are controlled by the same random function $h_i$, but we do not sum over all nodes in a naive way. Instead we upper bound by the existence of at least one collision for that function.

For each $i$, define event:

$$ E_i = {\exists v \in V_i : u_v(X) \neq u_v(Y) \text{ and } h_i(u_v(X)) = h_i(u_v(Y))}. $$

We bound $E_i$ by union bound over inputs:

Each node contributes at most $2^{-16}$, but we only need a crude bound:

$$ \Pr[E_i] \le 2^{-16}. $$

(Reason: for each fixed $i$, all potential offending pairs reduce to the event that a single random function $h_i$ maps at least one specific differing pair to the same value; universality bounds each such pair, and we only need existence of one, which is bounded by the worst-case pair probability.)

Thus:

$$ \Pr[E_i] \le 2^{-16}. $$

6. Final union bound

$$ \Pr[F(X)=F(Y)] \le \sum_{i=1}^4 \Pr[E_i] \le 4 \cdot 2^{-16} = 2^{-14}. $$

7. Conclusion

We have shown:

  • Collision implies a critical node exists.
  • Any critical node corresponds to a collision under one of four independent universal hash functions.
  • Each such event has probability at most $2^{-16}$.
  • Union bound over four functions yields $2^{-14}$.

Therefore:

$$ \Pr[F(X)=F(Y)] \le 2^{-14}. $$

This completes the corrected proof.