Question

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 \bmod m$.
• B. Multiplication method, i.e., use the hash function $h(k) = \lfloor m(kA - \lfloor kA \rfloor) \rfloor$, 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.

Hint:

When facing adversarial key generation in hashing, use universal hashing}. Randomization ensures that the adversary cannot predict collisions, unlike deterministic methods.

Answer 1

The Correct Option is C

Step 1: Recall the problem.
The adversary is generating keys maliciously, with the intention of maximizing collisions in the hash table. Thus, a deterministic hash function (like division or multiplication method) can be exploited by the adversary.
Step 2: Why division and multiplication fail.
- Division method: $h(k) = k \bmod m$ is predictable. An adversary can easily choose keys that collide modulo $m$.
- Multiplication method: Though better, it is still deterministic and predictable if the adversary knows the constant $A$.
Step 3: Advantage of universal hashing.
Universal hashing selects a hash function randomly from a family of hash functions. Since the adversary cannot predict which function will be used, they cannot deliberately choose colliding keys. This minimizes the expected number of collisions.
Step 4: Conclusion.
Universal hashing is the best strategy against an adversary trying to maximize collisions, because it introduces randomness and unpredictability in hash function selection. \[ \boxed{\text{Universal hashing method is the best choice.}} \]