Abstract
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.