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

To effectively address the problem of storing keys in a hash table where a malicious adversary tries to maximize collisions, it's important to understand different hashing strategies and their capabilities to minimize such collisions.

1. Division Method:
   • This method uses the hash function h(k) = k \bmod m.
   • It is simple and efficient for evenly distributing keys when m is chosen as a prime number.
   • However, an adversary can exploit this method by selecting keys that cause collisions, especially if the modulus m is not carefully chosen.
2. Multiplication Method:
   • This method uses the hash function h(k) = \lfloor m(kA - \lfloor kA \rfloor) \rfloor, where A is a constant.
   • It tends to distribute keys more uniformly compared to division, due to its dependence on constant A which is carefully chosen.
   • However, its effectiveness against a malicious adversary ultimately depends on the choice of A.
3. Universal Hashing Method:
   • Universal hashing is a strategy where the hash function is randomly chosen from a class of functions with certain properties.
   • It provides a strong guarantee that the average performance across different hash functions is good, reducing the risk of collisions, even with an adversarial key selection.
   • In a universal hash family, the probability of a collision is minimized making it robust against adversaries.
   • This method is particularly effective in scenarios where the adversary knows the hash function in advance.
4. Conditional Use of Division/Multiplication:
   • This approach suggests using the division method if k is a prime number; otherwise, using the multiplication method.
   • While this could reduce collisions for specific cases, it doesn't offer a robust strategy against a determined adversary who knows the method in advance.

After evaluating these options, the Universal Hashing method is the most effective strategy under adversarial conditions because:

• It minimizes the expected number of collisions by randomly selecting hash functions, thus effectively neutralizing the adversarial threat.
• This unpredictability ensures that the adversary cannot consistently predict inputs that will result in collisions.

Therefore, the correct answer is: Universal hashing method.