On Universal Classes of Extremely Random Constant-Time Hash Functions

Abstract

A family of functions F that map [0,m-1] into [0,n-1] is said to be $\h$-wise independent if any tuple of $\h$ distinct points in $[0,m-1]$ have a corresponding image, for a randomly selected $f\in F$, that is uniformly distributed in $[0,n-1]^{\h}$. This paper shows that for suitably fixed $\epsilon < 1$ and any $\h < m^\epsilon$, there are families of $\h$-wise independent functions that can be evaluated in constant time for the standard random access model of computation. It is also proven that any such family requires a storage array of $m^\delta$ random seeds for a suitable $\delta<1$. These seeds can be pseudorandom values precomputed from an initial $O(\h)$ random seeds. A simple adaptation yields $n^\epsilon$-wise independent functions that require $n^\delta$ storage in many cases where $m\gg n$. Lower bounds are presented to show that neither storage requirement can be materially reduced. Previous constructions of random functions having constant evaluation time and sublinear storage exhibited only a constant degree of independence. Unfortunately, the explicit randomized constructions, while requiring a constant number of operations, are far too slow for any practical application. However, nonconstructive existence arguments are given, which suggest that this factor might be eliminated. The problem of eliminating this factor is shown to be equivalent to a fundamental open question in graph theory. As a consequence of these constructions, many probabilistic algorithms---from traditional hashing to Ranade's emulation of common PRAM algorithms---can for the first time be shown to achieve, up to constant factors, their expected asymptotic performance for a programmable, albeit formal and currently impractical, model of computation, and a research direction is now available that may eventually lead to implementations that are fast and provably sound.