Bit-Fixing Extractors for Almost-Logarithmic Entropy

Doron, Dean; Fridman, Ori

doi:10.4230/LIPIcs.APPROX/RANDOM.2025.33

Bit-Fixing Extractors for Almost-Logarithmic Entropy

Dean Doron

Ben-Gurion University of the Negev, Beer-Sheva, Israel Ori Fridman

Ben-Gurion University of the Negev, Beer-Sheva, Israel

Abstract

An oblivious bit-fixing source is a distribution over $\left\{{0,1}\right\}^{n}$ , where $k$ bits are uniform and independent and the rest $n-k$ are fixed a priori to some constant value. Extracting (close to) true randomness from an oblivious bit-fixing source has been studied since the 1980s, with applications in cryptography and complexity theory.

We construct explicit extractors for oblivious bit-fixing source that support $k=\widetilde{O}(\log n)$ , outputting almost all the entropy with low error. The previous state-of-the-art construction that outputs many bits is due to Rao [Rao, CCC ’09], and requires entropy $k\geq\log^{c}n$ for some large constant $c$ . The two key components in our constructions are new low-error affine condensers for poly-logarithmic entropies (that we achieve using techniques from the nonmalleable extractors literature), and a dual use of linear condensers for OBF sources.

Keywords and phrases:

Seedless extractors, oblivious bit-fixing sources

Category:

RANDOM

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Expander graphs and randomness extractors

Acknowledgements:

We thank Jesse Goodman for many helpful and interesting conversations, and Mahdi Cheraghchi for helpful discussion on the cryptographic applications of OBF extractors.

Funding:

The work is supported in part by NSF-BSF grant #2022644.

DOI:

10.4230/LIPIcs.APPROX/RANDOM.2025.33

Event:

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Editors:

Alina Ene and Eshan Chattopadhyay

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Whenever randomness is used in computations–whether because it is necessary or just because it is faster and simpler in practice, access to unbiased bits is assumed. Because sources of perfect randomness are notoriously hard to come by, ad hoc, very weak sources of randomness are used instead. It is essential, therefore, that the crude randomness generated by such sources be purified, thus driving the development of the beautiful theory of randomness extractors. This problem of extracting randomness from imperfect sources can be traced back to von Neumann [54]. A randomness extractor is a deterministic procedure that converts a weak random source into a random source that is close to uniform.

Definition 1 (seedless extractor).

Let $\mathcal{X}$ be a family of distributions over $\left\{{0,1}\right\}^{n}$ . We say that $\mathsf{Ext}\colon\left\{{0,1}\right\}^{n}\rightarrow\left\{{0,1}\right\}^{m}$ is an extractor for $\mathcal{X}$ with error $\varepsilon$ , if for every $X\in\mathcal{X}$ , $\mathsf{Ext}(X)$ is $\varepsilon$ -close, in total variation distance, to $U_{m}$ , the uniform distribution over $m$ bits.

One common assumption is that each weak source $X\in\mathcal{X}$ has min-entropy.¹¹1We say that $X\sim\left\{{0,1}\right\}^{n}$ has min-entropy $k$ , $H_{\infty}(X)\geq k$ , if $\max_{x\sim X}\Pr[X=x]\leq 2^{-k}$ . We call such $X$ an $(n,k)$ source. Unfortunately, if all we assume is an entropy guarantee, it is easy to show that such an $\mathsf{Ext}$ does not exist. However, seedless extraction is possible for some restricted classes of sources,²²2To extract from general $(n,k)$ sources, one can use an additional short uniform seed, driving the rich theory of seeded extractors. See Definition 8 for the definition. and indeed, studying the capabilities and limitations of extraction from natural families of structured sources has been a fruitful endeavor for the past four decades (see [27, Section 1.3] for a comprehensive up-to-date survey of seedless extraction results).

One of the simplest and most natural families of weak sources of randomness is oblivious bit fixing sources, wherein $k$ bits are uniform and independent, while the rest $n-k$ bits are fixed.

Definition 2 (OBF source).

A distribution $X\sim\left\{{0,1}\right\}^{n}$ is an $(n,k)$ oblivious bit-fixing source if there exists a subset $I\subseteq[n]$ of size $k$ of “good indices”, such that the $\left\{{X_{i}}\right\}_{i\in I}$ -s are uniform and independent, and the rest are fixed.³³3To clarify the terminology, the word “oblivious” refers to the fact that the fixed bits are chosen before the random bits are tossed. On the other hand, in nonoblivious bit fixing sources, the non-uniform bits can depend arbitrarily on the values of the good ones (see Section 3.4).

In addition to simulating true randomness, extractors have been found to be useful, even essential, in myriad applications, and extractors for oblivious bit-fixing sources are no exception.

In cryptography, especially in exposure resilient cryptography (see, e.g., [21]), there are several related primitives for which OBF extractors are useful. (Cryptographic) resilient functions (and almost perfect resilient functions) are essentially OBF extractors, possibly under a different choice of error measure [6, 53]. Exposure resilient functions are a weaker variant, wherein the security is guaranteed only on average over the uniform bits [9]. Both primitives are useful for wiretap protocols, where two parties wish to agree on a random string in the presence of an adversary that can learn some of the transmitted bits. Another related notion is that of all-or-nothing transforms, used for protection of block ciphers [49, 32, 21, 22] (see also [15], and the discussion in [15, Appendix A]). OBF extractors were also used for distributed generation of correlated randomness [23]. Outside of cryptography, OBF extractors have also found applications in complexity theory, mainly for lower bounds [35, 14].

Previous constructions

Extractors for OBF sources were first studied by Chor, Goldreich, Håstad, Freidmann, Rudich, and Smolensky [17] in the zero-error setting (indeed, this is one of the rare examples in which outputting exactly uniform bits is possible). They observed that the simple XOR function outputs a uniform bit for any $k\geq 1$ , but also proved that $k\geq n/3$ is necessary even for the $m=2$ case. More generally, via establishing connections to error correcting codes, Chor et al. showed that when $k=n-t$ , we can (explicitly) extract $m\approx n-t\log(n/t)$ bits, but cannot extract more than, roughly, $n-(t/2)\log(n/t)$ bits. Further lower bounds in this regime were obtained by Friedman [24].

What if we allow error, and wish to support lower entropies? Kamp and Zuckerman were the first to go below linear entropy, achieving $k\geq n^{1/2+\gamma}$ and $m=\Omega(n^{2\gamma})$ , with error $\varepsilon=2^{-\Omega(m)}$ . The entropy loss in the [34] construction was later improved by Gabizon, Raz, and Shaltiel [26], who achieved $m=(1-o(1))k$ and exponentially-small error. Gabizon et al. were also able to reduce the entropy down to $k\geq{\rm poly}(\log n)$ , but with a worse error of $k^{-\Omega(1)}$ . But often, especially in cryptographic applications, a large error is prohibitive. The first low-error OBF extractor for poly-logarithmic entropy was constructed by Rao [47], outputting $m=(1-o(1))k$ bits with error $2^{-k^{\Omega(1)}}$ . We will further discuss Rao’s construction in Section 2.1.

For even lower entropies, recent explicit constructions that support near-logarithmic entropy already work for the more general family of affine sources.⁴⁴4An $(n,k)$ affine source is a distribution that is flat over some affine subspace of $\mathbb{F}_{2}^{n}$ of dimension $k$ . Thus, an $(n,k)$ OBF source is simply an affine source whose basis consists of only elementary vectors. Using techniques from the nonmalleable extractors literature, Chattopadhyay, Goodman, and Liao [10] achieved $k=\widetilde{O}(\log n)$ , and this was later improved by a recent work of Li [44] that gets $k=O(\log n)$ . Unfortunately, the latter two constructions work for constant error and one output bit, which is not relevant for OBF extractors. However, one can think of applying techniques similar to the ones in [50, 42]. But these, to the best of our knowledge, do not readily give a significant improvement on either $m$ or $\varepsilon$ .

Lastly, it is interesting to note that while a straightforward application of the probabilistic method gives a non-explicit construction for (roughly) $k\geq\log n+2\log(1/\varepsilon)$ and $m=k-2\log(1/\varepsilon)$ , logarithmic entropy is not a lower bound. In [34], they gave a construction that outputs only $\Omega(\log k)$ bits, has error $k^{-\Omega(1)}$ , but works for any $k$ . In [20], Cohen and Shinkar gave a lower bound for extraction, and showed that when $k$ is a small enough function of $n$ , $\Omega(\log k)$ output bits are all we can hope for. Moreover, they gave a “semi-explicit” construction, when the error is large enough, for sub-logarithmic entropy. Their construction supports $k=\Omega(\log\log n)$ , outputs $m=k-O_{\varepsilon}(1)$ bits, and runs in time $2^{\widetilde{O}_{\varepsilon}(\log n)}$ .

Our result

We give an explicit low-error construction for $k\geq\widetilde{O}(\log n)$ that outputs almost all the entropy.

Theorem 3 (see also Theorem 24).

There exist constants $c>1$ and $\beta\in(0,1)$ such that the following holds for any $n\in\mathbb{N}$ and $k\geq\log n\cdot(\log\log n)^{c}$ . There exists an explicit function

\mathsf{OBFExt}\colon\left\{{0,1}\right\}^{n}\rightarrow\left\{{0,1}\right\}^{% m=(1-o(1))k}

that is a $(k,\varepsilon)$ extractor for OBF sources, where $\varepsilon=2^{-(k/\log n)^{\beta}}$ .

While the error guarantee does not meet the optimal $2^{-\Omega(k)}$ (or even $2^{-k^{\Omega(1)}}$ ), both our construction and [47] achieve $\varepsilon=n^{-\omega(1)}$ starting from $k={\rm poly}(\log n)$ . Importantly, our construction is the first to extract almost all the entropy with vanishing error starting from $k=\widetilde{O}(\log n)$ . In particular, our error guarantee surpasses a $k^{-\Omega(1)}$ -type dependence for all ranges of $k$ .

The low-error challenge

The recent decade has seen exciting progress in extractors that support small entropies, most notably in constructions of two-source extractors⁵⁵5A two-source extractor for entropy $k$ extracts from the family of sources $\mathcal{X}$ in which each $X\in\mathcal{X}$ comprises two independent sources $(X_{1},X_{2})\sim\left\{{0,1}\right\}^{n}\times\left\{{0,1}\right\}^{n}$ , each $X_{i}$ satisfies $H_{\infty}(X_{i})\geq k$ . ([13, 4, 19, 43, 44]), and the use of similar techniques to construct affine extractors [42, 10, 44]. While these extractors, which generally follow the celebrated Chattopadhyay–Zuckerman framework [13], work for low entropies, their error is relatively high for reasons which will be discussed in Section 2.2. Low-error constructions are crucial for the security of cryptographic applications, as well as for good correlation bounds in lower bounds applications, but despite numerous attempts, recent constructions do not obtain negligible error in polynomial time.⁶⁶6For two-source extractors, the best low-error constructions require $k\geq(1/2-\alpha)n$ for a small constant $\alpha>0$ [8, 36], whereas the [13] construction gets $k={\rm poly}(\log n)$ with $\varepsilon=k^{-\Omega(1)}$ , and followup constructions for even lower entropies only work for constant error. For affine extractors, the best low-error constructions require $k=\omega(n/\log\log n)$ [55, 37, 45], whereas, again, recent constructions in the near-logarithmic regime only work for constant error. It is worth noting that if one allows three independent sources, then efficient low-error three-source extractors exist already for poly-logarithmic min-entropy [40, 3].

Our construction uses key components of the [13] framework (mainly towards constructing new low-error affine condensers, see Section 2.2), and is able to outperform the error parameter in most related constructions. We thus view this work also as a proof-of-concept for utilizing more recent machinery to tackle low-error constructions.

2 Proof Overview

Our construction combines two new components: A low-error affine condenser with a small gap, and a dual use of linear condensers for OBF sources. In Section 2.1, we will revisit Rao’s construction [47] and his use of linear condensers for OBF sources. In Section 2.2, we will discuss the [13] framework, the low-error adaptation of [3] to two-source condensers, and our construction of affine condensers. In Section 2.3, we will give the full construction, after discussing our use of linear condensers for OBF sources.

2.1 Rao’s Construction

Given an $(n,k)$ OBF source $X$ , Rao’s construction [47] goes roughly as follows.⁷⁷7The [47] construction works not only for OBF sources, but more generally to low-weight affine sources. Our result captures low-weight affine sources as well, and we discuss this in Section 5.3.

1.

Transform $X$ into $X^{\prime}=P\cdot X$ , where $P$ is a linear transformation, $X^{\prime}$ is much shorter than $X$ , yet it preserves the entropy of $X$ . Thus, this step can be seen as applying a linear condenser for OBF sources, and we discuss this step a bit more thoroughly below. Note that $X^{\prime}$ is an affine source.
2.

Transform $X^{\prime}$ into an affine somewhere-random source. This is a source distributed over a table, where one row is uniform, and every other row depends on the uniform one in an affine way. $Z$ has few rows, $k^{\Omega(1)}$ , but the length of each row is almost $k$ . This transformation is done via applying a (linear) seeded extractor on $X^{\prime}$ and every possible seed, i.e., $Z_{i}=\mathsf{Ext}(X^{\prime},i)$ .⁸⁸8More accurately, to make each row longer than $k^{\Omega(1)}$ , Rao injects more entropy to the table by performing an additional extraction step, this time with $X$ itself as the source, and $Z_{i}$ as the seed. This is the part that requires $X$ to have poly-logarithmic entropy.
3.

Next, extract from $Z$ . This step is done via repeatedly applying an affine somewhere-random condenser, that halves the number of rows in the table, while only shortening each row by a little bit.

Our construction makes use of Step (1) (in fact, more than once, see Section 2.3), and completely dispenses with Step (3). In our construction, once we have our table $Z$ from Step (2), we condense it into a single string using a different mechanism. This is encapsulated under a new affine condenser, which we discuss soon in Section 2.2.

Linear Condensers for OBF Sources

In [47], Rao observed that parity check matrices of binary error correcting codes are good linear condensers for OBF sources, and low-weight affine sources in general.⁹⁹9It is interesting to note that relying on the distance property of error correcting codes alone cannot give optimal linear OBF condensers. One can show that there exist condensers with output length $t=O(k)$ . Specifically, let $P\in\mathbb{F}_{2}^{n\times t}$ be the parity check matrix of a linear code $\mathcal{C}\subseteq\mathbb{F}_{2}^{n}$ with co-dimension $t$ and distance $k+1$ (see Section 3.5 for the relevant definitions). Then, given an $(n,k)$ OBF source $X$ , the affine source $P\cdot X\sim\mathbb{F}_{2}^{t}$ still has entropy $k$ (see Lemma 22 for the easy proof).

This (lossless) condensing allows Rao, and us, to apply affine primitives on sources of much shorter lengths. Indeed, working with BCH codes, one can get $t=O(k\log n)$ .¹⁰¹⁰10[47] uses an error correcting code that comes from small-bias sets, and achieves a worse distance-to-codimension tradeoff. In fact, for our construction, BCH codes are necessary. In our construction, we will also use a lossy instantiation of these linear OBF condensers, where $t\ll k$ . We discuss this further in Section 2.3.

2.2 Low-Error Affine Condensers

The [13] Framework

We start by briefly describing the [13] framework, originally geared towards obtaining an extractor for two independent sources. The CZ construction uses two main ingredients: A “correlation breaking” primitive,¹¹¹¹11The idea of constructing extractors via correlation breaking appeared prior to [13], notably in [38, 39, 41, 18]. and a resilient function. For the former, we will consider here a $t$ -correlation breaker with advice,¹²¹²12The actual definition offers much more flexibility than what we describe here, but it suffices for this discussion. Also, the original CZ construction uses non-malleable extractors as the correlation breaking primitive, but there are known reductions between the two objects. which is a function $\mathsf{CB}\colon\left\{{0,1}\right\}^{n}\times\left\{{0,1}\right\}^{d}% \rightarrow\left\{{0,1}\right\}^{m}$ that takes inputs from a weak source $X_{1}$ , a uniform seed $Y$ , and a fixed advice string $\alpha$ , and the guarantee is that

\mathsf{CB}\left(X_{1},Y,\alpha\right)\approx U_{m}\nobreak\ \Big|\nobreak\ % \left\{{\mathsf{CB}\left(X_{1},Y^{(1)},\alpha^{(1)}\right),\ldots,\mathsf{CB}% \left(X_{1},Y^{(t)},\alpha^{(t)}\right)}\right\},

where $Y^{(1)},\ldots,Y^{(t)}$ are independent of $X_{1}$ , and the $\alpha^{(i)}$ -s are all different from $\alpha$ . Roughly speaking, for a typical $y\sim Y$ , $\mathsf{CB}(X_{1},y,\alpha)$ is close to uniform even given the value of $\mathsf{CB}$ on $t$ other adversarially chosen $y^{(i)}$ -s. Hence, if we were to build a table with $D=2^{d}$ rows, and put, say, $\mathsf{CB}(X_{1},i,i)$ in the $i$ -th row, then rows of good seeds were not only close to uniform, but they’re also close to being $t$ -wise independent.

Yet, there are no one-source extractors, and [13] need to use a second weak source $X_{2}$ to sub-sample from the seeds of $\mathsf{CB}$ . Specifically, take a seeded extractor $\mathsf{Ext}\colon\left\{{0,1}\right\}^{n}\times\left\{{0,1}\right\}^{d_{0}}% \rightarrow\left\{{0,1}\right\}^{d}$ ,¹³¹³13See Definition 8 for the formal definition. and consider the table $Z$ with $r=2^{d_{0}}\ll D$ rows, in which each row is given by

Z_{i}=\mathsf{CB}\left(X_{1},\mathsf{Ext}(X_{2},i),i\right).

(1)

An analogous way to view the construction of $Z$ , which would be more beneficial towards our construction, is to first create the table with $r$ rows wherein the $i$ -th row is simply $\mathsf{Ext}(X_{2},i)$ . While most of the rows in that table are marginally close to uniform, they are arbitrarily correlated. We then use $\mathsf{CB}$ with an independent source $X_{1}$ to (partially) break correlations.¹⁴¹⁴14This viewpoint was taken, e.g., in [18, 42, 5].

It turns out that $Z$ itself, when the parameters are set correctly, is close to a table in which $r-q$ “good” rows are truly $t$ -wise independent, and there are $q$ “bad” rows that can depend arbitrarily on the good ones. Indeed, many constructions following [13] can also be divided into two steps, where the first one transforms $X_{1}$ and $X_{2}$ into $Z=Z(X_{1},X_{2})$ with the above structure, known as a non-oblivious bit-fixing source, and the second one, which we now discuss, is where resilient functions comes into play.

Concisely, a resilient function $f\colon\left\{{0,1}\right\}^{r}\rightarrow\left\{{0,1}\right\}$ is an extractor for non-oblivious bit fixing sources. That is, we want a nearly-balanced $f$ whose output cannot be heavily influenced by any small set of $q$ bad bits (we’re considering $m=1$ for now), and in our case $f$ needs to be resilient even when the good bits are only $t$ -wise independent (and uniform), unlike the more standard case in which the good bits are completely independent. The second step of the CZ framework then amounts to applying a resilient function on $Z$ , outputting $W=f(Z)$ .

While this beautiful approach does give us that $W\approx_{\varepsilon}U_{1}$ , it is inherently bound to have runtime which is polynomial in $1/\varepsilon$ . The Kahn–Kalai–Linial theorem [33] tells us that no matter what $f$ is, there will always be a single bad bit that has influence $p=\Omega(\log r/r)$ , i.e., with probability $p$ over the good bits, the single corrupt bit can fully determine the result.¹⁵¹⁵15In terms of explicit $f$ -s, [13] derandomized the Ajtai-Linial [1] randomized construction, supporting $q=r^{1-\delta}$ for any constant $\delta>0$ . In a subsequent work, Meka [46] obtained a derandomized version of [1] that matches the randomized construction and can support $q=O\left(\frac{r}{\log^{2}r}\right)$ bad bits (see also [30, 31] for followup constructions with smaller bias). Thus, the running time, which is at least $r$ , is also at least $1/\varepsilon$ . This is a common feature of almost all constructions that follow the CZ approach.

The [3] Low-Error Adaptation

In [3], Ben-Aroya, Cohen, Doron, and Ta-Shma, evaded the above resilient functions barrier by aiming for a weaker object – a two source condenser. Namely, the output $W$ is not $\varepsilon$ -close to uniform, but $\varepsilon$ -close to some random variable $W^{\prime}\sim\left\{{0,1}\right\}^{m}$ that has min-entropy $m-g$ , where we call $g$ the entropy gap (note that an extractor has gap $g=0$ ). While when $m=1$ , a single malicious bit can bias the result pretty significantly, the key observation in [3] is that when $m$ becomes large, the probability that the bad bits can reduce $g$ bits of entropy from the output can be exponentially-small in $g$ . We call such a function $f_{\mathsf{s}}\colon\Sigma^{r}\rightarrow\Sigma$ , $\Sigma=\left\{{0,1}\right\}^{m}$ , an entropy-resilient function, which is essentially a condenser for non-oblivious symbol-fixing sources (that is, the natural extension of bit-fixing sources to arbitrary alphabets). In [3], they constructed an explicit such $f_{\mathsf{s}}$ , and were able to conclude that $W=f_{\mathsf{s}}(Z)$ is $\varepsilon$ -close to having gap $g=o(\log(1/\varepsilon))$ provided that $k$ is at least polynomial in $\log(n/\varepsilon)$ , and $m=k^{\Omega(1)}$ . Importantly, the construction’s runtime is polynomial in $n$ , and not in $1/\varepsilon$ .

Teleporting to the affine setting

Starting from the work of Li [42], and throughout a sequence of followup works [11, 10, 12, 44], the correlation breaking framework was used to extract from affine sources and other related families of weak sources such as sumset sources, small-space sources, and interleaved sources. While in the affine case we don’t have two sources at our disposal, our single source has structure we can utilize.

Specifically, recall our table $\left\{{\mathsf{Ext}(X,i)}\right\}_{i\in[r]}$ above, and assume that $\mathsf{Ext}$ is linear, meaning that for any fixed seed, the output is a linear function of the source. Here too, our table has many good rows (in fact, the good rows are exactly uniform), but they are, again, arbitrarily correlated. It turns out that we can use the same source $X$ to break the correlation and make the table close to a $t$ -non-oblivious bit-fixing source. This heavily uses the (by now) standard “affine conditioning” technique (see Lemma 7), in which given a linear function $L\colon\left\{{0,1}\right\}^{n}\rightarrow\left\{{0,1}\right\}^{m}$ , we can decompose $X=A+B$ , where both $A$ and $B$ are affine, and there is a bijection between $A$ and $L(X)$ , and $B$ is independent of $L(X)$ .¹⁶¹⁶16In our case, the function $L$ is chosen according to our linear seeded extractor $\mathsf{Ext}$ , and in fact bundles up $t$ of them. For a more detailed description of the correlation breaking mechanism, see, for example, [42]. Conveniently, the intricate correlation breaking constructions for linearly-correlated source and seed was made explicit in [12], coined affine correlation breakers. The state-of-the-art affine correlation breakers follow from a recent work of Li [44] (see Definitions 13 and 14).

Our Low-Error Affine Condenser

Armed with a low-error two-source condenser, and a method to adapt the two-source setting to the affine world, a low-error affine condenser follows rather easily. Consider the table $Z$ from Equation 1, but this time we form it as follows:

Z_{i}=\mathsf{AffCB}\left(X,\mathsf{LExt}(X,i),i\right),

(2)

where $\mathsf{AffCB}$ is an affine correlation breaker, and $\mathsf{LExt}$ is a linear seeded extractor. We then output

W=f_{\mathsf{s}}(Z),

where $f_{\mathsf{s}}$ is the above entropy resilient function. We can then show that if our affine source $X\sim\mathbb{F}_{2}^{n}$ has at least $k\geq{\rm poly}(\log(n/\varepsilon))$ entropy, $W\sim\left\{{0,1}\right\}^{k^{\Omega(1)}}$ is $\varepsilon$ -close to having entropy gap $o(\log(1/\varepsilon))$ . This is precisely a condensing guarantee, and the formal construction is given in Section 4.

2.3 Our OBF Extractor

Equipped with a linear condenser for OBF sources $P$ , and a low-error affine condenser for poly-logarithmic entropies $\mathsf{AffCond}$ , one natural attempt would be to try and output

\mathsf{LExt}\left(X,\mathsf{AffCond}\left(P(X)\right)\right),

where $\mathsf{LExt}$ is a linear seeded extractor. Note that $P(X)$ is a short affine source with entropy $k$ , so the entropy lower bound of $\mathsf{AffCond}$ is now much lower! There are three potential problems with the above construction:

1.

We want $\mathsf{AffCond}$ to supply the seed for $\mathsf{LExt}$ , but $Y=\mathsf{AffCond}\left(P(X)\right)$ is not uniform – it is only $\varepsilon$ -close to having some entropy gap $g$ . But since $g$ is tiny, we can in fact use $Y$ as a seed, suffering only a small loss in the error. (This observation is by now standard.)
2.

$X$ has length $n$ , and we don’t have linear seeded extractors outputting many bits with optimal seed length. In particular, the entropy in $Y$ cannot be greater than $k$ , but all known extractors require seed $\gg\log^{2}n$ .

To try and resolve the issue, one may change the construction to $\mathsf{LExt}\left(P(X),\mathsf{AffCond}\left(P(X)\right)\right)$ , thereby only working with the short $P(X)$ . Even then, we are still left with the challenge of handling the correlations between the source and the seed.
3.

Indeed, $Y$ depends on $P(X)$ (or $X$ ) – it’s a deterministic function of it! As mentioned above, we will use the affine conditioning technique in order to handle the correlations. We decompose $X=A+B$ , where $A$ and $B$ are affine and independent, $A$ is a deterministic function of $P(X)$ , and $B$ is independent of $P(X)$ .

Morally, after an appropriate “fixing”, the source we use for $\mathsf{LExt}$ is the affine source $B$ . But we can only guarantee that $H_{\infty}(B)\geq k-|P(X)|$ , which provides no useful bound if we want to retain most of the entropy of $X$ .

In order to make $X$ shorter and guarantee that some entropy is left even after the affine conditioning, we make use of linear OBF condensers in two ways:

\mathsf{OBFExt}(X)=\mathsf{LExt}\left(P_{1}(X),\mathsf{AffCond}\left(P_{2}(X)% \right)\right)

Above,

$\blacksquare$

$P_{1}$ is a lossless condenser for OBF sources, mapping $n$ bits to $n^{\prime}=O(k\log n)$ bits.
$\blacksquare$

$P_{2}$ is a lossy condenser for OBF sources, mapping $n$ bits to $\gamma k$ bits for a small $\gamma\in(0,1)$ , while retaining $k^{\prime}\approx\frac{k}{\log n}$ entropy. We construct $P_{2}$ using error correcting codes as well, only with different parameters.

For $\mathsf{AffCond}$ to condense, we need $k^{\prime}\geq{\rm poly}(\log(n^{\prime}/\varepsilon))$ , and this sets our lower bound on $k$ and the bound on the error.

Finally, we need to show that we can apply $\mathsf{LExt}$ . Towards this end, we “affine condition” with respect to $P_{2}(X)$ , and so we can write

\mathsf{OBFExt}(X)=\mathsf{LExt}(P_{1}(A),Y)+\mathsf{LExt}(P_{1}(B),Y),

(3)

where $Y=\mathsf{AffCond}(P_{2}(X))$ , $A$ and $B$ are independent, and $P_{2}(X)$ is a deterministic function of $A$ . Thus, $B$ and $Y$ are also independent, and furthermore, $B$ still has enough entropy. This, in turn, implies that $P_{1}(B)$ has enough entropy, and we can safely fix a good seed $y\sim Y$ , making the first term in Equation 3 fixed, and the second one close to uniform. The full details appear in Section 5.2.

3 Preliminaries

We use $\log(x)$ for $\log_{2}(x)$ . For an integer $n$ , we denote by $[n]$ the set $\left\{{1,\ldots,n}\right\}$ . The density of a subset $B\subseteq A$ is denoted by $\mu(B)=\frac{|B|}{|A|}$ . For a function $f\colon\Omega_{1}\rightarrow\Omega_{2}$ , we say that $f$ is explicit if there exists a deterministic procedure that runs in time ${\rm poly}(\log(|\Omega_{1}|))$ and computes $f$ .

Random variables, entropy

The support of a random variable $X$ distributed over some domain $\Omega$ is the set $x\in\Omega$ for which $\Pr[X=x]\neq 0$ , which we denote by $\mathrm{Supp}(X)$ . The total variation distance (or, statistical distance) between two random variables $X$ and $Y$ over the same domain $\Omega$ is defined as $|X-Y|=\max_{A\subseteq\Omega}(\Pr[X\in A]-\Pr[Y\in A])$ . Whenever $|X-Y|\leq\varepsilon$ we say that $X$ is $\varepsilon$ -close to $Y$ and denote it by $X\approx_{\varepsilon}Y$ . We denote by $U_{n}$ the random variable distributed uniformly over $\left\{{0,1}\right\}^{n}$ . We say a random variable is flat if it is uniform over its support. Whenever we write $x\sim A$ for $A$ being a set, we mean $x$ is sampled uniformly at random from the flat distribution over $A$ .

For a function $f\colon\Omega_{1}\rightarrow\Omega_{2}$ and a random variable $X$ distributed over $\Omega_{1}$ , $f(X)$ is the random variable distributed over $\Omega_{2}$ obtained by choosing $x$ according to $X$ and computing $f(x)$ . For a set $A\subseteq\Omega_{1}$ , $f(A)=\left\{{f(x):x\in A}\right\}$ . For every $f\colon\Omega_{1}\rightarrow\Omega_{2}$ and two random variables $X$ and $Y$ distributed over $\Omega_{1}$ it holds that $|f(X)-f(Y)|\leq|X-Y|$ , and is often referred to as a data-processing inequality. Another property of statistical distance is the triangle inequality, which states that for all distributions $X, Y, Z$ , we have $|X-Y|\leq|X-Z|+|Y-Z|$ .

The min-entropy of $X$ is defined by

H_{\infty}(X)=\min_{x\in\mathrm{Supp}(X)}\log\frac{1}{\Pr[X=x]},

and it always holds that $H_{\infty}(X)\leq H(X)$ , where $H()$ is Shannon’s entropy. A random variable $X$ is an $(n,k)$ source if $X$ is distributed over $\left\{{0,1}\right\}^{n}$ and has min-entropy at least $k$ .

Limited Independence

We say that a distribution $X\sim\left\{{0,1}\right\}^{n}$ is $(t,\gamma)$ -wise independent, if the restriction of $X$ to any $t$ coordinates is $\gamma$ -close to $U_{t}$ . When $\gamma=0$ , we simply say that $X$ is $t$ -wise independent.

Lemma 4 ([2]).

Let $X\sim\left\{{0,1}\right\}^{n}$ be $(t,\gamma)$ -wise independent. Then, $X$ is $(n^{\gamma}t)$ -close to a $t$ -wise independent distribution.

3.1 OBF and Affine Sources

We repeat the definition of affine and OBF sources.

Definition 5 (affine source).

An $(n,k)$ affine source is a distribution $X\sim\mathbb{F}_{2}^{n}$ that is flat over some (unknown) affine subspace of dimension $k$ .

In other words, for any such $X$ there exist independent $v_{0},v_{1},\ldots,v_{k}\in\mathbb{F}_{2}^{n}$ such that sampling $x\sim X$ amounts to sampling $\alpha_{1},\ldots,\alpha_{k}\sim\mathbb{F}_{2}$ uniformly at random, and outputting $x=v_{0}+\sum_{i=1}^{k}\alpha_{i}v_{i}$ . Notice that when $X$ is affine, $H_{\infty}(X)=H(X)$ .

Definition 6 (OBF source).

An $(n,k)$ oblivious bit-fixing (OBF) source is a distribution $X\sim\left\{{0,1}\right\}^{n}$ for which there exists an (unknown) subset $I\subseteq[n]$ of size $k$ , and $c\in\left\{{0,1}\right\}^{n-k}$ , such that $X_{I}=U_{k}$ , and $X_{[n]\setminus I}$ is fixed to $c$ .

In other words, a bit-fixing source is a very structured affine source – one in which $v_{1},\ldots,v_{k}$ are indicator vectors. The following lemma will let us use linearly-correlated source and seed when using linear seeded extractors.

Lemma 7 (affine conditioning, [25, 47, 37]).

Let $X$ be an $(n,k)$ affine source, and let $L\colon\left\{{0,1}\right\}^{n}\rightarrow\left\{{0,1}\right\}^{m}$ be a linear function. Then, there exist independent affine sources $A$ and $B$ , over $\left\{{0,1}\right\}^{n}$ , such that:

$\blacksquare$

$X=A+B$ .
$\blacksquare$

There exists $c\in\left\{{0,1}\right\}^{m}$ such that for every $b\in\operatorname{Supp}(B)$ it holds that $L(b)=c$ .
$\blacksquare$

$H(A)=H(L(A))$ and there exists an affine function $L_{\mathsf{inv}}\colon\left\{{0,1}\right\}^{n}\rightarrow\left\{{0,1}\right\}^% {m}$ such that $A=L_{\mathsf{inv}}(L(A))$ . In particular, $H(A)\leq m$ and $H(B)\geq k-m$ .
$\blacksquare$

For every $\ell\in\operatorname{Supp}(L(X))$ , $H(X|\left\{{L(X)=\ell}\right\})=H(B)$ .

3.2 Seeded Extractors

Definition 8 (seeded extractor).

A function $\mathsf{Ext}\colon\left\{{0,1}\right\}^{n}\times\left\{{0,1}\right\}^{n}% \rightarrow\left\{{0,1}\right\}^{m}$ is a $(k,\varepsilon)$ (seeded) extractor if for every $(n,k)$ source and an independent and uniform $Y\sim\left\{{0,1}\right\}^{d}$ , it holds that $\mathsf{Ext}(X,Y)\approx_{\varepsilon}U_{m}$ . Furthermore, we say that $\mathsf{Ext}$ is strong if $\left(\mathsf{Ext}(X,Y),Y\right)\approx_{\varepsilon}(U_{m},Y)$ .

We say that $\mathsf{Ext}$ is linear if it is linear in the source, namely if for any $x_{1},x_{2}\in\left\{{0,1}\right\}^{n}$ and $y\in\left\{{0,1}\right\}^{d}$ , it holds that $\mathsf{Ext}(x_{1}+x_{2},y)=\mathsf{Ext}(x_{1},y)+\mathsf{Ext}(x_{2},y)$ .

Combining a (linear variant) of the GUV seeded condenser [28, 16] with the Shaltiel–Umans extractor [51], we can get the following logarithmic-seed linear seeded extractor, that outputs a constant power of the entropy.

Theorem 9 (linear seeded extractor, I [42]).

There exists a constant $c_{1}$ such that the following holds, for any positive integers $n$ and $c_{1}\log^{8}n\leq k\leq n$ , and any $\varepsilon\geq n^{-2}$ . There exists an explicit linear strong $(k,\varepsilon)$ extractor $\mathsf{LExt}_{1}\colon\left\{{0,1}\right\}^{n}\times\left\{{0,1}\right\}^{d}% \rightarrow\left\{{0,1}\right\}^{m}$ with $d=c_{1}\cdot\log n$ and $m=\sqrt{k}$ .

Replacing the SU extractor with Trevisan’s extractor [52], as analyzed in [48], we can output almost all the entropy, at the cost of a larger seed.

Theorem 10 (linear seeded extractor, II).

There exists a constant $c_{2}$ such that the following holds, for any positive integers $n$ and $k\leq n$ , and any $\varepsilon,\gamma>0$ . There exist an explicit linear strong $(k,\varepsilon)$ extractor $\mathsf{LExt}_{2}\colon\left\{{0,1}\right\}^{n}\times\left\{{0,1}\right\}^{d}% \rightarrow\left\{{0,1}\right\}^{m}$ where $m=(1-\gamma)k$ and

d=c_{2}\cdot\left(\log n+\log^{2}k\cdot\log(1/\varepsilon)\cdot\log(1/\gamma)% \right).

We omit the easy proof, which is similar to the proof of Theorem 9 in [42].

When the extractor is linear and the source is affine, a good seed already implies perfect uniformity, for any nontrivial error.

Lemma 11 ([47]).

Let $\mathsf{LExt}\colon\left\{{0,1}\right\}^{n}\times\left\{{0,1}\right\}^{d}% \rightarrow\left\{{0,1}\right\}^{m}$ be a linear strong $(k,\varepsilon)$ extractor with $\varepsilon<1/2$ . Then, for every $(n,k)$ affine source, it holds that

\Pr_{y\sim U_{d}}[|\mathsf{LExt}(X,y)-U_{m}|=0]\geq 1-2\varepsilon.

We will also need the following claim, that is often used when one wishes to use seeded extractors with a non perfect seed.

Claim 12 (strong extractors with weak seeds).

Let $\mathsf{Ext}\colon\left\{{0,1}\right\}^{n}\times\left\{{0,1}\right\}^{d}% \rightarrow\left\{{0,1}\right\}^{m}$ be a strong $(k,\varepsilon)$ extractor, let $X$ be an $(n,k)$ source, and let $Y$ be $\delta$ -close to a $(d,d-g)$ source which is independent of $X$ . Then, with probability at least $1-2^{g}\sqrt{\varepsilon}-\delta$ over $y\sim Y$ , it holds that $\mathsf{Ext}(X,y)\approx_{\sqrt{\varepsilon}}U_{m}$ .

Proof.

By Markov’s inequality, there exists a set ${\rm BAD}\subseteq\left\{{0,1}\right\}^{d}$ of density $\rho({\rm BAD})\leq\sqrt{\varepsilon}$ such that for every $z\notin{\rm BAD}$ it holds that $\mathsf{Ext}(X,z)\approx_{\sqrt{\varepsilon}}U_{m}$ . Let $Y^{\prime}$ be a $(d,d-g)$ source that is $\delta$ -close to $Y$ . Then,

	$\displaystyle\Pr[Y\in{\rm BAD}]$	$\displaystyle\leq\Pr[Y^{\prime}\in{\rm BAD}]+\delta$
		$\displaystyle=\sum_{z\in{\rm BAD}}\Pr[Y^{\prime}=z]+\delta\leq\|{\rm BAD}\|\cdot 2% ^{-(d-g)}+\delta\leq 2^{g}\sqrt{\varepsilon}+\delta.\$

$\hfill\vartriangleleft$

3.3 Affine Correlation Breakers

We proceed with formally defining affine correlation breakers (with advice).

Definition 13 (affine correlation breaker).

We say that $\mathsf{AffCB}\colon\left\{{0,1}\right\}^{n}\times\left\{{0,1}\right\}^{d}% \times\left\{{0,1}\right\}^{a}\rightarrow\left\{{0,1}\right\}^{m}$ is a $(t,k,\varepsilon)$ affine correlation breaker if for all distributions $X,X^{(1)},\ldots,X^{(t)}\sim\left\{{0,1}\right\}^{n}$ , $B,B^{(1)},\ldots,B^{(t)}\sim\left\{{0,1}\right\}^{n}$ , $A,A^{(1)},\ldots,A^{(t)}\sim\left\{{0,1}\right\}^{n}$ , $Y,Y^{(1)},\ldots,Y^{(t)}\sim\left\{{0,1}\right\}^{d}$ , and all strings $\alpha,\alpha^{(1)},\ldots,\alpha^{(t)}\in\left\{{0,1}\right\}^{a}$ such that:

$\blacksquare$

$X=A+B$ and $X^{(i)}=A^{(i)}+B^{(i)}$ for all $i\in[t]$ ,
$\blacksquare$

$H_{\infty}(B)\geq k$ and $Y$ is uniform,
$\blacksquare$

$\left(B,B^{(1)},\ldots,B^{(t)}\right)$ is independent of $\left(A,A^{(1)},\ldots,A^{(t)},Y,Y^{(1)},\ldots,Y^{(t)}\right)$ , and,
$\blacksquare$

For all $i\in[t]$ , $\alpha\neq\alpha^{(i)}$ ,

it holds that

\left(\mathsf{AffCB}(X,Y,\alpha),\left\{{\mathsf{AffCB}\left(X^{(i)},Y^{(i)},% \alpha^{(i)}\right)}\right\}_{i\in[t]}\right)\approx_{\varepsilon}\left(U_{m},% \left\{{\mathsf{AffCB}\left(X^{(i)},Y^{(i)},\alpha^{(i)}\right)}\right\}_{i\in% [t]}\right).

We say that $\mathsf{AffCB}$ is strong if the above holds also when we add $Y,Y^{(1)},\ldots,Y^{(t)}$ .

We will use the following recent affine correlation breaker.

Theorem 14 ([44]).

For any positive integers $n, m, t, a$ , and any $\varepsilon>0$ , there exists an explicit strong $(t,k,\varepsilon)$ affine correlation breaker $\mathsf{AffCB}\colon\left\{{0,1}\right\}^{n}\times\left\{{0,1}\right\}^{d}% \times\left\{{0,1}\right\}^{a}\rightarrow\left\{{0,1}\right\}^{m}$ , where $k=O\left(tm+ta+t^{2}\log^{2}(t+1)\log(nt/\varepsilon)\right)$ and $d=O\left(m+ta+t\log^{3}(t+1)\log(nt/\varepsilon)\right)$ .

3.4 Entropy-Resilient Functions

We summarize the required definitions and results given in [3].

Definition 15 (NOSF sources).

Let $\Sigma=\left\{{0,1}\right\}^{m}$ . A $(q,t)$ non-oblivious $\Sigma$ -fixing source $X=(X_{1},\ldots,X_{D})$ is a random variable over $\Sigma^{D}=\left\{{0,1}\right\}^{Dm}$ for which there exists a set ${\rm BAD}\subseteq[D]$ of cardinality $q^{\prime}\leq q$ such that:

$\blacksquare$

The joint distribution of $\left\{{(X_{i})_{j}:i\in[D]\setminus{\rm BAD},j\in[m]}\right\}$ , denoted by $G_{X}$ , is $t$ -wise independent over $\left\{{0,1}\right\}^{(D-q^{\prime})m}$ ; and
$\blacksquare$

Each of the random variables in $B_{X}\triangleq\left\{{(X_{i})_{j}}\right\}$ with $i\in{\rm BAD}$ and $j\in[m]$ may depend arbitrarily on all other random variables in $G_{X}$ and $B_{X}$ .

If $t=(D-q^{\prime})m$ , we say that $X$ is a $q$ -non-oblivious $\Sigma$ -fixing source. If $m=1$ , the definition coincides with the standard definition of non-oblivious bit-fixing sources.

In [3], Ben-Aroya et al. constructed seedless condensers for NOSF sources, also known as entropy-resilient functions.

Definition 16 (entropy-resilient functions).

Let $\Sigma=\left\{{0,1}\right\}^{m}$ . A function $f\colon\Sigma^{D}\to\Sigma$ is a $(q,t,g,\varepsilon)$ entropy-resilient function if for every $(q,t)$ non-oblivious $\Sigma$ -fixing source $X$ over $\Sigma^{D}$ , the output $f(X)$ is $\varepsilon$ -close to an $(m,m-g)$ -source.

Theorem 17 ([3]).

For every constant $0<\gamma<1$ there exist constants $0<\alpha<1$ and $c^{\prime}\geq 1$ such that the following holds. For all integers $D$ , $m\leq D^{\alpha/2}$ , every $\varepsilon>0$ , and for every integer $t\geq m\cdot(\log D)^{c^{\prime}}$ , there exists an explicit function $\mathsf{EntRes}\colon\Sigma^{D}\to\Sigma$ , for $\Sigma=\left\{{0,1}\right\}^{m}$ , that is $(q=D^{1-\gamma},t,g,\varepsilon)$ entropy-resilient, with entropy gap $g=o(\log(1/\varepsilon))$ .

3.5 Error Correcting Codes

A binary code $\mathcal{C}\subseteq\mathbb{F}_{2}^{n}$ is linear if $\mathcal{C}$ is a linear subspace of $\mathbb{F}_{2}^{n}$ . The dimension of $\mathcal{C}$ as a subspace is called the dimension of the code. We will identify a linear code $\mathcal{C}\subseteq\mathbb{F}_{2}^{n}$ of dimension $k$ with the image of its encoding function $\mathcal{C}\colon\mathbb{F}_{2}^{k}\rightarrow\mathbb{F}_{2}^{n}$ , which is given by a generator matrix $A\in\mathbb{F}_{2}^{n\times k}$ . A parity check matrix of $\mathcal{C}$ is a generator matrix $P\in\mathbb{F}_{2}^{(n-k)\times n}$ of the dual code $\mathcal{C}^{\perp}=\left\{{x\in\mathbb{F}_{2}^{n}:\langle x,c\rangle=0% \nobreak\ \forall c\in\mathcal{C}}\right\}$ , and thus $Px=0$ if and only if $x\in\mathcal{C}$ .

We say that an error correcting code $\mathcal{C}\subseteq\mathbb{F}_{2}^{n}$ has distance $d$ if for any distinct codewords $x,y\in\mathcal{C}$ it holds that $x_{i}\neq y_{i}$ in at least $d$ $i$ -s. We say that $\mathcal{C}$ is an $[n,k,d]$ code, if $\mathcal{C}\subseteq\mathbb{F}_{2}^{n}$ is a linear code of dimension $k$ and distance $d$ . We will use the following explicit code, the BCH code.

Theorem 18 ([7, 29]).

There exists a constant $c>0$ such that the following holds. For every positive integers $n$ and $d<n$ , there exists an $[n,r,d]$ code $\mathcal{C}_{\mathsf{BCH}}$ with co-dimension $n-r=\lfloor c\log n\rfloor\cdot d$ .¹⁷¹⁷17The original BCH code assumes $n=2^{m}-1$ for some integer $m$ , and then $n-r\leq\frac{md}{2}$ . Standard manipulations let us work for any $n$ . Moreover, the parity-check matrix of $\mathcal{C}_{\mathsf{BCH}}$ can be constructed in time ${\rm poly}(n)$ .

4 Low-Error Affine Condensers

In this section, we give our construction of low-error affine condensers with tiny entropy gap.

Theorem 19.

There exist universal constants $c\geq 1$ and $\alpha\in(0,1)$ such that the following holds. For any positive integers $n, k$ , and any $\varepsilon>0$ such that $n\geq k\geq\log^{c}\left(\frac{n}{\varepsilon}\right)$ , there exists an explicit function $\mathsf{AffCond}\colon\left\{{0,1}\right\}^{n}\rightarrow\left\{{0,1}\right\}^% {m}$ where $m\geq k^{\alpha}$ such that for any $(n,k)$ affine source $X$ , it holds that $\mathsf{AffCond}(X)$ is $\varepsilon$ -close to an $(m,m-g)$ source, where $g=o(\log(1/\varepsilon))$ .

We will start by reducing an affine source to a non-oblivious symbol-fixing (NOSF) source.

Lemma 20.

There exist constants $c,c_{1}>1$ such that the following holds, for any positive integers $n, t, m, k$ , and any $\varepsilon>0$ , satisfying $k\geq\left(mt\log(n/\varepsilon)\right)^{c}.$ There exists an explicit function $\mathsf{AffToNOSF}\colon\left\{{0,1}\right\}^{n}\rightarrow\Sigma^{D}$ with $\Sigma=\left\{{0,1}\right\}^{m}$ and $D=n^{c_{1}}$ such that for every $(n,k)$ affine source $X$ , $\mathsf{AffToNOSF}(X)$ is $\varepsilon$ -close to a $(D^{1-1/c_{1}},t)$ NOSF source.

Proof.

We use the following two building blocks.

$\blacksquare$

Let $\mathsf{LExt}\colon\left\{{0,1}\right\}^{n}\times\left\{{0,1}\right\}^{d_{0}}% \rightarrow\left\{{0,1}\right\}^{d}$ be the linear strong $(k_{\mathsf{Ext}},\varepsilon_{\mathsf{Ext}}=1/2n)$ extractor given by Theorem 9, where $k_{\mathsf{Ext}}=d^{2}\geq c_{1}\log^{8}n$ , for $c_{1}$ being the constant given in Theorem 9. Note that we can take $d_{0}=c_{1}\cdot\log n$ .
$\blacksquare$

Let $\mathsf{AffCB}\left\{{0,1}\right\}^{n}\times\left\{{0,1}\right\}^{d}\times% \left\{{0,1}\right\}^{d_{0}}\rightarrow\left\{{0,1}\right\}^{m}$ be the $(t-1,k_{\mathsf{CB}}=k-td,\varepsilon_{\mathsf{CB}})$ affine correlation breaker of Theorem 14 with $\varepsilon_{\mathsf{CB}}=\frac{\varepsilon}{t(mD)^{tm}}$ , and

$d=O\left(m+td_{0}+t\log^{3}(t+1)\log(nt/\varepsilon_{\mathsf{CB}})\right)=O% \left(t^{5}m\log n+t^{4}\log(1/\varepsilon)\right).$

We need to make sure that $k\geq k_{\mathsf{CB}}+td$ where $k_{\mathsf{CB}}=O(tm+td_{0}+t^{2}\log^{2}(t+1)\log(nt/\varepsilon_{\mathsf{CB}% }))$ , and indeed, this is satisfied by taking $k\geq C\cdot\left(t^{6}m\log n+t^{5}\log(1/\varepsilon)\right)$ for a large enough constant $C$ . We also need to make sure that $k\geq d^{2}$ and $k\geq c\log^{8}n$ , and both inequalities, together with our previous lower bound on $k$ , indeed holds whenever

$k\geq C\cdot t^{10}m^{2}\log^{8}n\log^{2}(1/\varepsilon)$

for a large enough constant $C$ .

Our construction goes as follows. For simplicity, identify $\left\{{0,1}\right\}^{d_{0}}$ with $[D=n^{c_{1}}]$ . Given $x\in\left\{{0,1}\right\}^{n}$ :

1.

For every $i\in[D]$ , compute $y_{i}=\mathsf{LExt}(x,i)$ .
2.

For every $i\in[D]$ , compute $z_{i}=\mathsf{AffCB}(x,y_{i},i)$ .

We’ll show that the table $Z=(Z_{1},\ldots,Z_{D})$ satisfies the requirement of the lemma. First, by Lemma 11, we have a set ${\rm BAD}\subseteq[D]$ of density $\rho({\rm BAD})\leq 1/n$ such that for any $i\notin{\rm BAD}$ it holds that $Y_{i}\sim\left\{{0,1}\right\}^{d}$ is uniform. Next, fix $t$ good rows $\left\{{i_{1},\ldots,i_{t}}\right\}\subseteq[D]\setminus{\rm BAD}$ . Consider the linear function $L\colon\left\{{0,1}\right\}^{n}\rightarrow\left\{{0,1}\right\}^{t\cdot d}$ that is given by $\left(\mathsf{LExt}(\cdot,i_{1}),\ldots,\mathsf{LExt}(\cdot,i_{t})\right)$ . Via the affine conditioning lemma, Lemma 7, we can write $X=A+B$ , where:

$\blacksquare$

$A$ and $B$ are affine and independent.
$\blacksquare$

$H(B)\geq H(X)-td=k_{\mathsf{CB}}$ .
$\blacksquare$

$L(B)$ is constant, so $Y_{i_{1}},\ldots,Y_{i_{t}}$ is independent of $B$ , and moreover, $B$ is independent of $\left(A,Y_{i_{1}},\ldots,Y_{i_{t}}\right)$ .

Recalling that each $Y_{i_{j}}$ is uniform, all conditions are met to apply are affine correlation breaker, which gives us

\left(Z_{i_{j}},\left\{{Z_{i_{k}}}\right\}_{k\in[t]\setminus\left\{{j}\right\}% }\right)\approx_{\varepsilon_{\mathsf{CB}}}\left(U_{m},\left\{{Z_{i_{k}}}% \right\}_{k\in[t]\setminus\left\{{j}\right\}}\right)

for every $j\in[t]$ . Therefore,

\left(Z_{i_{1}},\ldots,Z_{i_{t}}\right)\approx_{t\cdot\varepsilon_{\mathsf{CB}% }}U_{tm},

and so by Lemma 4, $Z$ itself is $(mD)^{tm}\cdot t\varepsilon_{\mathsf{CB}}=\varepsilon$ close to a $(q,t)$ non-oblivious $\left\{{0,1}\right\}^{m}$ -fixing source for $q=\frac{D}{n}=D^{1-\frac{1}{c_{1}}}$ . $\hfill\blacktriangleleft$

Next, we can simply apply the low-error condenser for NOSF sources given by [3].

Proof of Theorem 19.

Given $n$ and $\varepsilon>0$ , let $m$ be the number of bits we eventually output, and the entropy of $X$ will be determined according to that later on. Set $\gamma=\frac{1}{c_{1}}$ , and let $\alpha\in(0,1)$ and $c^{\prime}\geq 1$ be the constants that are set according to $\gamma$ , guaranteed to us by Theorem 17.

Let $\mathsf{AffToNOSF}\colon\left\{{0,1}\right\}^{n}\rightarrow\Sigma^{D}$ be the function from Lemma 20, where $\Sigma=\left\{{0,1}\right\}^{m}$ and $D=n^{c_{1}}$ , set with $t\leftarrow m\cdot d_{0}^{c^{\prime}}$ and $\varepsilon\leftarrow\varepsilon/2$ . By that lemma, there exists a constant $C>1$ such that whenever $k\geq\left(m\log(n/\varepsilon)\right)^{C}$ and $X$ is an $(n,k)$ affine source, it holds that $\mathsf{AffToNOSF}(X)$ is $\frac{\varepsilon}{2}$ -close to an $(D^{1-\gamma},t)$ NOSF source.

Now, let $\mathsf{EntRes}\colon\Sigma^{D}\rightarrow\Sigma$ be the $(D^{1-\gamma},t,g,\varepsilon/2)$ entropy resilient function from Theorem 17. Whenever $m\leq D^{\alpha/2}$ , we are guaranteed that $\mathsf{EntRes}\left(\mathsf{AffToNOSF}(X)\right)$ is $\varepsilon$ -close to an $(m,m-g)$ source with $g=o(\log(1/\varepsilon))$ . To conclude, we have that there exist constants $C\geq 1$ and $\delta\in(0,1)$ such that whenever $m\leq n^{\delta}$ and $k\geq\left(m\log(n/\varepsilon)\right)^{C}$ , the function

\mathsf{AffCond}(x)=\mathsf{EntRes}\left(\mathsf{AffToNOSF}(x)\right)

is an affine condenser with entropy gap $g=o(\log(1/\varepsilon))$ . Putting it differently, there exist constants $C^{\prime}\geq 1$ and $\delta^{\prime}\in(0,1)$ such that whenever $k\geq\left(\log(n/\varepsilon)\right)^{C^{\prime}}$ , our condenser outputs $k^{\delta^{\prime}}$ bits. $\hfill\blacktriangleleft$

5 Extractors for OBF Sources

5.1 Linear OBF Condensers

We begin by defining these condensers, and focus on the linear setting.

Definition 21 (OBF condenser).

A matrix $L\in\mathbb{F}_{2}^{m\times n}$ is an $(n,k)\to(m,t)$ linear condenser for OBF sources if $H_{\infty}(L(X))\geq t$ for any $(n,k)$ OBF source $X$ .

Rao showed that linear condensers for OBF sources can be obtained by parity check matrices of binary codes. The next statement is a bit different than the one in [47], so we provide the proof for completeness.¹⁸¹⁸18The connection between pseudorandomness for OBF sources and codes was established, at least for extractors, already in [17], and, possibly under different formulations, in the cryptography literature, e.g, in [15].

Lemma 22 (following [47]).

Let $X$ be an $(n,k)$ OBF source, let $k^{\prime}\leq k$ be any positive integer, and let $\mathcal{C}\subseteq\mathbb{F}_{2}^{n}$ be an $[n,r,d]$ code with a parity check matrix $P\in\mathbb{F}_{2}^{m\times n}$ , where $m=n-r$ and $d\geq k^{\prime}+1$ . Then, $Z=P\cdot X\sim\left\{{0,1}\right\}^{m}$ satisfies $H_{\infty}(Z)\geq k^{\prime}$ .

Proof.

Letting $i_{1},\ldots,i_{k}\in[n]$ be the entropic coordinates of $X$ , and let $c\in\mathbb{F}_{2}^{n}$ be its constant shift.¹⁹¹⁹19We can assume that $c$ is zero on $i_{1},\ldots,i_{k}$ . Consider

V_{k^{\prime}}=\operatorname{Span}\left(\left\{{e_{i_{1}},\ldots,e_{i_{k^{% \prime}}}}\right\}\right)\subseteq\operatorname{Supp}(X)+c,

observing that each element of $V_{k^{\prime}}$ has Hamming weight at most $k^{\prime}$ . Since $\mathcal{C}$ has distance greater than $k^{\prime}$ , $V_{k^{\prime}}\cap\mathcal{C}=\left\{{0}\right\}$ and so $P$ is injective on $V_{k^{\prime}}$ and thus also on $V_{k^{\prime}}+c$ . Let $W$ be the subspace for which $\operatorname{Supp}(X)+c=V_{k^{\prime}}\oplus W$ , and also refer to $V_{k^{\prime}}$ and $W$ as the corresponding flat distributions. Thus, for each $z\in\left\{{0,1}\right\}^{m}$ ,

\Pr[Z=z]=\Pr[P\cdot V_{k^{\prime}}=z+P\cdot W+c]=\operatorname*{\mathbb{E}}_{w% \sim W}\left[\Pr[P\cdot V_{k^{\prime}}=z+P\cdot w+c]\right]\leq 2^{-k^{\prime}},

and we are done. $\hfill\blacktriangleleft$

Using the BCH codes from Theorem 18, we get the following linear condensers for OBF sources.

Corollary 23.

There exists a constant $c>0$ such that the following holds. For every positive integers $n$ , $k\leq n$ , and $k^{\prime}\leq k$ , there exists an explicit linear function $P\colon\left\{{0,1}\right\}^{n}\rightarrow\left\{{0,1}\right\}^{m}$ for $m=ck^{\prime}\log n$ , such that the following holds. For every $(n,k)$ OBF source $X$ , it holds that $H_{\infty}(P(X))\geq k^{\prime}$ . That is, $P$ is an $(n,k)\rightarrow(ck^{\prime}\log n,k^{\prime})$ linear condenser for OBF sources.

5.2 OBF Extractors for Almost-Logarithmic Entropy

We are given $n,k\in\mathbb{N}$ , and $\gamma>0$ . Let $\varepsilon$ be our error guarantee, to be determined later on. We use the following ingredients:

$\blacksquare$

Let $P_{1}\colon\left\{{0,1}\right\}^{n}\rightarrow\left\{{0,1}\right\}^{n_{1}}$ be the linear condenser for OBF sources given in Corollary 23, set with $k^{\prime}\leftarrow k$ , so $n_{1}=c\cdot k\log n$ for some universal constant $c>0$ .
$\blacksquare$

Let $P_{2}\colon\left\{{0,1}\right\}^{n}\rightarrow\left\{{0,1}\right\}^{n_{2}}$ be the linear condenser for OBF sources given in Corollary 23, set with $k^{\prime}\leftarrow\frac{\gamma k}{2c\log n}\triangleq k_{\mathsf{Cond}}$ , so $n_{2}=\gamma k/2$ .
$\blacksquare$

Let $\mathsf{AffCond}\colon\left\{{0,1}\right\}^{n_{2}}\rightarrow\left\{{0,1}% \right\}^{d}$ be the affine condenser from Theorem 19, set with $k\leftarrow k_{\mathsf{Cond}}$ and $\varepsilon\leftarrow\varepsilon/2$ .
$\blacksquare$

Let $\mathsf{LExt}\colon\left\{{0,1}\right\}^{n_{1}}\times\left\{{0,1}\right\}^{d}% \rightarrow\left\{{0,1}\right\}^{m}$ be the $(k_{\mathsf{Ext}}=(1-\gamma/2)k,\varepsilon_{\mathsf{Ext}})$ extractor of Theorem 10, where $\varepsilon_{\mathsf{Ext}}=\varepsilon^{4}/16$ and $m=(1-\gamma/2)k_{\mathsf{Ext}}\geq(1-\gamma)k$ . There exists a constant $c_{2}$ such that a seed of length $d=c_{2}\left(\log(n_{1})+\log^{2}(k/\varepsilon)\cdot\log(1/\gamma)\right)$ suffices.

Now, given $x\in\left\{{0,1}\right\}^{n}$ , our extractor $\mathsf{OBFExt}\colon\left\{{0,1}\right\}^{n}\rightarrow\left\{{0,1}\right\}^{m}$ is given by

\mathsf{OBFExt}(x)=\mathsf{LExt}\left(P_{1}(x),\mathsf{AffCond}\left(P_{2}(x)% \right)\right)

The fact that $\mathsf{OBFExt}$ is explicit readily follows from the explicitness of its components. The correctness is established in the following theorem.

Theorem 24.

There exist universal constants $c_{k},c_{\gamma}>1$ and $\beta\in(0,1)$ such that the following holds, assuming $k\geq\frac{\log n}{\gamma}\cdot(\log\frac{\log n}{\gamma})^{c_{k}}$ and $\gamma\geq\frac{\log^{c_{\gamma}}k}{k}$ . For every $(n,k)$ OBF source $X$ it holds that $\mathsf{OBFExt}(X)\approx_{\varepsilon}U_{m}$ for $\varepsilon=2^{-((\gamma k)/\log n)^{\beta}}$ , recalling that $m=(1-\gamma)k$ .

Proof.

Denote $X_{1}=P_{1}(X)$ , $X_{2}=P_{2}(X)$ , $Y=\mathsf{AffCond}(X_{2})$ , and $Z=\mathsf{LExt}(X_{1},Y)$ . We “affine condition” (Theorem 19) according to $P_{2}$ , and so we can write $X$ as $X=A+B$ , where $A$ and $B$ are affine and independent and there exists a linear bijection between $A$ and $X_{2}$ (so $B$ is independent of $X_{2}$ and thus also of $Y$ ). We can then write

Z=\mathsf{LExt}(X_{1},Y)=\mathsf{LExt}(P_{1}(A),Y)+\mathsf{LExt}(P_{1}(B),Y).

We know that $H(X_{1})\geq k$ , $H(A)\leq n_{2}$ , and $H(B)\geq H(X)-n_{2}\geq(1-\gamma/2)k=k_{\mathsf{Ext}}$ . Also, $X_{1}=P_{1}(A)+P_{1}(B)$ , and $P_{1}(A)$ and $P_{1}(B)$ are independent. Thus, $H(P_{1}(B))\geq k_{\mathsf{Ext}}$ as well,²⁰²⁰20To see this, recall that $B$ is a subspace of $X$ (up to a shift), and $P_{1}$ is injective on $X$ . and $P_{1}(B)$ is independent of $Y$ .

Claim 25.

With probability at least $1-\varepsilon/2$ over $y\sim Y$ it holds that $\mathsf{LExt}(P_{1}(B),y)\approx_{\varepsilon/2}U_{m}$ .

Proof.

To apply our affine condenser, Theorem 19, we need to make sure that:

1.

$k_{\mathsf{Cond}}\geq\log^{c^{\prime}}(n_{2}/\varepsilon)$ , where $c^{\prime}>1$ is the constant guaranteed to us by Theorem 19. Recall that

$\log^{c^{\prime}}\left(\frac{n_{2}}{\varepsilon}\right)=O\left(\log^{c^{\prime% }}\left(\frac{k}{\varepsilon}\right)\right),$

and that

$k_{\mathsf{Cond}}=\Omega\left(\frac{\gamma k}{\log n}\right),$

so the inequality is met as long as $k\geq\frac{\log n}{\gamma}\cdot(\log\frac{\log n}{\gamma})^{c_{k}}$ and $\varepsilon\geq 2^{-((\gamma k)/\log n)^{\beta}}$ for some constants $c_{k}>1$ and $\beta\in(0,1)$ .
2.
$d\leq k_{\mathsf{Cond}}^{\alpha}$ , where $\alpha\in(0,1)$ is the constant guaranteed to us by Theorem 19. Plugging in the expression for $d$ above, we get that similarly, we need to satisfy:
1. (a)
  
  $k\geq\frac{\log n}{\gamma}\cdot(\log\frac{\log n}{\gamma})^{c_{k}}$ for some constants $c_{k}>1$ ,
2. (b)
  
  $\varepsilon\geq 2^{-((\gamma k)/\log n)^{\beta}}$ for some constant $\beta\in(0,1)$ , and,
3. (c)
  
  $\gamma\geq\frac{\log^{c_{\gamma}}k}{k}$ for some constant $c_{\gamma}>1$ .

So indeed, Theorem 19 tells us that $Y$ itself is $(\varepsilon/4)$ -close to a $(d,d-g)$ -source for $g=o(\log(1/\varepsilon))$ , and thus by Claim 12 we have that $\mathsf{LExt}(P_{1}(B),y)\approx_{\sqrt{\varepsilon_{\mathsf{Ext}}}}U_{m}$ except for probability

2^{g}\sqrt{\varepsilon_{\mathsf{Ext}}}+\frac{\varepsilon}{4}\leq\frac{1}{% \varepsilon}\cdot\frac{\varepsilon^{2}}{4}+\frac{\varepsilon}{4}\leq\frac{% \varepsilon}{2}.\

$\hfill\vartriangleleft$ Fix a good $y$ (in the sense of the above claim), and observe that $\mathsf{LExt}(P_{1}(A),y)$ is independent from $\mathsf{LExt}(P_{1}(B),y)$ , making

\mathsf{LExt}(X_{1},y)=\mathsf{LExt}(P_{1}(A),y)+\mathsf{LExt}(P_{1}(B),y)

close to uniform as well. Overall, $Z\approx_{2\cdot(\varepsilon/2)}U_{m}$ , and we are done. $\hfill\blacktriangleleft$

Choosing $\gamma=\frac{1}{\log^{c}k}$ for any constant $c$ , we obtain our Theorem 3.

5.3 Handling Low-Weight Affine Sources

We say that an $(n,k)$ affine source $X$ has weight $w$ if each basis element of $X$ has weight at most $w$ . This generalizes OBF sources (that have $w=1$ ), and [47] can handle $w=k^{\alpha}$ for a small constant $\alpha>0$ . Note that the only place in the proof that we used the fact that $X$ is an OBF source (rather than a full-fledged affine source) is Lemma 22, where we argued that codes with sufficiently large distance give linear condensers. This can easily be extended to the $w>1$ case.

Lemma 26 (following [47]).

Let $X$ be an $(n,k)$ affine source of weight $w$ , let $k^{\prime}\leq k$ be any positive integer, and let $\mathcal{C}\subseteq\mathbb{F}_{2}^{n}$ be an $[n,r,d]$ code with a parity check matrix $P\in\mathbb{F}_{2}^{m\times n}$ , where $m=n-r$ and $d\geq wk^{\prime}+1$ . Then, $Z=P\cdot X\sim\left\{{0,1}\right\}^{m}$ satisfies $H_{\infty}(Z)\geq k^{\prime}$ .

Thus, as $w$ grows, the co-dimension of the code we need to take grows too, and so the condensing quality decreases. To modify our construction to handle $w>1$ , we need to set $n_{1}=c\cdot wk\log n$ and $k_{\mathsf{Cond}}=\frac{\gamma k}{2cw\log n}$ . Repeating the same analysis as in Section 5.2, we see that one can take $w={\rm poly}(\log k)$ without significant loss in parameters.

Theorem 27.

For any constant $\ell>0$ there exist constants $c>1$ and $\beta\in(0,1)$ such that the following holds for any $n\in\mathbb{N}$ and $k\geq\log n\cdot(\log\log n)^{c}$ . There exists an explicit function

\mathsf{OBFExt}\colon\left\{{0,1}\right\}^{n}\rightarrow\left\{{0,1}\right\}^{% m=(1-o(1))k}

that is a $(k,\varepsilon)$ extractor for affine sources of weight $w=\log^{\ell}k$ , where $\varepsilon=2^{-(k/\log n)^{\beta}}$ .

References

[1] Miklós Ajtai and Nathan Linial. The influence of large coalitions. Combinatorica, 13(2):129–145, 1993. doi:10.1007/BF01303199.
[2] Noga Alon, Oded Goldreich, and Yishay Mansour. Almost k-wise independence versus k-wise independence. Information Processing Letters, 88(3):107–110, 2003. doi:10.1016/S0020-0190(03)00359-4.
[3] Avraham Ben-Aroya, Gil Cohen, Dean Doron, and Amnon Ta-Shma. Two-source condensers with low error and small entropy gap via entropy-resilient functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 43:1–43:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.43.
[4] Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. An efficient reduction from two-source to nonmalleable extractors:: Achieving near-logarithmic min-entropy. SIAM Journal on Computing, 51(2):STOC17–31, 2019.
[5] Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. Near-optimal erasure list-decodable codes. In Computational Complexity Conference (CCC), pages 1:1–1:27. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.CCC.2020.1.
[6] Charles H. Bennett, Gilles Brassard, and Jean-Marc Robert. How to reduce your enemy’s information. In Advances in Cryptology (CRYPTO), volume 218 of Lecture Notes in Computer Science, pages 468–476. Springer, 1985.
[7] Raj Chandra Bose and Dwijendra K. Ray-Chaudhuri. On a class of error correcting binary group codes. Information and control, 3(1):68–79, 1960. doi:10.1016/S0019-9958(60)90287-4.
[8] Jean Bourgain. More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory, 1(01):1–32, 2005.
[9] Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, and Amit Sahai. Exposure-resilient functions and all-or-nothing transforms. In Advances in Cryptology (EUROCRYPT), pages 453–469. Springer, 2000. doi:10.1007/3-540-45539-6_33.
[10] Eshan Chattopadhyay, Jesse Goodman, and Jyun-Jie Liao. Affine extractors for almost logarithmic entropy. In Annual Symposium on Foundations of Computer Science (FOCS), pages 622–633. IEEE, 2022.
[11] Eshan Chattopadhyay and Xin Li. Explicit non-malleable extractors, multi-source extractors, and almost optimal privacy amplification protocols. In Annual Symposium on the Foundations of Computer Science (FOCS), pages 158–167. IEEE, 2016. doi:10.1109/FOCS.2016.25.
[12] Eshan Chattopadhyay and Jyun-Jie Liao. Extractors for sum of two sources. In Annual Symposium on Theory of Computing (STOC), pages 1584–1597. ACM, 2022. doi:10.1145/3519935.3519963.
[13] Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. Annals of Mathematics, 189(3):653–705, 2019.
[14] Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, and David Zuckerman. Mining circuit lower bound proofs for meta-algorithms. computational complexity, 24:333–392, 2015. doi:10.1007/S00037-015-0100-0.
[15] Mahdi Cheraghchi, Fredric Didier, and Amin Shokrollahi. Invertible extractors and wiretap protocols. IEEE Transactions on Information Theory, 58(2):1254–1274, 2011. doi:10.1109/TIT.2011.2170660.
[16] Mahdi Cheraghchi and Piotr Indyk. Nearly optimal deterministic algorithm for sparse Walsh-Hadamard transform. ACM Transactions on Algorithms (TALG), 13(3):1–36, 2017. doi:10.1145/3029050.
[17] Benny Chor, Oded Goldreich, Johan Håstad, Joel Freidmann, Steven Rudich, and Roman Smolensky. The bit extraction problem or t-resilient functions. In Annual Symposium on Foundations of Computer Science (FOCS), pages 396–407. IEEE, 1985.
[18] Gil Cohen. Local correlation breakers and applications to three-source extractors and mergers. SIAM Journal on Computing, 45(4):1297–1338, 2016. doi:10.1137/15M1029837.
[19] Gil Cohen. Towards optimal two-source extractors and Ramsey graphs. In Annual Symposium on Theory of Computing (STOC), pages 1157–1170. ACM, 2017. doi:10.1145/3055399.3055429.
[20] Gil Cohen and Igor Shinkar. Zero-fixing extractors for sub-logarithmic entropy. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 343–354. Springer, 2015. doi:10.1007/978-3-662-47672-7_28.
[21] Yevgeniy Dodis. Exposure-Resilient Cryptography. Phd thesis, MIT, 2000.
[22] Yevgeniy Dodis, Amit Sahai, and Adam Smith. On perfect and adaptive security in exposure-resilient cryptography. In Advances in Cryptology (EUROCRYPT), pages 301–324. Springer, 2001. doi:10.1007/3-540-44987-6_19.
[23] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology (EUROCRYPT), pages 486–503. Springer, 2006. doi:10.1007/11761679_29.
[24] Joel Friedman. On the bit extraction problem. In Annual Symposium on Foundations of Computer Science (FOCS), volume 33, pages 314–314. IEEE, 1992.
[25] Ariel Gabizon and Ran Raz. Deterministic extractors for affine sources over large fields. Combinatorica, 28(4):415–440, 2008. doi:10.1007/S00493-008-2259-3.
[26] Ariel Gabizon, Ran Raz, and Ronen Shaltiel. Deterministic extractors for bit-fixing sources by obtaining an independent seed. SIAM Journal on Computing, 36(4):1072–1094, 2006. doi:10.1137/S0097539705447049.
[27] Jesse Patrick McGrenra Goodman. Seedless Extractors. Phd thesis, Cornell University, 2023. Available at https://jpmgoodman.com/thesis.pdf.
[28] Venkatesan Guruswami, Christopher Umans, and Salil Vadhan. Unbalanced expanders and randomness extractors from parvaresh–vardy codes. Journal of the ACM (JACM), 56(4):20, 2009.
[29] Alexis Hocquenghem. Codes correcteurs d’erreurs. Chiffers, 2:147–156, 1959.
[30] Peter Ivanov, Raghu Meka, and Emanuele Viola. Efficient resilient functions. In Annual Symposium on Discrete Algorithms (SODA), pages 2867–2874. ACM-SIAM, 2023. doi:10.1137/1.9781611977554.CH108.
[31] Peter Ivanov and Emanuele Viola. Resilient functions: Optimized, simplified, and generalized. arXiv preprint arXiv:2406.19467, 2024. doi:10.48550/arXiv.2406.19467.
[32] Markus Jakobsson, Julien P. Stern, and Moti Yung. Scramble all, encrypt small. In International Workshop on Fast Software Encryption, pages 95–111. Springer, 1999. doi:10.1007/3-540-48519-8_8.
[33] Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on boolean functions. In Annual Symposium on Foundations of Computer Science (FOCS), pages 68–80. IEEE, 1988.
[34] Jesse Kamp and David Zuckerman. Deterministic extractors for bit-fixing sources and exposure-resilient cryptography. SIAM Journal on Computing, 36(5):1231–1247, 2006. doi:10.1137/S0097539705446846.
[35] Ilan Komargodski, Ran Raz, and Avishay Tal. Improved average-case lower bounds for demorgan formula size. In Annual Symposium on Foundations of Computer Science (FOCS), pages 588–597. IEEE, 2013. doi:10.1109/FOCS.2013.69.
[36] Mark Lewko. An explicit two-source extractor with min-entropy rate near 4/9. Mathematika, 65(4):950–957, 2019.
[37] Xin Li. A new approach to affine extractors and dispersers. In Computational Complexity Conference (CCC), pages 137–147. IEEE, 2011. doi:10.1109/CCC.2011.27.
[38] Xin Li. Extractors for a constant number of independent sources with polylogarithmic min-entropy. In Annual Symposium on the Foundations of Computer Science (FOCS), pages 100–109. IEEE, 2013. doi:10.1109/FOCS.2013.19.
[39] Xin Li. New independent source extractors with exponential improvement. In Annual Symposium on Theory of Computing (STOC), pages 783–792. ACM, 2013. doi:10.1145/2488608.2488708.
[40] Xin Li. Three-source extractors for polylogarithmic min-entropy. In Annual Symposium on Foundations of Computer Science (FOCS), pages 863–882. IEEE, 2015. doi:10.1109/FOCS.2015.58.
[41] Xin Li. Three-source extractors for polylogarithmic min-entropy. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 863–882. IEEE, 2015. doi:10.1109/FOCS.2015.58.
[42] Xin Li. Improved two-source extractors, and affine extractors for polylogarithmic entropy. In Annual Symposium on Foundations of Computer Science (FOCS), pages 168–177. IEEE, 2016. doi:10.1109/FOCS.2016.26.
[43] Xin Li. Non-malleable extractors and non-malleable codes: Partially optimal constructions. In Computational Complexity Conference (CCC), pages 28:1–28:49. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPICS.CCC.2019.28.
[44] Xin Li. Two source extractors for asymptotically optimal entropy, and (many) more. In Annual Symposium on Foundations of Computer Science (FOCS), pages 1271–1281. IEEE, 2023. doi:10.1109/FOCS57990.2023.00075.
[45] Xin Li and Yan Zhong. Explicit directional affine extractors and improved hardness for linear branching programs. In Computational Complexity Conference (CCC), pages 10:1–10:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.CCC.2024.10.
[46] Raghu Meka. Explicit resilient functions matching Ajtai-Linial. In Annual Symposium on Discrete Algorithms (SODA), pages 1132–1148. ACM-SIAM, 2017. doi:10.1137/1.9781611974782.73.
[47] Anup Rao. Extractors for low-weight affine sources. In Computational Complexity Conference (CCC), pages 95–101. IEEE, 2009. doi:10.1109/CCC.2009.36.
[48] Ran Raz, Omer Reingold, and Salil Vadhan. Extracting all the randomness and reducing the error in trevisan’s extractors. Journal of Computer and System Sciences, 65(1):97–128, 2002. doi:10.1006/JCSS.2002.1824.
[49] Ronald L Rivest. All-or-nothing encryption and the package transform. In Fast Software Encryption: 4th International Workshop, FSE’97 Haifa, Israel, January 20–22 1997 Proceedings 4, pages 210–218. Springer, 1997. doi:10.1007/BFB0052348.
[50] Ronen Shaltiel. How to get more mileage from randomness extractors. Random Structures & Algorithms, 33(2):157–186, 2008. doi:10.1002/RSA.20207.
[51] Ronen Shaltiel and Christopher Umans. Simple extractors for all min-entropies and a new pseudorandom generator. Journal of the ACM (JACM), 52(2):172–216, 2005. doi:10.1145/1059513.1059516.
[52] Luca Trevisan. Extractors and pseudorandom generators. Journal of the ACM (JACM), 48(4):860–879, 2001. doi:10.1145/502090.502099.
[53] Umesh V. Vazirani. Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources. Combinatorica, 7(4):375–392, 1987. doi:10.1007/BF02579325.
[54] John von Neumann. Various techniques used in connection with random digits. Applied Math Series, 12(36-38):5, 1951.
[55] Amir Yehudayoff. Affine extractors over prime fields. Combinatorica, 31(2):245–256, 2011. doi:10.1007/S00493-011-2604-9.

[bib.bib1] [1] Miklós Ajtai and Nathan Linial. The influence of large coalitions. Combinatorica, 13(2):129–145, 1993. doi:10.1007/BF01303199.

[bib.bib2] [2] Noga Alon, Oded Goldreich, and Yishay Mansour. Almost k-wise independence versus k-wise independence. Information Processing Letters, 88(3):107–110, 2003. doi:10.1016/S0020-0190(03)00359-4.

[bib.bib3] [3] Avraham Ben-Aroya, Gil Cohen, Dean Doron, and Amnon Ta-Shma. Two-source condensers with low error and small entropy gap via entropy-resilient functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 43:1–43:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.43.

[bib.bib4] [4] Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. An efficient reduction from two-source to nonmalleable extractors:: Achieving near-logarithmic min-entropy. SIAM Journal on Computing, 51(2):STOC17–31, 2019.

[bib.bib5] [5] Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. Near-optimal erasure list-decodable codes. In Computational Complexity Conference (CCC), pages 1:1–1:27. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.CCC.2020.1.

[bib.bib6] [6] Charles H. Bennett, Gilles Brassard, and Jean-Marc Robert. How to reduce your enemy’s information. In Advances in Cryptology (CRYPTO), volume 218 of Lecture Notes in Computer Science, pages 468–476. Springer, 1985.

[bib.bib7] [7] Raj Chandra Bose and Dwijendra K. Ray-Chaudhuri. On a class of error correcting binary group codes. Information and control, 3(1):68–79, 1960. doi:10.1016/S0019-9958(60)90287-4.

[bib.bib8] [8] Jean Bourgain. More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory, 1(01):1–32, 2005.

[bib.bib9] [9] Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, and Amit Sahai. Exposure-resilient functions and all-or-nothing transforms. In Advances in Cryptology (EUROCRYPT), pages 453–469. Springer, 2000. doi:10.1007/3-540-45539-6_33.

[bib.bib10] [10] Eshan Chattopadhyay, Jesse Goodman, and Jyun-Jie Liao. Affine extractors for almost logarithmic entropy. In Annual Symposium on Foundations of Computer Science (FOCS), pages 622–633. IEEE, 2022.

[bib.bib11] [11] Eshan Chattopadhyay and Xin Li. Explicit non-malleable extractors, multi-source extractors, and almost optimal privacy amplification protocols. In Annual Symposium on the Foundations of Computer Science (FOCS), pages 158–167. IEEE, 2016. doi:10.1109/FOCS.2016.25.

[bib.bib12] [12] Eshan Chattopadhyay and Jyun-Jie Liao. Extractors for sum of two sources. In Annual Symposium on Theory of Computing (STOC), pages 1584–1597. ACM, 2022. doi:10.1145/3519935.3519963.

[bib.bib13] [13] Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. Annals of Mathematics, 189(3):653–705, 2019.

[bib.bib14] [14] Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, and David Zuckerman. Mining circuit lower bound proofs for meta-algorithms. computational complexity, 24:333–392, 2015. doi:10.1007/S00037-015-0100-0.

[bib.bib15] [15] Mahdi Cheraghchi, Fredric Didier, and Amin Shokrollahi. Invertible extractors and wiretap protocols. IEEE Transactions on Information Theory, 58(2):1254–1274, 2011. doi:10.1109/TIT.2011.2170660.

[bib.bib16] [16] Mahdi Cheraghchi and Piotr Indyk. Nearly optimal deterministic algorithm for sparse Walsh-Hadamard transform. ACM Transactions on Algorithms (TALG), 13(3):1–36, 2017. doi:10.1145/3029050.

[bib.bib17] [17] Benny Chor, Oded Goldreich, Johan Håstad, Joel Freidmann, Steven Rudich, and Roman Smolensky. The bit extraction problem or t-resilient functions. In Annual Symposium on Foundations of Computer Science (FOCS), pages 396–407. IEEE, 1985.

[bib.bib18] [18] Gil Cohen. Local correlation breakers and applications to three-source extractors and mergers. SIAM Journal on Computing, 45(4):1297–1338, 2016. doi:10.1137/15M1029837.

[bib.bib19] [19] Gil Cohen. Towards optimal two-source extractors and Ramsey graphs. In Annual Symposium on Theory of Computing (STOC), pages 1157–1170. ACM, 2017. doi:10.1145/3055399.3055429.

[bib.bib20] [20] Gil Cohen and Igor Shinkar. Zero-fixing extractors for sub-logarithmic entropy. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 343–354. Springer, 2015. doi:10.1007/978-3-662-47672-7_28.

[bib.bib21] [21] Yevgeniy Dodis. Exposure-Resilient Cryptography. Phd thesis, MIT, 2000.

[bib.bib22] [22] Yevgeniy Dodis, Amit Sahai, and Adam Smith. On perfect and adaptive security in exposure-resilient cryptography. In Advances in Cryptology (EUROCRYPT), pages 301–324. Springer, 2001. doi:10.1007/3-540-44987-6_19.

[bib.bib23] [23] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology (EUROCRYPT), pages 486–503. Springer, 2006. doi:10.1007/11761679_29.

[bib.bib24] [24] Joel Friedman. On the bit extraction problem. In Annual Symposium on Foundations of Computer Science (FOCS), volume 33, pages 314–314. IEEE, 1992.

[bib.bib25] [25] Ariel Gabizon and Ran Raz. Deterministic extractors for affine sources over large fields. Combinatorica, 28(4):415–440, 2008. doi:10.1007/S00493-008-2259-3.

[bib.bib26] [26] Ariel Gabizon, Ran Raz, and Ronen Shaltiel. Deterministic extractors for bit-fixing sources by obtaining an independent seed. SIAM Journal on Computing, 36(4):1072–1094, 2006. doi:10.1137/S0097539705447049.

[bib.bib27] [27] Jesse Patrick McGrenra Goodman. Seedless Extractors. Phd thesis, Cornell University, 2023. Available at https://jpmgoodman.com/thesis.pdf.

[bib.bib28] [28] Venkatesan Guruswami, Christopher Umans, and Salil Vadhan. Unbalanced expanders and randomness extractors from parvaresh–vardy codes. Journal of the ACM (JACM), 56(4):20, 2009.

[bib.bib29] [29] Alexis Hocquenghem. Codes correcteurs d’erreurs. Chiffers, 2:147–156, 1959.

[bib.bib30] [30] Peter Ivanov, Raghu Meka, and Emanuele Viola. Efficient resilient functions. In Annual Symposium on Discrete Algorithms (SODA), pages 2867–2874. ACM-SIAM, 2023. doi:10.1137/1.9781611977554.CH108.

[bib.bib31] [31] Peter Ivanov and Emanuele Viola. Resilient functions: Optimized, simplified, and generalized. arXiv preprint arXiv:2406.19467, 2024. doi:10.48550/arXiv.2406.19467.

[bib.bib32] [32] Markus Jakobsson, Julien P. Stern, and Moti Yung. Scramble all, encrypt small. In International Workshop on Fast Software Encryption, pages 95–111. Springer, 1999. doi:10.1007/3-540-48519-8_8.

[bib.bib33] [33] Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on boolean functions. In Annual Symposium on Foundations of Computer Science (FOCS), pages 68–80. IEEE, 1988.

[bib.bib34] [34] Jesse Kamp and David Zuckerman. Deterministic extractors for bit-fixing sources and exposure-resilient cryptography. SIAM Journal on Computing, 36(5):1231–1247, 2006. doi:10.1137/S0097539705446846.

[bib.bib35] [35] Ilan Komargodski, Ran Raz, and Avishay Tal. Improved average-case lower bounds for demorgan formula size. In Annual Symposium on Foundations of Computer Science (FOCS), pages 588–597. IEEE, 2013. doi:10.1109/FOCS.2013.69.

[bib.bib36] [36] Mark Lewko. An explicit two-source extractor with min-entropy rate near 4/9. Mathematika, 65(4):950–957, 2019.

[bib.bib37] [37] Xin Li. A new approach to affine extractors and dispersers. In Computational Complexity Conference (CCC), pages 137–147. IEEE, 2011. doi:10.1109/CCC.2011.27.

[bib.bib38] [38] Xin Li. Extractors for a constant number of independent sources with polylogarithmic min-entropy. In Annual Symposium on the Foundations of Computer Science (FOCS), pages 100–109. IEEE, 2013. doi:10.1109/FOCS.2013.19.

[bib.bib39] [39] Xin Li. New independent source extractors with exponential improvement. In Annual Symposium on Theory of Computing (STOC), pages 783–792. ACM, 2013. doi:10.1145/2488608.2488708.

[bib.bib40] [40] Xin Li. Three-source extractors for polylogarithmic min-entropy. In Annual Symposium on Foundations of Computer Science (FOCS), pages 863–882. IEEE, 2015. doi:10.1109/FOCS.2015.58.

[bib.bib41] [41] Xin Li. Three-source extractors for polylogarithmic min-entropy. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 863–882. IEEE, 2015. doi:10.1109/FOCS.2015.58.

[bib.bib42] [42] Xin Li. Improved two-source extractors, and affine extractors for polylogarithmic entropy. In Annual Symposium on Foundations of Computer Science (FOCS), pages 168–177. IEEE, 2016. doi:10.1109/FOCS.2016.26.

[bib.bib43] [43] Xin Li. Non-malleable extractors and non-malleable codes: Partially optimal constructions. In Computational Complexity Conference (CCC), pages 28:1–28:49. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPICS.CCC.2019.28.

[bib.bib44] [44] Xin Li. Two source extractors for asymptotically optimal entropy, and (many) more. In Annual Symposium on Foundations of Computer Science (FOCS), pages 1271–1281. IEEE, 2023. doi:10.1109/FOCS57990.2023.00075.

[bib.bib45] [45] Xin Li and Yan Zhong. Explicit directional affine extractors and improved hardness for linear branching programs. In Computational Complexity Conference (CCC), pages 10:1–10:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.CCC.2024.10.

[bib.bib46] [46] Raghu Meka. Explicit resilient functions matching Ajtai-Linial. In Annual Symposium on Discrete Algorithms (SODA), pages 1132–1148. ACM-SIAM, 2017. doi:10.1137/1.9781611974782.73.

[bib.bib47] [47] Anup Rao. Extractors for low-weight affine sources. In Computational Complexity Conference (CCC), pages 95–101. IEEE, 2009. doi:10.1109/CCC.2009.36.

[bib.bib48] [48] Ran Raz, Omer Reingold, and Salil Vadhan. Extracting all the randomness and reducing the error in trevisan’s extractors. Journal of Computer and System Sciences, 65(1):97–128, 2002. doi:10.1006/JCSS.2002.1824.

[bib.bib49] [49] Ronald L Rivest. All-or-nothing encryption and the package transform. In Fast Software Encryption: 4th International Workshop, FSE’97 Haifa, Israel, January 20–22 1997 Proceedings 4, pages 210–218. Springer, 1997. doi:10.1007/BFB0052348.

[bib.bib50] [50] Ronen Shaltiel. How to get more mileage from randomness extractors. Random Structures & Algorithms, 33(2):157–186, 2008. doi:10.1002/RSA.20207.

[bib.bib51] [51] Ronen Shaltiel and Christopher Umans. Simple extractors for all min-entropies and a new pseudorandom generator. Journal of the ACM (JACM), 52(2):172–216, 2005. doi:10.1145/1059513.1059516.

[bib.bib52] [52] Luca Trevisan. Extractors and pseudorandom generators. Journal of the ACM (JACM), 48(4):860–879, 2001. doi:10.1145/502090.502099.

[bib.bib53] [53] Umesh V. Vazirani. Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources. Combinatorica, 7(4):375–392, 1987. doi:10.1007/BF02579325.

[bib.bib54] [54] John von Neumann. Various techniques used in connection with random digits. Applied Math Series, 12(36-38):5, 1951.

[bib.bib55] [55] Amir Yehudayoff. Affine extractors over prime fields. Combinatorica, 31(2):245–256, 2011. doi:10.1007/S00493-011-2604-9.