Variationally Universal Hashing

Authors: Ted Krovetz and Phillip Rogaway

Reference: Information Processing Letters, vol. 100, no. 1, pp. 36-39, 2006.

Abstract: The strongest well-known measure for the quality of a universal hash-function family is its being ε-strongly universal (ε-SU). We give an example application in which this measure is too week, and we introduce a stronger measure for the quality of a hash-function family, ε-variationally universal (ε-VU). We explain the utility of this notion and provide an approach for constructing efficient ε-VU hash-function families.

Availability: pdf

Rogaway's home page.