TL;DR
This paper introduces "average bias," a new measure of randomness for sources that is more sensitive than traditional min-entropy for certain types of sources. They show that low average bias is a stronger condition for extractability and use it to design dispersers for quadratic sources, a class of sources that have been challenging to work with.
What Problem Does This Paper Address?
Extracting randomness from imperfect sources is a fundamental problem in computer science with applications in cryptography, coding theory, and more. Existing methods often rely on the "min-entropy" of a source, which measures the probability of the most likely outcome. However, min-entropy alone isn't always sufficient to guarantee good randomness extraction. For example, sources with high min-entropy can still be difficult to extract from. This paper addresses this gap by introducing a new measure, "average bias," which captures a different aspect of a source's randomness. They then explore the relationship between average bias and min-entropy, particularly for polynomial sources, and leverage this understanding to construct new randomness extractors and dispersers for a challenging class of sources: quadratic sources over finite fields.
Methods
The core of the paper introduces and analyzes the concept of average bias. For a distribution $Z$ over $\{0,1\}^n$, its average bias is defined as $b_{av}(Z) = \mathbb{E}_{c \in \{0,1\}^n} |\mathbb{E}_{z \sim Z}[(-1)^{\langle c, z \rangle}]|$. This is essentially the spectral norm of the probability distribution. The authors then establish key relationships:
- Average Bias vs. Min-Entropy: They prove that if a source $Z$ has average bias at most $2^{-k}$, then its min-entropy is at least $k$. This shows that low average bias is a stronger condition than high min-entropy.
- Extractors for Low Average Bias: They demonstrate that bent functions (a class of highly nonlinear functions) act as extractors for sources with small average bias.
- Quadratic Sources: The main technical contribution is showing that for quadratic sources $P$ over $\mathbb{F}_2^n$, if the min-entropy $H_\infty(P) \ge d$, then the average bias $b_{av}(P) \le 2^{-\Omega(\sqrt{d})}$. This is a significant result because it implies that for quadratic sources, high min-entropy does translate to low average bias, albeit with a weaker guarantee than for affine sources.
- Dispersers for Separable Quadratic Sources: They leverage the average bias-min-entropy relationship for quadratic sources to design dispersers (functions that ensure the output is not constant) for a specific class of quadratic sources called "r-separable quadratic sources."
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Average Bias as a Better Measure: The introduction of average bias provides a more nuanced understanding of randomness sources, especially for structured sources like polynomials. It reveals that some sources with high min-entropy might still have significant "bias" in a different sense, making them unsuitable for extraction.
- Quadratic Sources are More Structured than Arbitrary: The paper shows that while arbitrary sources with high min-entropy might not be extractable, quadratic sources exhibit a structure that allows for randomness extraction if their average bias is low. The relationship $H_\infty(P) \ge d \implies b_{av}(P) \le 2^{-\Omega(\sqrt{d})}$ is crucial here, showing that min-entropy does imply a certain level of low average bias for these sources.
- Bridging the Gap for Quadratic Sources: The work provides a concrete method to construct dispersers for r-separable quadratic sources, a class that was previously difficult to handle. This is achieved by using average bias as an intermediate measure to connect the min-entropy of the source to the rank of its coefficient matrices.
Key Results
- Lemma 1.1: A source with average bias $\le 2^{-k}$ has min-entropy $\ge k$.
- Theorem 1.1: For a quadratic source $P$ over $\mathbb{F}_2^n$, if $H_\infty(P) \ge d$, then $b_{av}(P) \le 2^{-\Omega(\sqrt{d})}$.
- Theorem 1.2: Affine dispersers act as dispersers for r-separable quadratic sources with min-entropy $k > Cr^2 k_{min}$, where $k_{min}$ is the min-entropy of the affine source. This result is instantiated with existing affine extractors to provide dispersers for quadratic sources with polylogarithmic min-entropy.
Limitations and Future Work
- Conjecture 1.5: The authors conjecture that for extracting $m$ uniform bits, the average bias must be $\le \exp(-m)$. Proving this would further solidify the importance of average bias.
- Conjecture 1.6: They hypothesize that for degree-$d$ polynomial sources, $H_\infty(X) \ge k$ implies $b_{av}(X) \le 2^{-f_d(k)}$ for some function $f_d$ depending only on $d$.
- Conjecture 1.7: They believe that affine extractors can be made to act as dispersers for quadratic sources with min-entropy at least $k$, for any $k > 0$.
- General Polynomial Sources: The paper focuses on quadratic sources. Extending the results to higher-degree polynomial sources is a natural next step.
- Extractors for Quadratic Sources: While they design dispersers, constructing explicit extractors for quadratic sources with non-trivial min-entropy guarantees remains an open problem.
Summary updated