patternMinor
Universal Hashing in Practice
Viewed 0 times
hashinguniversalpractice
Problem
A family $H$ of hash functions $h: U \rightarrow \{0,\ldots,M-1\}$ is universal if
$$\forall x,y \in U, x \neq y \Rightarrow \Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{M}$$
You can find more about universal hashing this wikipedia article.
The concept of universal hashing is now a standard part of undergraduate data structure courses. It would be nice to be able to motivate students about the importance of universal hashing in industrial applications. So my question is:
Are constructions of universal family of hash functions important in practice? If the answer is yes, would you please share some interesting industrial applications that you've seen?
$$\forall x,y \in U, x \neq y \Rightarrow \Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{M}$$
You can find more about universal hashing this wikipedia article.
The concept of universal hashing is now a standard part of undergraduate data structure courses. It would be nice to be able to motivate students about the importance of universal hashing in industrial applications. So my question is:
Are constructions of universal family of hash functions important in practice? If the answer is yes, would you please share some interesting industrial applications that you've seen?
Solution
Universal hashing (or near-universal) is a key ingredient in defending against algorithmic complexity attacks that engineer hash table collisions from user input.
See Scott A. Crosby and Dan S. Wallach's "Denial of Service via Algorithmic Complexity Attacks".
See Scott A. Crosby and Dan S. Wallach's "Denial of Service via Algorithmic Complexity Attacks".
Context
StackExchange Computer Science Q#16118, answer score: 4
Revisions (0)
No revisions yet.