Premium
Dispersing hash functions
Author(s) -
Pagh Rasmus
Publication year - 2009
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20257
Subject(s) - hash function , computer science , computer security
We define a family of functions F from a domain U to a range R to be dispersing if for every set S ⊆ U of a certain size and random h ∈ F , the expected value of ∣ S ∣ – ∣ h [ S ]∣ is not much larger than the expectation if h had been chosen at random from the set of all functions from U to R . We give near‐optimal upper and lower bounds on the size of dispersing families and present several applications where using such a family can reduce the use of random bits compared to previous randomized algorithms. A close relationship between dispersing families and extractors is exhibited. This relationship provides good explicit constructions of dispersing hash functions for some parameters, but in general the explicit construction is left open. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009