An algorithm has to store several keys generated by an adversary in a hash…
2023
An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let k be the number of keys, m be the number of slots in the hash table, and k>m.
Which one of the following is the best hashing strategy to counteract the adversary?
- A.
Division method, i.e., use the hash function h(k) = k mod m.
- B.
Multiplication method i.e use the hash function h(k)=[m(kA)-kA], where A is a carefully chosen constant.
- C.
Universal hashing method.
- D.
If k is a prime number, use Division method. Otherwise, use Multiplication method.
Attempted by 342 students.
Show answer & explanation
Correct answer: C
Key idea: prevent an adversary from predicting collisions by choosing the hash function at random from a family with low pairwise collision probability.
What universal hashing means: use a family of hash functions H and pick h uniformly at random from H at runtime.
Provable guarantee: for any two distinct keys x and y, Pr[h(x)=h(y)] ≤ 1/m. This holds regardless of how the adversary chooses keys.
Consequence: the expected number of colliding pairs is at most k(k-1)/(2m), so universal hashing minimizes expected collisions even when k>m.
Why other deterministic methods fail: fixed methods like division or multiplication can be anticipated by an adversary, who can then craft many keys that map to the same slot.
Therefore, universal hashing is the best strategy to counteract a malicious adversary who tries to maximize collisions.