Lower bounds on $q$-wise independence tails and applications to min-entropy condensers

Maciej SkorskiarXiv 2015 · OpenReview

TL;DR

This paper tightens theoretical bounds on how efficiently we can "condense" randomness. It shows that for certain cryptographic applications like key derivation, the required level of pseudo-randomness in hashing functions is nearly optimal, meaning we can't achieve the same security with significantly less complex (lower $q$-wise independent) hashing.

What Problem Does This Paper Address?

In cryptography, we often need to generate secure keys or other random-looking outputs from sources that have some randomness but aren't perfectly uniform (they have "min-entropy"). This process is called "randomness condensation." A key tool for this is "universal hashing," specifically $q$-wise independent hash functions. A previous result showed that we can condense $k$ bits of min-entropy into a $k$-bit string with very little entropy loss (specifically, $k - \log\log(1/\epsilon)$ bits of entropy, where $\epsilon$ is the acceptable error) using $q$-wise independent hashing with $q = \log(1/\epsilon)$. This is great because it significantly reduces the amount of entropy needed compared to older methods.

However, the previous work only provided a positive result: it showed what is possible. The natural question that arises is: what is the minimum level of $q$-wise independence ($q$) required to achieve a certain level of condensation? Can we get away with less complex hashing functions, or is the $q = \log(1/\epsilon)$ bound essentially necessary? This paper tackles this question by deriving lower bounds on $q$, showing how much independence is required.

Methods

The core of the paper's contribution lies in developing novel anti-concentration inequalities for the "balls and bins" problem, specifically when the number of balls ($M$) equals the number of bins ($N$). They use a clever application of the Paley-Zygmund inequality to analyze higher moments of the "load" in a bin (i.e., how many balls land in a specific bin).

Key techniques include:

  • Explicit representation of load moments: They express the moments of the bin load using Stirling numbers of the second kind. This allows for a more structured analysis.
  • Asymptotic estimates of Stirling numbers: They leverage known results on the growth rates of Stirling numbers and derive bounds for Bell numbers (which are related to Stirling numbers).
  • Paley-Zygmund inequality: This probabilistic tool is used to derive bounds on the probability that a random variable (the bin load) deviates significantly from its expected value.
  • Specialization to $M=N$: The analysis is focused on the scenario where the number of balls equals the number of bins, which is relevant to the min-entropy condenser problem.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Tightness of existing bounds: The paper demonstrates that the parameters used in previous positive results for min-entropy condensers are essentially tight. This means we can't significantly improve the entropy loss or reduce the required independence level without sacrificing security.
  • Necessity of high $q$-independence: The derived lower bounds show that for practical security levels (small $\epsilon$), achieving a certain quality of randomness condensation requires a level of $q$-wise independence that is closely related to the previously established upper bound ($q \approx \log(1/\epsilon)$). This implies that simpler, lower $q$-wise independent hash functions are insufficient for these tasks.
  • Connection between balls-bins and cryptography: The work highlights a deep connection between a fundamental combinatorial problem (balls and bins) and the security of cryptographic primitives like key derivation.
  • Novel anti-concentration technique: The application of the Paley-Zygmund inequality to higher moments of the balls-bins load provides a new tool for analyzing such problems.

Key Results

The paper establishes a lower bound for min-entropy condensers. Specifically, it shows that for a condenser to achieve a certain quality (entropy loss $\ell = \log\log(1/\epsilon) - 3$) with a source of min-entropy $k$ and an error $\epsilon$, the hashing family must be at least $q$-wise independent, where $q = (1-o(1))\log(1/\epsilon)$. This result is asymptotically tight, meaning it closely matches the positive result from prior work that showed $q = \log(1/\epsilon)$ is sufficient.

They also provide explicit, non-asymptotic bounds in terms of Bell numbers and illustrate these with numerical examples.

Limitations and Future Work

  • Asymptotic nature of bounds: While the bounds are shown to be asymptotically tight, the paper acknowledges that better hard bounds can be obtained using their Lemma 1 directly.
  • $M=N$ specialization: The current work focuses on the case where the number of balls equals the number of bins ($M=N$). The authors suggest extending these results to settings where $M > N$ as an open problem.
  • Almost independent hash functions: The paper mentions that practical implementations often use "almost independent" hash functions (which are weaker than $q$-wise independent but have shorter seeds). Extending their methods to analyze these functions is suggested as future work.

Summary updated

Abstract

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 $\epsilon$-close to almost full min-entropy (precisely $ k-\log\log(1/\epsilon)$ bits of entropy) can be achieved by the use of $q$-independent hashing with $q= \log(1/\epsilon)$. We prove that when given a source of min-entropy $k$ and aiming at entropy loss $\ell = \log\log (1/\epsilon) - 3$, the independence level $q=(1-o(1))\log(1/\epsilon)$ is necessary (for small values of $\epsilon$), 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 }
BibTeX
@misc{skorski2015lower,
  author = {Maciej Skorski},
  title = {{Lower bounds on $q$-wise independence tails and applications to min-entropy condensers}},
  year = {2015},
  eprint = {1504.02333},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1504.02333},
}
Figure