Why use universal hashing instead of fixed hash functions?
Universal hashing involves selecting a hash function at random from a designated family rather than relying on a single fixed function. This randomized approach guarantees a low expectation of collisions, protecting data structures like hash tables even when inputs are manipulated by an adversary. It is widely applied across computer science, randomized algorithms, and cryptography.
What we know
- Universal hashing selects a hash function at random from a family of hash functions possessing a specific mathematical property. [1, 2]
- The method guarantees a low number of collisions in expectation, even if the input data is intentionally chosen by an adversary. [1, 2]
- Universal families exist for various data types including integers, vectors, and strings, and their evaluation is often very efficient. [2]
- Universal hashing is utilized in diverse computer science applications such as hash table implementations, randomized algorithms, and cryptography. [2]
Where to go next
- the bigger pictureHow does k-independent hashing work?
- compared withWhat is a cryptographic hash function?
- a case in pointWhat are universal one-way hash functions in cryptography?
- what followedHow do hash table collisions cause denial-of-service attacks?
- how it workedHow are universal hash families evaluated efficiently?
- an unexpected connectionHow do universal hash functions secure digital signatures?Specialized universal hash functions like UOWHFs can be used to build digital signature schemes without requiring trapdoor functions.
Sources
- [1]universal hashing (Wikidata Q846912) · CC0 1.0
- [2]Universal hashing · CC BY-SA 4.0
- [3]Cryptographic hash function · CC BY-SA 4.0
- [4]Universal one-way hash function · CC BY-SA 4.0
- [5]K-independent hashing · CC BY-SA 4.0