





















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 }
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。