Locally Computable High Independence Hashing

We consider (almost) k-wise independent hash functions, whose evaluations on any k inputs are (almost) uniformly random, for very large values of k. Such hash functions need to have a large key that grows linearly with k. However, it may be possible to evaluate them in sub-linear time by only reading a small subset of t ≪ k locations during each evaluation; we call such hash functions t-local. Local hash functions were previously studied in several works starting with Siegel (FOCS'89, SICOMP'04). For a hash function with n-bit input and output size, we get the following new results:

• There exist (non-constructively) perfectly k-wise independent t-local hash functions with key size O(kn) and locality of t = O(n) bits. An analogous prior result of Larsen et al. (ICALP '24) had a locality of t = O(n) words consisting of w = O(n) bits each, and hence a suboptimal O(n 2 ) bits total. Furthermore, we show that such hash functions could be made explicit if we had explicit optimal constructions of unbalanced bipartite lossless expanders. Plugging in currently best known suboptimal explicit expanders yields correspondingly suboptimal hash functions.

• Perfectly k-wise independent local hash functions generically yield expanders with corresponding parameters. This is true even if the locations accessed by the hash function can be chosen adaptively and shows that progress on explicit hash functions inherently requires progress on explicit expanders.

• We initiate the study of ε-almost k-wise independent hash functions, where any k adaptive queries to the hash function are ε-statistically indistinguishable from k queries to a random function. We construct an explicit family of such hash functions with optimal key size O(kn) bits, optimal locality t = O(n) bits, and ε = 2 -n , significantly improving over the best known parameters for explicit perfectly independent hashing.

• More generally, if we consider a word model with larger word size w, then we get an explicit, efficient construction of ε-almost k-wise independent hash functions with key size O(kn/w) words, locality t = O(n/ √ w) words, and statistical distance ε = 2 -n , which we show to be nearly optimal. Such parameters go beyond what is possible for perfect independence.

We discuss applications to nearly optimal bounded-use information-theoretic cryptography.