Lower bounds on $q$-wise independence tails and applications to min-entropy condensers
This work provides nearly optimal bounds for min-entropy condensers, which are incremental but crucial for cryptographic applications like key derivation.
The paper tackles the problem of mapping balls into bins using q-universal hashing and derives sharp lower bounds for higher load moments, leading to a tight counterpart for min-entropy condensers in key derivation, showing that condensing k bits of min-entropy into a k-bit string with entropy loss log log(1/ε) - 3 requires independence level q = (1-o(1))log(1/ε) for small ε, almost matching prior positive results.
We present novel and sharp lower bounds for higher load moments in the classical problem of mapping $M$ balls into $N$ bins by $q$-universal hashing, specialized to the case when $M=N$. As a corollary we prove a tight counterpart for the result about min-entropy condensers due to Dodis, Pietrzak and Wichs (CRYPTO'14), which has found important applications in key derivation. It states that condensing $k$ bits of min-entropy into a $k$-bit string $ε$-close to almost full min-entropy (precisely $ k-\log\log(1/ε)$ bits of entropy) can be achieved by the use of $q$-independent hashing with $q= \log(1/ε)$. We prove that when given a source of min-entropy $k$ and aiming at entropy loss $\ell = \log\log (1/ε) - 3$, the independence level $q=(1-o(1))\log(1/ε)$ is necessary (for small values of $ε$), which almost matches the positive result. Besides these asymptotic bounds, we provide clear hard bounds in terms of Bell numbers and some numerical examples. Our technique is based on an explicit representation of the load moments in terms of Stirling numbers, some asymptotic estimates on Stirling numbers and a tricky application of the Paley-Zygmund inequality. \keywords{ min-entropy condensers, key derivation, balls and bins hashing, anti-concentration inequalities }