Variationally universal hashing

The strongest well-known measure for the quality of a universal hash-function family H is its being ε-strongly universal, which measures, for randomly chosen h∈H, one's inability to guess h(m′) even if h(m) is known for some m≠m′. We give example applications in which this measure is too weak, and we introduce a stronger measure for the quality of a hash-function family, ε-variationally universal, which measures one's inability to distinguish h(m′) from a random value even if h(m) is known for some m≠m′. We explain the utility of this notion and provide an approach for constructing efficiently computable ε-VU hash-function families.