Locality of almost k-wise independent local hash functions
A log n gap between what is provably necessary and what is explicitly achieved, at word size 1 and at large word size
Motivation
A local hash function reads only a handful of words of its own key on any one evaluation, which matters wherever the key is huge (as it must be, to get strong independence guarantees) but per-query work has to stay small — for instance, in locally computable, information-theoretically secure one-time authentication and encryption at very high independence. Perfect \(k\)-wise independence forces the key length to grow linearly in \(k\), and Siegel’s classical constructions show locality can be traded against key size along that axis. Almost \(k\)-wise independence — indistinguishable from perfectly independent to any \(k\)-query distinguisher, rather than exactly independent — lets the key length shrink to only logarithmic in \(k\), and the source paper on this hub asks how small the locality (words of the key touched per evaluation) can then be, as a function of the word size \(w\) used to store the key. It answers the question up to a factor of \(\log n\), but only where it has a construction to compare its lower bound against.
Provenance and history
The statement comes from Dodis, Lovett and Wichs, Locally Computable High Independence Hashing (IACR ePrint 2026/622), continuing a line on locally computable independent hashing initiated by Siegel and later advanced by Larsen, Pagh, Persiano, Pitassi, Yeo and Zamir. In the cryptographic regime the source cares about most — input and output both \(n\) bits, independence parameter \(k = \mathrm{poly}(n)\), statistical error \(2^{-n}\) — its Theorem 5.1 proves a locality lower bound of \(\Omega(n/(\sqrt w \log n))\) that holds at every word size \(w\). Matching explicit constructions, achieving \(O(n/\sqrt w)\), are given only at \(w = 1\) (the bit-local case, Theorem 5.7) and at \(w = \Omega(\log^2 n)\) and above (the word-local case, Theorem 5.10); the source’s own summary states the latter needs a “sufficiently large word size.” For word sizes strictly in between, no matching construction — indeed no explicit construction of any kind — is given, and the source records a separate, easier-stated wish to unify its bit-local and word-local constructions into one spanning every word size. Closing the \(\log n\) gap, where a construction exists to compare against, is recorded as its own open problem in the source’s closing section.
Parameter lattice
One axis: word size \(w\). The other: lower bound versus best known explicit construction, both specialized to \(n\)-bit input/output and error \(2^{-n}\).
| Lower bound | Best explicit construction | Gap | |
|---|---|---|---|
| \(w = 1\) (bit-local) | \(\Omega(n/\log n)\), Theorem 5.1 | \(O(n)\), Theorem 5.7 | c/0066 — \(\Theta(\log n)\), open |
| \(w = \Omega(\log^2 n)\) up to \(n^2\) (word-local) | \(\Omega(n/(\sqrt w \log n))\), Theorem 5.1 | \(O(n/\sqrt w)\), Theorem 5.10 | c/0066 — \(\Theta(\log n)\), open |
| \(2 \le w = o(\log^2 n)\) | \(\Omega(n/(\sqrt w \log n))\), Theorem 5.1 | unstated: no matching construction is given at all | not comparable; the subject of the source’s separate unification remark, not of this hub’s statement |