Universal Classes of Extremely Random Constant Time Hash Functions and their Time-Space Tradeoff.

摘要

A family of functions F that map [0,n] longmaps to [0,n], is said to be h-wise independent if any h points in [0,n] have an image, for randomly selected f epsilon F, that in uniformly distributed. This paper gives both probabilistic and explicit randomized constructions of n epsilon-wise independent functions, epsilon less than or equal to 1, that can be evaluated in constant time for the standard random access model of computation.