Average Bias and Polynomial Sources

Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka

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

Abstract

We identify a new notion of pseudorandomness for randomness sources, which we call the average bias. Given a distribution $Z$ over $\{0,1\}^n$, its average bias is: $b_{\text{av}}(Z) =2^{-n} \sum_{c \in \{0,1\}^n} |\mathbb{E}_{z \sim Z}(-1)^{\langle c, z\rangle}|$. A source with average bias at most $2^{-k}$ has min-entropy at least $k$, and so low average bias is a stronger condition than high min-entropy. We observe that the inner product function is an extractor for any source with average bias less than $2^{-n/2}$. The notion of average bias especially makes sense for polynomial sources, i.e., distributions sampled by low-degree $n$-variate polynomials over $\mathbb{F}_2$. For the well-studied case of affine sources, it is easy to see that min-entropy $k$ is exactly equivalent to average bias of $2^{-k}$. We show that for quadratic sources, min-entropy $k$ implies that the average bias is at most $2^{-Ω(\sqrt{k})}$. We use this relation to design dispersers for separable quadratic sources with a min-entropy guarantee.
BibTeX
@inproceedings{bhattacharyya2019average,
  author = {Arnab Bhattacharyya and Philips George John and Suprovat Ghoshal and Raghu Meka},
  title = {{Average Bias and Polynomial Sources}},
  booktitle = {Electronic Colloquium on Computational Complexity (ECCC)},
  year = {2019},
  url = {https://openreview.net/forum?id=C1QMFQg1Pl},
}
Figure