Nearly-Linear Time Seeded Extractors with Short Seeds

Dean Doron Ben-Gurion University. [email protected]. Part of this work was done while visiting Instituto de Telecomunicações and the Simons Institute for the Theory of Computing. João Ribeiro Instituto de Telecomunicações and Departamento de Matemática, Instituto Superior Técnico, Universidade de Lisboa. [email protected]. Part of this work was done while at NOVA LINCS and NOVA School of Science and Technology, and while visiting the Simons Institute for the Theory of Computing.

Abstract

Seeded extractors are fundamental objects in pseudorandomness and cryptography, and a deep line of work has designed polynomial-time seeded extractors with nearly-optimal parameters. However, existing constructions of seeded extractors with short seed length and large output length run in time $\Omega(n\log(1/\varepsilon))$ and often slower, where $n$ is the input source length and $\varepsilon$ is the error of the extractor. Since cryptographic applications of extractors require $\varepsilon$ to be small, the resulting runtime makes these extractors unusable in practice.

Motivated by this, we explore constructions of strong seeded extractors with short seeds computable in nearly-linear time $O(n\log^{c}n)$ , for any error $\varepsilon$ . We show that an appropriate combination of modern condensers and classical approaches for constructing seeded extractors for high min-entropy sources yields strong extractors for $n$ -bit sources with any min-entropy $k$ and any target error $\varepsilon$ with seed length $d=O(\log(n/\varepsilon))$ and output length $m=(1-\eta)k$ for an arbitrarily small constant $\eta>0$ , running in nearly-linear time, after a reasonable one-time preprocessing step (finding a primitive element of $\mathds{F}_{q}$ with $q=\operatorname{poly}(n/\varepsilon)$ a power of $2$ ) that is only required when $k<2^{C\log^{*}\!n}\cdot\log^{2}(n/\varepsilon)$ , for a constant $C>0$ and $\log^{*}\!$ the iterated logarithm, and which can be implemented in time $\operatorname{polylog}(n/\varepsilon)$ under mild conditions on $q$ . As a second contribution, we give an instantiation of Trevisan’s extractor that can be evaluated in truly linear time in the RAM model, as long as the number of output bits is at most $\frac{n}{\log(1/\varepsilon)\operatorname{polylog}(n)}$ . Previous fast implementations of Trevisan’s extractor ran in $\widetilde{O}(n)$ time in this setting. In particular, these extractors directly yield privacy amplification protocols with the same time complexity and output length, and communication complexity equal to their seed length.

1 Introduction

Seeded randomness extractors are central objects in the theory of pseudorandomness. A strong $(k,\varepsilon)$ -seeded extractor is a deterministic function $\mathsf{Ext}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\to\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m}$ that receives as input an $n$ -bit source of randomness $X$ with $k$ bits of min-entropy¹¹1A random variable $X$ has $k$ bits of min-entropy if $\Pr[X=x]\leq 2^{-k}$ for all $x$ . Min-entropy has been the most common measure for the quality of a weak source of randomness since the work of Chor and Goldreich [CG88]. and a $d$ -bit independent and uniformly random seed $Y$ , and outputs an $m$ -bit string $\mathsf{Ext}(X,Y)$ that is $\varepsilon$ -close in statistical distance to the uniform distribution over $\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m}$ , where $\varepsilon$ is an error term, even when the seed $Y$ is revealed. Besides their most direct application to the generation of nearly-perfect randomness from imperfect physical sources of randomness (and their inaugural applications to derandomizing space-bounded computation [NZ96] and privacy amplification [BBCM95]), seeded extractors have also found many other surprising applications throughout computer science, particularly in cryptography.

For most applications, it is important to minimize the seed length of the extractor. A standard application of the probabilistic method shows the existence of strong $(k,\varepsilon)$ -seeded extractors with seed length $d=\log(n-k)+2\log(1/\varepsilon)+O(1)$ and output length $m=k-2\log(1/\varepsilon)-O(1)$ , and we also know that these parameters are optimal up to the $O(1)$ terms [RT00]. This motivated a deep line of research devising explicit constructions of seeded extractors with seed length as small as possible spanning more than a decade (e.g., [NZ96, SZ99, NT99, Tre01, TZS06, SU05]) and culminating in extractors with essentially optimal seed length [LRVW03, GUV09]. In particular, the beautiful work of Guruswami, Umans, and Vadhan [GUV09] gives explicit strong extractors with order-optimal seed length $d=O(\log(n/\varepsilon))$ and output length $m=(1-\eta)k$ for any constant $\delta>0$ , and follow-up work [DKSS13, TU12] further improved the entropy loss $k+d-m$ . The extractors constructed in these works are explicit, in the sense that there is an algorithm that given $x$ and $y$ computes the corresponding output $\mathsf{Ext}(x,y)$ in time polynomial in the input length.

A closer look shows that the short-seed constructions presented in the literature all run in time $\Omega(n\log(1/\varepsilon))$ , and often significantly slower. In cryptographic applications of extractors we want the error guarantee $\varepsilon$ to be small, which means that implementations running in time $\Omega(n\log(1/\varepsilon))$ are often impractical. If we insist on nearly-linear runtime for arbitrary error $\varepsilon$ , we can use strong seeded extractors based on universal hash functions that can be implemented in $O(n\log n)$ time (e.g., see [HT16]), have essentially optimal output length, but have the severe drawback of requiring a very large seed length $d=\Omega(m)$ .

These limitations have been noted in a series of works studying concrete implementations of seeded extractors, with practical applications in quantum cryptography in mind [MPS12, FWE⁺23, FYEC24]. For example, Foreman, Yeung, Edgington, and Curchod [FYEC24] implement a version of Trevisan’s extractor [Tre01, RRV02] with its standard instantiation of Reed–Solomon codes concatenated with the Hadmadard code, and emphasize its excessive running time as a major reason towards non-adoption.²²2The reason why these works focus on Trevisan’s extractor is that this is the best seeded extractor (in terms of asymptotic seed length) that is known to be secure against quantum adversaries [DPVR12]. Instead, they have to rely on extractors based on universal hash functions, which, as mentioned above, are fast but require very large seeds.

This state of affairs motivates the following question, which is the main focus of this work:

Can we construct strong $(k,\varepsilon)$ -seeded extractors with seed length $d=O(\log(n/\varepsilon))$ and output length $m=(1-\eta)k$ computable in nearly-linear time, for arbitrary error $\varepsilon$ ?

Progress on this problem would immediately lead to faster implementations of many cryptographic protocols that use seeded extractors.

1.1 Our Contributions

We make progress on the construction of nearly-linear time extractors.

Seeded extractors with order-optimal seed length and large output length.

We construct nearly-linear time strong seeded extractors with order-optimal seed length and large output length for any $k$ and $\varepsilon$ , with the caveat that they require a one-time preprocessing step whenever $k=O(\log^{2}(n/\varepsilon))$ . This preprocessing step corresponds to finding primitive elements of finite fields $\mathds{F}_{q}$ with $q=\operatorname{poly}(n/\varepsilon)$ , which, as we discuss below, is reasonable in practical applications. More precisely, we have the following result.

Theorem 1.

For any constant $\eta>0$ there exists a constant $C>0$ such that the following holds. For any positive integers $n$ and $k\leq n$ and any $\varepsilon>0$ satisfying $k\geq C\log(n/\varepsilon)$ there exists a strong $(k,\varepsilon)$ -seeded extractor

\mathsf{Ext}\colon\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m}

with seed length $d\leq C\log(n/\varepsilon)$ and output length $m\geq(1-\eta)k$ . Furthermore,

•

if $k\geq 2^{C\log^{*}\!n}\cdot\log^{2}(n/\varepsilon)$ , then $\mathsf{Ext}$ is computable in time $\widetilde{O}(n)$ , where $\widetilde{O}(\cdot)$ hides polylogarithmic factors in its argument and $\log^{*}\!$ denotes the iterated logarithm;
•

if $k<2^{C\log^{*}\!n}\cdot\log^{2}(n/\varepsilon)$ , then $\mathsf{Ext}$ is computable in time $\widetilde{O}(n)$ after a preprocessing step, corresponding to finding a primitive element of $\mathds{F}_{q}$ with $q=\operatorname{poly}(n/\varepsilon)$ a power of $2$ .³³3In full rigor, the preprocessing step corresponds to finding primitive elements of $O(\log\log n)$ fields $\mathds{F}_{q}$ with orders $q\leq\operatorname{poly}(n/\varepsilon)$ , each a power of $2$ . This $O(\log\log n)$ term has negligible influence on the complexity of this preprocessing step. Note that we can find such a primitive element in time $\operatorname{polylog}(n/\varepsilon)$ if $q\leq\operatorname{poly}(n/\varepsilon)$ is a power of $2$ and we know the factorization of $q-1$ , but we do not know how to do that in time $\widetilde{O}(\log q)$ . More precisely, given the factorization of $q-1$ we can test whether a given $\alpha\in\mathds{F}_{q}$ is primitive in time $\operatorname{polylog}(q)$ by checking whether $\alpha^{\frac{q-1}{p}}\neq 1$ for all prime factors $p$ of $q-1$ . We can exploit this in various ways. If we are fine with using randomness in the one-time preprocessing stage, then we can sample an element of $\mathds{F}_{q}$ uniformly at random, test whether it is primitive, and repeat if not. If we insist on a deterministic algorithm, then we can combine the testing procedure with algorithms of Shoup [Sho90] or Shparlinski [Shp92] which identify in time $\operatorname{polylog}(q)$ a subset of size $\operatorname{polylog}(q)$ in $\mathds{F}_{q}$ that is guaranteed to contain a primitive element. For an alternative faster randomized algorithm, see [DD06].

1 follows from combining modern condensers with short seeds (namely, the lossless condenser of Kalev and Ta-Shma [KT22] and the lossy Reed-Solomon-based condenser of Guruswami, Umans, and Vadhan [GUV09]) with a careful combination and instantiation of classical recursive approaches developed by Srinivasan and Zuckerman [SZ99] and in [GUV09]. It readily implies, among other things, an $\widetilde{O}(n)$ -time privacy amplification protocol where only $O(\log(n/\varepsilon))$ bits need to be communicated over the one-way authenticated public channel and almost all the min-entropy can be extracted (after a reasonable one-time preprocessing step if the min-entropy bound $k$ is very small).

A new non-recursive construction.

As a conceptual contribution which may be of independent interest, we present a new “non-recursive” construction of extractors with seed length $O(\log(n/\varepsilon))$ and output length $(1-\eta)k$ that is computable in nearly-linear time when $k>\operatorname{polylog}(1/\varepsilon)$ and avoids the complicated recursive procedures from [SZ99, GUV09]. We believe this to be a conceptually better approach towards constructing seeded extractors, and we discuss it in more detail in the technical overview.

Faster instantiations of Trevisan’s extractor.

One of the most widely-used explicit seeded extractors is Trevisan’s extractor [Tre01, RRV02]. While by now we have extractors with better parameters, one of its main advantages is that it is one of the few examples of extractors, and in a sense the best one, which are known to be quantum proof.⁴⁴4An extractor is quantum proof if its output is close to uniform even in the presence of a quantum adversary that has some (bounded) correlation with $X$ . A bit more formally, $\mathsf{Ext}$ is quantum-proof if for all classical-quantum state $\rho_{XE}$ (where $E$ is a quantum state correlated with $X$ ) with $H_{\infty}(X|E)\geq k$ , and a uniform seed $Y$ , it holds that $\rho_{\mathsf{Ext}(X,Y)YE}\approx_{\varepsilon}\rho_{U_{m}}\otimes\rho_{Y}\otimes\rho_{E}$ . See [DPVR12] for more details.

Trevisan’s extractor uses two basic primitives: combinatorial designs (when more than one output bit is desired), and binary list-decodable codes. A standard instantiation of such suitable codes goes by concatenating a Reed-Solomon code with a Hadamard code, and this is also what is considered in [FWE⁺23, FYEC24]. As they also observe, this gives a nearly-linear time construction when the output length $m=1$ . In fact, by leveraging fast multipoint evaluation, one can also get a nearly-linear time construction for any output length $m\leq\frac{n}{\log(1/\varepsilon)}$ , although this was not noted in previous works.⁵⁵5For a rigorous statement on fast multipoint evaluation, see Lemma 2.1.

Our main contribution in this direction is an alternative instantiation of Trevisan’s extractor that can be computed in truly linear time on a RAM in the logarithmic cost model, for any output length $m\leq\frac{n}{\log(1/\varepsilon)\cdot\operatorname{polylog}(n)}$ .

Theorem 2.

There exists an instantiation of Trevisan’s extractor, set to extract $m$ bits with any error $\varepsilon>0$ , that is computable in:

1.

Time $O(n)+m\log(1/\varepsilon)\cdot\operatorname{polylog}(n)$ after a preprocessing step running in time $\widetilde{O}(m\log(n/\varepsilon))$ , on a RAM in the logarithmic cost model. In particular, there exists a universal constant $c$ , such that whenever $m\leq\frac{n}{\log(1/\varepsilon)\cdot\log^{c}(n)}$ , the instantiation runs in time $O(n)$ , without the need for a preprocessing step.
2.

Time $\widetilde{O}(n+m\log(1/\varepsilon))$ in the Turing model.

We note that one interesting instantiation of the above theorem is when Trevisan’s extractor is set to output $k^{\Omega(1)}$ bits for $k=n^{\Omega(1)}$ . In this setting, Trevisan’s extractor requires a seed of length $O\mathopen{}\mathclose{{}\left(\frac{\log^{2}(n/\varepsilon)}{\log(1/\varepsilon)}}\right)$ , and, as long as $\varepsilon$ is not too tiny, we get truly-linear runtime.

1.2 Other Related Work

Besides the long line of work focusing on improved constructions of explicit seeded extractors and mentioned in the introduction above, other works have studied randomness extraction in a variety of restricted computational models. These include extractors computable by streaming algorithms [BRST02], local algorithms [Lu02, Vad04, BG13, CL18], AC⁰ circuits [GVW15, CL18, CW24], AC⁰ circuits with a layer of parity gates [HIV22], NC¹ circuits [CW24], and low-degree polynomials [ACG⁺22, AGMR24, GGH⁺24]. Moreover, implementations in various restricted computational models of other fundamental pseudorandomness primitives such as $k$ -wise and $\varepsilon$ -biased generators, that often play a key role in constructions of various types of extractors, have also been independently studied (see [HV06, Hea08, CRSW13, MRRR14] for a very partial list).

As mentioned briefly above, some works have also focused on constructing seeded extractors computable in time $O(n\log n)$ motivated by applications in privacy amplification for quantum key distribution. Such constructions are based on hash functions, and are thus far restricted to $\Omega(m)$ seed length. The work of Hayashi and Tsurumaru [HT16] presents an extensive discussion of such efforts. We also mention that nearly-linear time extractors with very short seed, in the regime $k=n^{\Omega(1)}$ and $\varepsilon=n^{-o(1)}$ , were given in [DMOZ22], with applications in derandomization.

1.3 Technical Overview

In a nutshell, we obtain 1 by following two standard high-level steps:

1.

We apply a randomness condenser with small seed length $O(\log(n/\varepsilon))$ to the original $n$ -bit weak source $X$ to obtain an output $X^{\prime}$ that is $\varepsilon$ -close to a high min-entropy source.
2.

We apply a seeded extractor tailored to high min-entropy sources with small seed length $O(\log(n/\varepsilon))$ to $X^{\prime}$ to obtain a long output that is $\varepsilon$ -close to uniform.

To realize this approach, we need to implement each of these steps in nearly-linear time $\widetilde{O}(n)$ (possibly after a reasonable one-time preprocessing step). We briefly discuss how we achieve this, and some pitfalls we encounter along the way.

Observations about nearly-linear time condensers.

In order to implement Item 1, we need to use fast condensers with short seeds. Luckily for us, some existing state-of-the-art constructions of condensers already satisfy this property, although, to the best of our knowledge, this has not been observed before. We argue this carefully in Section 3.3.

For example, the “lossy Reed-Solomon condenser” from [GUV09] interprets the source as a polynomial $f\in\mathds{F}_{q}[x]$ of degree $d\leq n/\log q$ and the seed $y$ as an element of $\mathds{F}_{q}$ , and outputs $\mathsf{RSCond}(f,y)=(f(y),f(\zeta y),\dots,f(\zeta^{m^{\prime}}y))$ , for an appropriate $m^{\prime}$ and field size $q$ , with $\zeta$ a primitive element of $\mathds{F}_{q}$ . Evaluating $\mathsf{RSCond}(f,y)$ corresponds to evaluating the same polynomial $f$ on multiple points in $\mathds{F}_{q}$ . This is an instance of the classical problem of multipoint evaluation in computational algebra, for which we know fast and practical algorithms (e.g., see [vzGG13, Chapter 10] or Lemma 2.1) running in time $\widetilde{O}((d+m^{\prime})\log q)=\widetilde{O}(n)$ , since $d\leq n/\log q$ and if $m^{\prime}\leq n/\log q$ .

A downside of this condenser is that it requires knowing a primitive element $\zeta$ of $\mathds{F}_{q}$ with $q=\operatorname{poly}(n/\varepsilon)$ . As discussed above, if we know the factorization of $q-1$ and $q$ is a power of $2$ , then we can find such a primitive element in time $\operatorname{polylog}(q)$ . Beyond that, having access to such primitive elements, which only need to be computed once independently of the source and seed, is reasonable in practice. Therefore, we may leave this as a one-time preprocessing step.

The lossless “KT condenser” from [KT22] has a similar flavor. It interprets the source as a polynomial $f\in\mathds{F}_{q}[x]$ and the seed $y$ as an evaluation point, and outputs $\mathsf{KTCond}(f,y)=(f(y),f^{\prime}(y),\dots,f^{(m^{\prime})}(y))$ , for some appropriate $m^{\prime}$ . The problem of evaluating several derivatives of the same polynomial $f$ on the same point $y$ (sometimes referred to as Hermite evaluation) is closely related to the multipoint evaluation problem above, and can also be solved in time $\widetilde{O}(n)$ .⁶⁶6Interestingly, recent works used other useful computational properties of the KT condenser. Cheng and Wu [CW24] crucially use the fact that the KT condenser can be computed in NC¹. Doron and Tell [DT23] use the fact that the KT condenser is logspace computable for applications in space-bounded derandomization. Evaluating the KT condenser does not require preprocessing. On the other hand, it only works when the min-entropy $k\geq C\log^{2}(n/\varepsilon)$ for a large constant $C>0$ , where $n$ is the source length and $\varepsilon$ the target error of the condenser.

The “ideal” approach to seeded extraction from high min-entropy sources.

We have seen that there are fast condensers with short seeds. It remains to realize Item 2. Because of the initial condensing step, we may essentially assume that our $n$ -bit weak source $X$ has min-entropy $k\geq(1-\delta)n$ , for an arbitrarily small constant $\delta>0$ . In this case, we would like to realize in time $\widetilde{O}(n)$ and with overall seed length $O(\log(n/\varepsilon))$ what we see as the most natural approach to seeded extraction from high min-entropy sources:

1.

Use a fresh short seed to transform $X$ into a block source $Z=Z_{1}\circ Z_{2}\circ\cdots\circ Z_{t}$ with geometrically decreasing blocks, where $\circ$ denotes string concatenation. A block source has the property that each block $Z_{i}$ has good min-entropy even conditioned on the values of blocks $Z_{1},\dots,Z_{i-1}$ .
2.

Perform block source extraction on $Z$ using another fresh short seed. Due to its special structure, we can extract a long random string from $Z$ using only the (small) seed length associated with extracting randomness from the smallest block $Z_{t}$ , which has length $O(\log(n/\varepsilon))$ .

The classical approach to Item 2 where we iteratively apply extractors based on universal hash functions with increasing output lengths to the blocks of $Z$ from right to left is easily seen to run in time $\widetilde{O}(n)$ and requires a seed of length $O(\log(n/\varepsilon))$ if, e.g., we use the practical extractors of [TSSR11, HT16]. Therefore, we only need to worry about realizing Item 1.

A standard approach to Item 1 would be to use an averaging sampler to iteratively sample subsequences of $X$ as the successive blocks of the block source $Z$ , following a classical strategy of Nisan and Zuckerman [NZ96] (improved by [RSW06, Vad04]). We do know averaging samplers running in time $\widetilde{O}(n)$ (such as those based on random walks on a carefully chosen expander graph). However, this approach requires a fresh seed of length $\Theta(\log(n/\varepsilon))$ per block of $Z$ . Since $Z$ will have roughly $\log n$ blocks, this leads to an overall seed of length $\Theta(\log^{2}n+\log(1/\varepsilon))$ , which is too much for us.

Instead, we provide a new analysis of a sampler based on bounded independence, that runs in time $\widetilde{O}(n)$ and only requires a seed of length $O(\log(n/\varepsilon))$ to create the entire desired block source. We give the construction, which may be of independent interest, in Section 3.2. The caveat of this “block source creator” is that it only works as desired when the target error $\varepsilon\geq 2^{-k^{c}}$ for some small constant $c>0$ . Combining these realizations of Items 1 and 2 yields the desired $\widetilde{O}(n)$ -time extractor with order-optimal seed length $O(\log(n/\varepsilon))$ and output length $(1-\eta)n$ for arbitrary constant $\eta>0$ , provided that $\varepsilon\geq 2^{-k^{c}}$ . See Theorem 5.1 for the formal statement.

Getting around the limitation of the ideal approach.

We saw above that combining the ideal approach to seeded extraction from high min-entropy sources with the new analysis of the bounded independence sampler yields a conceptually simple construction with the desired properties when the error is not too small (or alternatively, whenever the entropy guarantee is large enough). However, we would like to have $\widetilde{O}(n)$ -time seeded extraction with $O(\log(n/\varepsilon))$ seed length and large output length for all ranges of parameters.

To get around this limitation of our first construction, it is natural to turn to other classical approaches for constructing nearly-optimal extractors for high min-entropy sources, such as those of Srinivasan and Zuckerman [SZ99] or Guruswami, Umans, and Vadhan [GUV09]. These approaches consist of intricate recursive procedures combining a variety of combinatorial objects, and require a careful analysis.⁷⁷7In our view, these approaches are much less conceptually appealing than the “ideal” approach above. We believe that obtaining conceptually simpler constructions of fast nearly-optimal extractors that work for all errors is a worthwhile research direction, even if one does not improve on the best existing parameters. However, we could not find such an approach that works as is, even when instantiated with $\widetilde{O}(n)$ -time condensers and $\widetilde{O}(n)$ -time hash-based extractors. In particular:

•

The GUV approach [GUV09] gives explicit seeded extractors with large output length and order-optimal seed length for any min-entropy requirement $k$ and error $\varepsilon$ . However, its overall runtime is significantly larger than $\widetilde{O}(n)$ whenever $\varepsilon$ is not extremely small (for example, $\varepsilon=2^{-k^{\alpha}}$ for some $\alpha\in(0,1/2)$ is not small enough).
•

The SZ approach [SZ99] can be made to run in time $\widetilde{O}(n)$ and have large output length when instantiated with fast condensers, samplers, and hash-based extractors, but it is constrained to error $\varepsilon\geq 2^{-ck/\log^{*}\!n}$ , where $\log^{*}$ is the iterated logarithm.

Fortunately, the pros and cons of the GUV and SZ approaches complement each other. Therefore, we can obtain our desired result by applying appropriately instantiated versions of the GUV and SZ approaches depending on the regime of $\varepsilon$ we are targeting.

1.4 Future Work

We list here some directions for future work:

•

Remove the preprocessing step that our constructions behind 1 require when $k<C\log^{2}(n/\varepsilon)$ .
•

On the practical side, develop concrete implementations of seeded extractors with near-optimal seed length and large output length. In particular, we think that our non-recursive construction in Section 5.1 holds promise in this direction.

1.5 Acknowledgements

Part of this research was done while the authors were visiting the Simons Institute for the Theory of Computing, supported by DOE grant # DE-SC0024124. D. Doron’s research was also supported by Instituto de Telecomunicações (ref. UIDB/50008/2020) with the financial support of FCT - Fundação para a Ciência e a Tecnologia and by NSF-BSF grant #2022644. J. Ribeiro’s research was also supported by Instituto de Telecomunicações (ref. UIDB/50008/2020) and NOVA LINCS (ref. UIDB/04516/2020) with the financial support of FCT - Fundação para a Ciência e a Tecnologia.

2 Preliminaries

2.1 Notation

We often use uppercase roman letters to denote sets and random variables – the distinction will be clear from context. We denote the support of a random variable $X$ by $\mathsf{supp}(X)$ , and, for a random variable $X$ and set $S$ , we also write $X\sim S$ to mean that $X$ is supported on $S$ . For a random variable $X$ , we write $x\sim X$ to mean that $x$ is sampled according to the distribution of $X$ . We use $U_{d}$ to denote a random variable that is uniformly distributed over $\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}$ . For two strings $x$ and $y$ , we denote their concatenation by $x\circ y$ . Given two random variables $X$ and $Y$ , we denote their product distribution by $X\times Y$ (i.e., $\Pr[X\times Y=x\circ y]=\Pr[X=x]\cdot\Pr[Y=y]$ . Given a positive integer $n$ , we write $[n]=\{1,\dots,n\}$ . For a prime power $q$ , we denote the finite field of order $q$ by $\mathds{F}_{q}$ . We denote the base- $2$ logarithm by $\log$ .

2.2 Model of Computation

We work in the standard, multi-tape, Turing machine model with some fixed number of work tapes. In particular, there exists a constant $C$ such that all our claimed time bounds hold whenever we work with at most $C$ work tapes. This also implies that our results hold in the RAM model, wherein each machine word can store integers up to some fixed length, and standard word operations take constant time. In Section 4 we will give, in addition to the standard Turing machine model bounds, an improved runtime bound that is dedicated to the logarithmic-cost RAM model.

2.3 Fast Finite Fields Operations

For a prime power $q=p^{\ell}$ , we let $M_{q}(d)$ be the number of field operations required to multiply two univariate polynomials over $\mathds{F}_{q}$ of degree less than $d$ , and $M_{q}^{\mathsf{b}}(d)$ be the bit complexity of such a multiplication, so $M_{q}^{\mathsf{b}}(d)\leq M_{q}(d)\cdot T(q)$ , where we denote by $T(q)$ an upper bound on the bit complexity of arithmetic operations in $\mathds{F}_{q}$ . When $\ell=1$ , Harvey and van der Hoeven [HvdH19, HvdH21] showed that

M^{\mathsf{b}}_{q}(d)=O(d\log q\cdot\log(d\log q)\cdot 4^{\max(0,\log^{*}\!d-\log^{*}\!q)}),

and in general, $M_{q}(d)=d\cdot\log d\cdot 2^{O(\log^{\star}n)}$ [Für09].⁸⁸8If $\mathds{F}_{q}$ contains a $d$ -th root of unity, one can get $M_{q}(d)=d\log d$ from the classic FFT algorithm [CT65]. For a simpler algorithm attaining the bound $M_{q}(d)=d\log d\operatorname{loglog}d$ , see [vzGG13, Sections 8,10]. See also [HvdH22] for a widely-believed conjecture under which $M_{q}(d)=d\log d$ always holds. When $p=2$ , we can use Schönhage’s algorithm [Sch77] to get $M_{q}^{\mathsf{b}}(d)=O(d\log d\cdot\operatorname{loglog}d\cdot M_{q}(\log q)),$ where we relied on the fact that addition and multiplication in $\mathds{F}_{q}$ can be done in time $M_{q}(\ell)=O(\ell\cdot\log\ell\cdot\operatorname{loglog}\ell)$ . Overall, when $d\leq q\leq 2^{d}$ , and $q$ is either a prime or a power of two, $M_{q}^{\mathsf{b}}(d)=d\log d\cdot\widetilde{O}(\log q)$ . We will use fast multi-point evaluation and fast computation of derivatives (together with the preceding bounds on $M_{q}^{\mathsf{b}}$ ).

Lemma 2.1 ([BM74], see also [vzGG13, Chapter 10]).

Let $d\in\mathbb{N}$ , and let $q$ be a prime, or a power of $2$ . Then, given a polynomial $f\in\mathds{F}_{q}[X]$ of degree at most $d$ , the following holds.

1.

Given a set $\mathopen{}\mathclose{{}\left\{{\alpha_{1},\ldots,\alpha_{t}}}\right\}\subseteq\mathds{F}_{q}$ , where $t\leq d$ , one can compute $f(\alpha_{1}),\ldots,f(\alpha_{t})$ in time $O(M^{\mathsf{b}}_{q}(d)\cdot\log d)=d\log^{2}d\cdot\widetilde{O}(\log q)$ .
2.

For $t\leq d$ and $\alpha\in\mathds{F}_{q}$ , one can compute the derivatives $f(\alpha),f^{\prime}(\alpha),\ldots,f^{(t)}(\alpha)$ in time $O(M_{q}(d)\cdot\log d)=d\log^{2}d\cdot\widetilde{O}(\log q)$ .

Note that when $q\leq 2^{d}$ , we can bound $O(M_{q}(d)\cdot\log d)$ by $\widetilde{O}(d)\cdot\log q$ .⁹⁹9The looser bound of $\widetilde{O}(d)\cdot\log q$ , when $q\leq 2^{d}$ , is also a bound for an arbitrary $\mathds{F}_{q}$ , and can be achieved with simpler algorithms than the ones cited.

For a comprehensive discussion of fast polynomial arithmetic, see Von Zur Gathen and Gerhard’s book [vzGG13] (and the more recent important developments [HvdH21]).

2.4 Statistical Distance, Entropy

We present some relevant definitions and lemmas about the statistical distance and min-entropy.

Definition 2.2 (statistical distance).

The statistical distance between two random variables $X$ and $Y$ supported on $\mathcal{S}$ , denoted by $\Delta(X,Y)$ , is defined as

\Delta(X,Y)=\sup_{\mathcal{T}\subseteq\mathcal{S}}|\Pr[X\in\mathcal{T}]-\Pr[Y\in\mathcal{T}]|=\frac{1}{2}\sum_{x\in\mathcal{S}}|\Pr[X=x]-\Pr[Y=x]|.

We say that $X$ and $Y$ are $\varepsilon$ -close, and write $X\approx_{\varepsilon}Y$ , if $\Delta(X,Y)\leq\varepsilon$ .

Definition 2.3 (min-entropy).

The min-entropy of a random variable $X$ supported on $\mathcal{X}$ , denoted by $\mathbf{H}_{\infty}(X)$ , is defined as

\mathbf{H}_{\infty}(X)=-\log\mathopen{}\mathclose{{}\left(\max_{x\in\mathcal{X}}\Pr[X=x]}\right).

Above, and throughout the paper, we use base- $2$ logarithms.

Definition 2.4 (average conditional min-entropy).

Let $X$ and $Y$ be two random variables supported on $\mathcal{X}$ and $\mathcal{Y}$ , respectively. The average conditional min-entropy of $X$ given $Y$ , denoted by $\widetilde{\mathbf{H}}_{\infty}(X|Y)$ , is defined as

\widetilde{\mathbf{H}}_{\infty}(X|Y)=-\log\mathopen{}\mathclose{{}\left(\mathds{E}_{y\sim Y}[2^{-\mathbf{H}_{\infty}(X|Y=y)}]}\right).

The following standard lemma gives a chain rule for min-entropy.

Lemma 2.5 (see, e.g., [DORS08]).

Let $X$ , $Y$ , and $Z$ be arbitrary random variables such that $|\mathsf{supp}(Y)|\leq 2^{\ell}$ . Then,

\widetilde{\mathbf{H}}_{\infty}(X|Y,Z)\geq\widetilde{\mathbf{H}}_{\infty}(X|Z)-\ell.

We can turn the chain rule above into a high probability statement.

Lemma 2.6 (see, e.g., [MW97]).

Let $X$ , $Y$ , and $Z$ be random variables such that $|\mathsf{supp}(Y)|\leq 2^{\ell}$ . Then,

\Pr_{y\sim Y}[\widetilde{\mathbf{H}}_{\infty}(X|Y=y,Z)\geq\widetilde{\mathbf{H}}_{\infty}(X|Z)-\ell-\log(1/\delta)]\geq 1-\delta

for any $\delta>0$ .

Definition 2.7 (smooth min-entropy).

We say that a random variable $X$ has $\varepsilon$ -smooth min-entropy at least $k$ , denoted by $\mathbf{H}_{\infty}^{\varepsilon}(X)\geq k$ , if there exists a random variable $X^{\prime}$ such that $X\approx_{\varepsilon}X^{\prime}$ and $\mathbf{H}_{\infty}(X^{\prime})\geq k$ .

2.5 Extractors and Condensers

Definition 2.8 ( $(n,k)$ -source).

We say that a random variable $X$ is an $(n,k)$ -source if $X\sim\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}$ and $\mathbf{H}_{\infty}(X)\geq k$ .

Definition 2.9 (block source).

A random variable $X$ is an $((n_{1},n_{2},\dots,n_{t}),(k_{1},\dots,k_{t}))$ -block source if we can write $X=X_{1}\circ X_{2}\circ\cdots\circ X_{t}$ , each $X_{i}\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n_{i}}$ , where $\widetilde{\mathbf{H}}_{\infty}(X_{i}|X_{1},\ldots,X_{i-1})\geq k_{i}$ for all $i\in[s]$ . In the special case where $k_{i}=\alpha n_{i}$ for all $i\in[t]$ , we say that $X$ is an $((n_{1},n_{2},\dots,n_{t}),\alpha)$ -block source.

We say that $X$ is an exact block source if $\mathbf{H}_{\infty}(X_{i}|X_{1}=x_{1},\ldots,X_{i-1}=x_{i-1})\geq k_{i}$ for any prefix $x_{1},\dots,x_{i-1}$ . Lemma 2.6 tells us that any $((n_{1},\ldots,n_{t}),\alpha)$ -block-source is $\varepsilon$ -close to an exact $((n_{1},\ldots,n_{t}),(1-\zeta)\alpha)$ -block-source, where $\varepsilon=\sum_{i=1}^{t}2^{-\alpha\zeta n_{i}}$ .

Definition 2.10 (seeded extractor).

A function $\mathsf{Ext}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\rightarrow\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m}$ is a $(k,\varepsilon)$ seeded extractor if the following holds. For every $(n,k)$ -source $X$ ,

\mathsf{Ext}(X,Y)\approx_{\varepsilon}U_{m},

where $Y$ is uniformly distributed over $\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}$ and is independent of $X$ and $U_{m}$ is uniformly distributed over $\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m}$ . We say that $\mathsf{Ext}$ is strong if $\mathsf{Ext}(X,Y)\circ Y\approx_{\varepsilon}U_{m+d}$ .

Furthermore, $\mathsf{Ext}$ is said to be an average-case $(k,\varepsilon)$ (strong seeded) extractor if for all correlated random variables $X$ and $W$ such that $X$ is supported on $\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}$ and $\widetilde{\mathbf{H}}_{\infty}(X|W)\geq k$ we have

\mathsf{Ext}(X,Y)\circ Y\circ W\approx_{\varepsilon}U_{m+d}\circ W,

where $Y$ is uniformly distributed over $\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}$ and is independent of $X$ and $U_{m+d}$ is uniformly distributed over $\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m+d}$ and independent of $W$ .

Remark 2.11.

By Lemma 2.6, every strong $(k,\varepsilon)$ -seeded extractor $\mathsf{Ext}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\to\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m}$ is also an average-case strong $(k^{\prime}=k+\log(1/\varepsilon),\varepsilon^{\prime}=2\varepsilon)$ -seeded extractor.

Definition 2.12 (condenser).

A function $\mathsf{Cond}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\rightarrow\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m}$ is a $(k,k^{\prime},\varepsilon)$ (seeded) condenser if the following holds. For every $(n,k)$ -source $X$ , $\mathbf{H}_{\infty}^{\varepsilon}(\mathsf{Cond}(X,Y))\geq k^{\prime}$ , where $Y$ is uniformly distributed over $\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}$ and is independent of $X$ .

We say that $\mathsf{Cond}$ is strong if $Y\circ\mathsf{Cond}(X,Y)$ is $\varepsilon$ -close to some distribution $Y\circ D$ with min-entropy $k^{\prime}$ (and note that here, necessarily, $d$ bits of entropy come from the seed). Finally, we say that $\mathsf{Cond}$ is lossless if $k^{\prime}=k+d$ .

We also define extractors tailored to block sources.

Definition 2.13 (block source extractor).

A function $\mathsf{BExt}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n_{1}}\times\cdots\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n_{t}}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\to\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m}$ is a $(k_{1},\dots,k_{t},\varepsilon)$ strong block-source extractor if for any $((n_{1},n_{2},\dots,n_{t}),(k_{1},\dots,k_{t}))$ -block-source $X$ ,

\mathsf{BExt}(X,Y)\circ Y\approx_{\varepsilon}U_{m+d},

We will also require the following extractors based on the leftover hash lemma and fast hash functions. We state a result from [TSSR11] which requires seed length $d\approx 2m$ , where $m$ is the output length. It is possible to improve the seed length to $d\approx m$ , but this requires the input length $n$ to be structured [HT16].

Lemma 2.14 (fast hash-based extractors [TSSR11, Theorem 10], adapted. See also [HT16, Table I]).

For any positive integers $n$ , $k$ , and $m$ and any $\varepsilon>0$ such that $k\leq n$ and $m\leq k-4\log(16/\varepsilon)$ there exists a $(k,\varepsilon)$ -strong seeded extractor $\mathsf{Ext}\colon\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m}$ with seed length $d\leq 2(m+\log n+2\log(1/\varepsilon)+4)$ . Moreover, $\mathsf{Ext}$ can be computed in time $O(n\log n)$ .

Note that by appending the seed to the output of the extractor, we can get the following: There exists a constant $c$ such that for any constant $\theta\leq\frac{1}{3}$ , $d\geq c\log(n/\varepsilon)$ and $k\geq\theta d+c\log(1/\varepsilon)$ , there exists a strong $(k,\varepsilon)$ -seeded extractor $\mathsf{Ext}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\rightarrow\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{(1+\theta)d}$ .

2.6 Averaging Samplers

In this section we define averaging samplers and state some useful related results and constructions.

Definition 2.15 (averaging sampler).

We say that $\mathsf{Samp}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{r}\to[n]^{m}$ is a $(\gamma,\theta)$ -averaging sampler if

\Pr_{(i_{1},\dots,i_{m})\sim\mathsf{Samp}(U_{r})}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left|\frac{1}{t}\sum_{j=1}^{m}f(i_{j})-\mathds{E}[f]}\right|\geq\theta}\right]<\gamma

for every function $f\colon[n]\to[0,1]$ , where $\mathds{E}[f]=\frac{1}{n}\sum_{i\in[n]}f(i)$ . We say that $\mathsf{Samp}$ has distinct samples if $\mathsf{Samp}(x)$ outputs $m$ distinct elements of $[n]$ for every input $x$ . The parameter $\theta$ is often referred to as the accuracy of the sampler, and $\gamma$ is its confidence parameter. Moreover, we sometimes refer to $\mathsf{Samp}(U_{r})\sim[n]^{m}$ as a $(\gamma,\theta)$ sampling distribution.

The following lemma gives guarantees on sub-sampling from a weak source using an averaging sampler.

Lemma 2.16 ([Vad04, Lemma 6.2]).

Let $\delta,\gamma,\tau\in(0,1)$ be such that $\delta\geq 3\tau$ and let $\mathsf{Samp}\colon\{0,1\}^{r}\to[n]^{m}$ be a $(\gamma,\theta=\tau/\log(1/\tau))$ -averaging sampler with distinct samples. Then, for any $(n,k=\delta n)$ -source $X$ and $Y$ uniformly distributed over $\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{r}$ we have that

Y\circ X_{\mathsf{Samp}(Y)}\approx_{\gamma+2^{-\Omega(\tau n)}}Y\circ W,

where $(W|Y=y)$ is an $(m,k^{\prime}=(\delta-3\tau)m)$ -source for every $y$ .

The “expander random walk” sampler.

We will need the following averaging sampler based on random walks on expanders. Let $G$ be a $D$ -regular graph with vertex set $[n]$ . We assume that the neighborhood of each vertex is ordered in some predetermined way. Then, the associated averaging sampler parses its input $x$ as $(i_{1},b_{1},b_{2},\dots,b_{t-1})$ , where $i_{1}\in[n]$ and $b_{1},\dots,b_{t-1}\in[D]$ , and outputs $\mathsf{Samp}(x)=(i_{1},\dots,i_{t})$ , where $i_{j}$ is the $b_{j-1}$ -th neighbor of $i_{j-1}$ when $j>1$ . To ensure distinct samples, we skip repeated vertices.

The performance of $\mathsf{Samp}$ as an averaging sampler is determined by the spectral expansion of $G$ . In fact, if $G$ has spectral expansion $\theta/2$ then a direct application of the expander Chernoff bound [Gil98] gives that $\mathsf{Samp}$ is a $(\gamma,\theta)$ -averaging sampler with $t=O(\log(1/\gamma)/\theta^{2})$ and $r=\log n+O(t\log(1/\theta))$ [Vad04, Section 8.2]. We instantiate $G$ with the regular expander graphs from the following result of Alon [Alo21].

Lemma 2.17 ([Alo21, Theorem 1.2], adapted).

Fix any prime $p$ such that $p\equiv 1\mod 4$ . Then, there is a constant $C_{p}$ such that for every integer $n\geq C_{p}$ there exists a $(D=p+2)$ -regular graph $G_{n}$ on $n$ vertices with spectral expansion $\lambda\leq\frac{(1+\sqrt{2})\sqrt{d-1}+o(1)}{d}$ , where the $o(1)$ tends to $0$ as $n\to\infty$ . Furthermore, the family $(G_{n})_{n}$ is strongly explicit.

In particular, for any $\theta>0$ there exist constants $C_{\theta}>0$ and $D_{\theta}=O(\theta^{-2})$ and a strongly explicit family of $D_{\theta}$ -regular graphs $(G_{n})_{n\geq C_{\theta}}$ with spectral expansion $\lambda\leq\theta$ for any $n\geq C_{\theta}$ .

Taking the $t$ -th power of a $\lambda$ -spectral expander improves its expansion to $\lambda^{t}$ . This readily gives us the following corollary.

Corollary 2.18.

For every large enough $n$ , and any $\lambda=\lambda(n)>0$ , there exists a $D$ -regular graph $G=(V=[n],E)$ with spectral expansion $\lambda$ , where $D=\operatorname{poly}(1/\lambda)$ , and given $x\in[n]$ and $i\in[D]$ , the $y$ -th neighbor of $x$ can be computed in time $\log(1/\lambda)\cdot\operatorname{polylog}(n)$ .

Combining the discussion above with Lemma 2.17 (or Corollary 2.18) immediately yields the following.

Lemma 2.19 ([Vad04, Lemma 8.2], appropriately instantiated).

For every large enough integer $n$ and every $\theta,\gamma\in(0,1)$ , there exists a $(\gamma,\theta)$ -averaging sampler $\mathsf{Samp}\colon\{0,1\}^{r}\to[n]^{t}$ with distinct samples with $t=O(\log(1/\gamma)/\theta^{2})$ and $r=\log n+O(t\log(1/\theta))$ . Furthermore, $\mathsf{Samp}$ is computable in time $O(t\cdot\operatorname{polylog}n)$ .

We can extend Lemma 2.19 to output more distinct samples while not increasing $r$ via the following simple lemma.

Lemma 2.20 ([Vad04, Lemma 8.3]).

Suppose that $\mathsf{Samp}_{0}\colon\{0,1\}^{r}\to[n]^{t}$ is a $(\gamma,\theta)$ -averaging sampler with distinct samples. Then, for every integer $m\geq 1$ there exists a $(\gamma,\theta)$ -averaging sampler $\mathsf{Samp}\colon\{0,1\}^{r}\to[m\cdot n]^{m\cdot t}$ with distinct samples. Furthermore, if $\mathsf{Samp}_{0}$ is computable in time $T$ , then $\mathsf{Samp}$ is computable in time $O(mT)$ .

Lemma 2.20 follows easily by parsing $[m\cdot t]=[m]\times[t]$ and considering the sampler $\mathsf{Samp}(x)_{i,j}=(i,\mathsf{Samp}_{0}(x)_{j})$ for $i\in[m]$ and $j\in[t]$ . If we can compute $\mathsf{Samp}_{0}(x)$ in time $T$ , then we can compute $\mathsf{Samp}(x)$ in time $O(mT)$ , as desired. The following is an easy consequence of Lemmas 2.19 and 2.20.

Lemma 2.21 ([Vad04, Lemma 8.4], with additional complexity claim).

There exists a constant $C>0$ such that the following holds. For every large enough $n$ and $\theta,\gamma\in(0,1)$ , there exists a $(\gamma,\theta)$ -averaging sampler $\mathsf{Samp}\colon\{0,1\}^{r}\to[n]^{t}$ with distinct samples for any $t\in[t_{0},n]$ with $t_{0}\leq C\log(1/\gamma)/\theta^{2}$ and $r=\log(n/t)+\log(1/\gamma)\cdot\operatorname{poly}(1/\theta)$ . Furthermore, $\mathsf{Samp}$ is computable in time $t\cdot\operatorname{poly}(1/\theta,\log n)$ .

In particular, if $\theta$ is constant then $t_{0}=O(\log(1/\gamma))$ , $r=\log(n/t)+O(\log(1/\gamma))$ , and $\mathsf{Samp}$ is computable in time $t\cdot\operatorname{polylog}n$ .

2.7 Standard Composition Techniques for Extractors

We collect some useful classical techniques for composing seeded extractors.

Lemma 2.22 (boosting the output length [WZ99, RRV02]).

Suppose that for $i\in\{1,2\}$ there exist strong $(k_{i},\varepsilon_{i})$ -seeded extractors $\mathsf{Ext}_{i}\colon\{0,1\}^{n}\times\{0,1\}^{d_{i}}\to\{0,1\}^{m_{i}}$ running in time $T_{i}$ , with $k_{2}\leq k_{1}-m_{1}-g$ . Then, $\mathsf{Ext}\colon\{0,1\}^{n}\times\{0,1\}^{d_{1}+d_{2}}\to\{0,1\}^{m_{1}+m_{2}}$ given by $\mathsf{Ext}(X,(Y_{1},Y_{2}))=\mathsf{Ext}_{1}(X,Y_{1})\circ\mathsf{Ext}(X,Y_{2})$ is a strong $(k_{1},\frac{\varepsilon_{1}}{1-2^{-g}}+\varepsilon_{2})$ -seeded extractor running in time $O(T_{1}+T_{2})$ .

Lemma 2.23 (block source extraction).

Let $X=X_{1}\circ\cdots\circ X_{t}$ be an $((n_{1},\dots,n_{t}),(k_{1},\dots,k_{t}))$ -block-source, and let $\mathsf{Ext}_{i}\colon\{0,1\}^{n_{i}}\times\{0,1\}^{d_{i}}\to\{0,1\}^{m_{i}}$ be average-case strong $(k_{i},\varepsilon_{i})$ -seeded extractors running in time $T_{i}$ with output length $m_{i}\geq d_{i-1}-d_{i}$ for $i\geq 2$ . Then, there exists a strong $(k_{1},\dots,k_{t},\varepsilon=\sum_{i\in[t]}\varepsilon_{i})$ -block-source extractor $\mathsf{BExt}\colon\{0,1\}^{n_{1}}\times\cdots\times\{0,1\}^{n_{t}}\times\{0,1\}^{d_{t}}\to\{0,1\}^{m}$ with output length $m=m_{1}+\sum_{i=2}^{t}(m_{i}-(d_{i-1}-d_{i}))$ that runs in time $O(\sum_{i\in[t]}T_{i})$ . If $X$ is an exact block source, then the $\mathsf{Ext}_{i}$ ’s do not need to be average-case.

We discuss how the fast hash-based extractor from Lemma 2.14 can be used to construct a fast extractor with seed length any constant factor smaller than its output length for high min-entropy sources. We need the following lemma, which is an easy consequence of the chain rule for min-entropy.

Lemma 2.24 ([GUV09, Corollary 4.16]).

If $X$ is an $(n,k=n-\Delta)$ -source and we write $X=X_{1}\circ\cdots\circ X_{t}$ with $|X_{i}|\geq n^{\prime}$ for all $i\in[t]$ , then $X_{1}\circ\cdots\circ X_{t}$ is $t\varepsilon$ -close to an $(n_{1}=n^{\prime},\dots,n_{t}=n^{\prime},k^{\prime}=n^{\prime}-\Delta-\log(1/\varepsilon))$ -block-source.

The following appears in [GUV09] without the time complexity bound. We appropriately instantiate their approach and analyze the time complexity below.

Lemma 2.25 (fast extractors with seed shorter than output [GUV09, Lemma 4.11]).

For every integer $t\geq 1$ there exists a constant $C>0$ such that for any positive integer $n$ and $\varepsilon>2^{-\frac{n}{50t}}$ there exists a strong $(k=(1-\frac{1}{20t})n,\varepsilon)$ -seeded extractor $\mathsf{Ext}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\to\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m}$ with $m\geq k/2$ and $d\leq k/t+C\log(n/\varepsilon)$ computable in time $O(tn\log n)$ .

Proof.

Let $X$ be an $(n,k=(1-\frac{1}{20t})n)$ -source and $\varepsilon^{\prime}=\frac{\varepsilon}{2t}$ . Write $X$ as $X=X_{1}\circ\cdots\circ X_{t}$ with $|X_{i}|=\lfloor n/t\rfloor=n^{\prime}$ for all $i$ . Then, Lemma 2.24 guarantees that $X_{1}\circ\cdots\circ X_{t}$ is $(t\varepsilon^{\prime})$ -close to an $(n_{1}=n^{\prime},\dots,n_{t}=n^{\prime},k^{\prime}=n^{\prime}-\frac{n}{20t}-\log(1/\varepsilon^{\prime}))$ -block-source $X^{\prime}$ . Note that

k^{\prime}=n^{\prime}-\frac{n}{20t}-\log(1/\varepsilon^{\prime})\geq\frac{19n}{20t}-1-\log(1/\varepsilon^{\prime})\geq 0.9n^{\prime},

since we have assumed that $\varepsilon>2^{-\frac{n}{50t}}$ . Now, let $\mathsf{Ext}^{\prime}\colon\{0,1\}^{n^{\prime}}\times\{0,1\}^{d}\to\{0,1\}^{m}$ be the strong $(k^{\prime},\varepsilon^{\prime})$ -seeded extractor from Lemma 2.14 with output length $m=\mathopen{}\mathclose{{}\left\lceil\frac{k}{2t}}\right\rceil\leq k-4\log(16/\varepsilon^{\prime})$ and corresponding seed length $d\leq k/t+4\log(n/\varepsilon^{\prime})+9\leq k/t+C\log(n/\varepsilon)$ for a large enough constant $C>0$ depending only on $t$ . Then, we apply block source extraction (Lemma 2.23) to $X^{\prime}$ with $\mathsf{Ext}_{1}=\cdots=\mathsf{Ext}_{t}=\mathsf{Ext}^{\prime}$ to get the desired strong $(k,2t\varepsilon^{\prime}=\varepsilon)$ -extractor $\mathsf{Ext}$ with output length $t\cdot m\geq k/2$ and seed length $d$ . Since $\mathsf{Ext}^{\prime}$ is computable in time $O(n\log n)$ , then $\mathsf{Ext}$ is computable in time $O(tn\log n)$ . ∎

In addition to Lemma 2.22, one can potentially boost the output length of a high min-entropy extractor by first treating the source as a block sources and then performing a simple block source extraction. The following corollary follows easily from Lemmas 2.23 and 2.24 (and can also be found in [Vad04, Section 6]).

Lemma 2.26.

Let $\mathsf{Ext}_{\mathsf{in}}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n/2}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{\ell}\rightarrow\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}$ and $\mathsf{Ext}_{\mathsf{out}}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n/2}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\rightarrow\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m}$ be $(k^{\prime},\varepsilon)$ -extractors. Then, for any $(n,k=\delta n)$ -source $X_{1}\circ X_{2}$ , each $X_{i}\sim\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n/2}$ , and an independent uniform $Y\sim\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{\ell}$ , we have that

\mathsf{Ext}((X_{1},X_{2}),Y)=\mathsf{Ext}_{\mathsf{out}}(X_{1},\mathsf{Ext}_{\mathsf{in}}(X_{2},Y))

is $4\varepsilon$ -close to uniform, assuming that $k^{\prime}\geq(\delta-\frac{3}{4})n$ and $\varepsilon\geq 2^{-n/4}$ . In other words, $\mathsf{Ext}$ is a $(k,4\varepsilon)$ -extractor. Moreover, if $\mathsf{Ext}_{\mathsf{in}}$ is strong then $\mathsf{Ext}$ is also strong, and if $\mathsf{Ext}_{\mathsf{in}}$ and $\mathsf{Ext}_{\mathsf{out}}$ run in time $T_{1}$ and $T_{2}$ , respectively, then $\mathsf{Ext}$ runs in time $O(T_{1}+T_{2})$ .

3 Additional Building Blocks

3.1 Fast Generation of Small-Bias Sets

A set $S\subseteq\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}$ is $\varepsilon$ -biased if the uniform distribution over its elements is indistinguishable from uniform by every linear test. Namely, if for every nonempty $T\subseteq[n]$ it holds that $\Pr_{s\sim S}[\bigoplus_{i\in T}s_{i}]\in[\frac{1-\varepsilon}{2},\frac{1+\varepsilon}{2}n]$ . We say that a linear code $\mathcal{C}\subseteq\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}$ is $\varepsilon$ -balanced if the Hamming weight of each nonzero codeword lies in $[\frac{1-\varepsilon}{2}n,\frac{1+\varepsilon}{2}]$ . It is known that these two objects are essentially the same: $S$ is $\varepsilon$ -biased if and only if the $|S|\times n$ matrix whose rows are the elements of $S$ is a generator matrix of an $\varepsilon$ -balanced code.

One prominent way of constructing $\varepsilon$ -balanced codes is via distance amplification, namely, starting with a code of some bias $\varepsilon_{0}\gg\varepsilon$ and, using a parity sampler, amplify its bias. We will use a specific, simple, instantiation of a parity sampler – the random walk sampler.

Lemma 3.1 (RWs amplify bias [Ta-17]¹⁰¹⁰10The argument for $t=2$ was suggested already by Rozenman and Wigderson (see [Bog12]).).

Let $\mathcal{C}_{0}\subseteq\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}$ be an $\varepsilon_{0}$ -balanced code, and let $G=(V=[n],E)$ be a $D$ -regular $\lambda$ -spectral expander, and for an even $t\in\mathbb{N}$ , let $\mathcal{W}_{t}=\mathopen{}\mathclose{{}\left\{{w_{1},\ldots,w_{\bar{n}}}}\right\}\subseteq[n]^{t}$ be the set of walks of length $t$ on $G$ , noting that $\bar{n}=n\cdot D^{t}$ . Define $\mathcal{C}\subseteq\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{\bar{n}}$ such that

\mathcal{C}=\mathopen{}\mathclose{{}\left\{{\mathrm{dsum}_{\mathcal{W}_{t}}(c_{0}):c_{0}\in\mathcal{C}_{0}}}\right\},

where $y=\mathrm{dsum}_{\mathcal{W}_{t}}(x)$ at location $i\in[\bar{n}]$ is given by $\bigoplus_{j\in w_{i}}x_{j}$ .

Then, $\mathcal{C}$ is $\varepsilon$ -balanced, for

\varepsilon=\mathopen{}\mathclose{{}\left(\varepsilon_{0}+2\lambda}\right)^{t/2}.

For $\mathcal{C}_{0}$ , we will use the Justesen code.

Lemma 3.2 ([Jus72]).

There exist constants $R\in(0,1)$ and $\varepsilon_{0}\in(0,1)$ such that there exists an explicit family of codes $\mathopen{}\mathclose{{}\left\{{\mathrm{Jus}_{n}}}\right\}$ , each of which has block length $n$ , rate $R$ , and is $\varepsilon_{0}$ -balanced. Moreover, given $x\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{k=Rn}$ , $\mathrm{Jus}_{n}(x)$ can be computed in $\widetilde{O}(n)$ .

Proof.

The parameters of the codes follow from the original construction (and specifically, the lemma holds, say, with $R=\frac{1}{8}$ and $\varepsilon_{0}=\frac{37}{40}$ ), so we will just show that the code is efficiently computable. Given a message $x$ , we first encode it with a full Reed–Solomon code of constant relative distance over a field $\mathds{F}_{q}$ of characteristic $2$ , where $q\log q=O(n)$ . By Lemma 2.1, this can be done in time $\widetilde{O}(q)=\widetilde{O}(n)$ . Then, we encode with polynomial evaluation $p_{x}(\alpha)$ , for $\alpha\in\mathds{F}_{q}$ , with the binary representation of $(p(\alpha),\alpha\cdot p(\alpha))$ . This takes $\widetilde{O}(q)$ time as well. ∎

Corollary 3.3.

There exist a constant $c>1$ , and an explicit family of balanced codes, such that for every $\bar{n}\in\mathbb{N}$ and any $\varepsilon>0$ , $\mathcal{C}\subseteq\mathds{F}_{2}^{\bar{n}}$ is $\varepsilon$ -balanced of rate $R=\varepsilon^{c}$ , and given $x\in\mathds{F}_{2}^{k=R\bar{n}}$ , any $m$ bits of $\mathcal{C}(x)$ can be computed in time $\widetilde{O}(n)+O(m\log(1/\varepsilon)\log n\operatorname{loglog}n)$ .

Moreover, for every $k\in\mathbb{N}$ and any $\varepsilon>0$ there exists an explicit $\varepsilon$ -biased set over $\mathds{F}_{2}^{k}$ generated by a function $\mathsf{SmallBias}\colon[\bar{n}]\rightarrow\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{k}$ computable in time $(k+\log(1/\varepsilon))\cdot\widetilde{O}(\log k)$ .

Proof.

Let $\mathcal{C}_{0}\colon\mathds{F}_{2}^{k=\Theta(n)}\rightarrow\mathds{F}_{2}^{n}$ be the $\varepsilon_{0}$ -balanced code guaranteed to us by Lemma 3.2, and let $G=(V=[n],E)$ be the $D$ -regular $\lambda$ -spectral expander of Corollary 2.18, instantiated with $\lambda=\frac{1-\varepsilon_{0}}{4}$ (so $D=D(\varepsilon_{0})$ ). Letting $\mathcal{C}\colon\mathds{F}_{2}^{k}\rightarrow\mathds{F}_{2}^{\bar{n}}$ be the amplified code of Lemma 3.1 set with

t=\frac{2\log(1/\varepsilon)}{\log\mathopen{}\mathclose{{}\left(\frac{1+\varepsilon_{0}}{2}}\right)}=O(\log(1/\varepsilon)),

the lemma tells us that it is $(\varepsilon_{0}+2\lambda)^{t/2}\leq\varepsilon$ balanced. Given $x\in\mathds{F}_{2}^{n}$ and $i\in[\bar{n}]$ , computing $\mathcal{C}(x)_{i}$ amounts to XORing $t$ coordinates of $\mathcal{C}_{0}(x)$ determined by $i=(v,i_{1},\ldots,i_{t})$ , which indexes a random walk over $G$ . Computing $\mathcal{C}_{0}(x)$ takes $\widetilde{O}(n)$ time, and computing a length- $t$ walk over $G$ takes $t\cdot O(\log(1/\lambda)\cdot\log n\cdot\operatorname{loglog}n)$ time. The corollary then follows, observing that $\bar{n}=n\cdot D^{t}=n\cdot\operatorname{poly}(1/\varepsilon)$ , and that

\widetilde{O}(n)+m\cdot t\cdot O(\log n\cdot\operatorname{loglog}n)=\widetilde{O}(n)+m\cdot\log(1/\varepsilon).

For the “Moreover” part, recall that we can take the rows of the generator matrix of $\mathcal{C}$ as our $\varepsilon$ -biased set $S$ . Thus, for any $i\in[\bar{n}]$ , we can compute $\mathsf{SmallBias}(i)$ as follows: Compute the corresponding random walk on $G$ , and then, for any $j\in[k]$ , $\mathsf{SmallBias}(i)_{j}$ is obtained by XORing the bits of $\mathcal{C}_{0}(e_{j})$ indexed by the $i$ -th random walk. Observing that each bit of $\mathcal{C}_{0}(e_{j})$ can be computed in time $\widetilde{O}(\log n)$ ,¹¹¹¹11Indeed, each coordinate of $\mathcal{C}_{0}(e_{j})$ is a bit in the encoding of $(\alpha^{j},\alpha^{j+1})$ for some $\alpha\in\mathds{F}_{q}$ , where $q\log q=O(n)$ . the runtime of $\mathsf{SmallBias}$ is

t\cdot O(\log(1/\lambda)\cdot\log n\cdot\operatorname{loglog}n)+k\cdot\widetilde{O}(\log n)=(k+\log(1/\varepsilon))\cdot\widetilde{O}(\log k).\qed

Remark 3.4.

Instead of using Justesen’s code from Lemma 3.2 as our inner code $\mathcal{C}_{0}$ , we can instead use the linear-time encodable code of Spielman [Spi96]. While not stated as balanced codes, but rather as constant relative distance codes, one can verify that the distance can also be bounded by above. The construction is more involved than Justesen’s one. However, in the logarithmic-cost RAM model, in which basic register operations over $O(\log n)$ bit registers count as a single time step, Spielman’s code can be implemented in $O(n)$ time.

3.2 A Sampler from Bounded Independence

Recall that $X_{1},\ldots,X_{n}\sim\Sigma^{n}$ is a $(b,\varepsilon)$ -wise independent distribution, if for every distinct $i_{1},\ldots,i_{b}\in[n]$ it holds that $(X_{i_{1}},\ldots,X_{i_{b}})$ is $\varepsilon$ -close to the uniform distribution over $\Sigma^{b}$ . Given our efficiently generated small biased spaces, we can efficiently generate almost $b$ -wise independent sample spaces as well.

Lemma 3.5.

For any positive integers $n$ , $m\leq n$ , and $b\leq m$ , and any $\varepsilon>0$ , there exists an explicit $(b,\varepsilon)$ -wise independent generator $\mathsf{BI}_{b,\varepsilon}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\rightarrow[n]^{m}$ with $d=O(b\log n+\log(1/\varepsilon))$ . That is, the distribution formed by picking $z\sim U_{d}$ and outputting $\mathsf{BI}_{b,\varepsilon}(z)$ is $(b,\varepsilon)$ -wise independent over $[n]^{m}$ . Moreover,

1.

Given $z\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}$ , $\mathsf{BI}_{b,\varepsilon}(z)$ is computable in time $\widetilde{O}(n)$ .
2.

Assume that $\theta\in(0,1/4)$ is such that $\varepsilon\leq\theta\cdot n^{-b/2}$ . Then, with probability at least $1-2^{-\Omega(\theta b)}$ over $z\sim U_{d}$ , $\mathsf{BI}_{b,\varepsilon}(z)$ has at least $m-(1+4\theta)\frac{m^{2}}{n}$ distinct elements.

Proof.

Let $q=2^{\lceil\log n\rceil}$ , and set $\gamma=\varepsilon\cdot 2^{-\frac{b\log q}{2}}$ and $n_{\mathsf{b}}=n\log q$ . Let $S_{\mathsf{b}}\subseteq\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n_{\mathsf{b}}}$ denote the $\gamma$ -biased set that is guaranteed to us by Corollary 3.3 and let $S\subseteq[q]^{n}$ be the set that corresponds to treating each consecutive $\log q$ bits as an element of $[q]$ .¹²¹²12Since we won’t care about optimizing the dependence on $n$ , we do not pre-encode using a bounded-independence generator (as in, say, [NN90, AGHP92]). By the XOR lemma, $S$ is $(b,\varepsilon)$ -biased over $[q]^{n}$ . Moreover, $\log|S|=O(\log(1/\varepsilon)+k\log q+\log n)=O(\log(1/\varepsilon)+b\log n)$ , and each element of $S$ can be generated in time

\mathopen{}\mathclose{{}\left(n_{\mathsf{b}}+\log(1/\gamma)}\right)\cdot\widetilde{O}(\log n_{\mathsf{b}})=\widetilde{O}(n)+\mathopen{}\mathclose{{}\left(b+\log(1/\varepsilon)}\right)\cdot\widetilde{O}(\log n)=\widetilde{O}(n),

where the last equality follows since we can always assume that $\varepsilon\geq m^{-n}$ . Notice that ignoring the last $n-m$ symbols of each element of $S$ still preserves the above properties, which indeed gives rise to an efficiently samplable $(b,\varepsilon)$ -wise independent sample space over $[q]^{m}$ .

Next, we argue that most samples contain mostly distinct elements. Towards this end, let $X_{1},\ldots,X_{m}$ be our $(b,\varepsilon)$ -wise independent distribution $\mathsf{BI}_{b,\varepsilon}(U_{d})$ , and let $Z_{i}$ denote the indicator random variable that is $1$ if and only if $X_{i}$ is a duplicate element (namely, there exists $j<i$ such that $X_{i}=X_{j}$ ). We are looking to bound $\sum_{i\in[m]}Z_{i}$ with high probability.

Claim 3.6.

Assume that $t\leq b/2$ and $\varepsilon\leq\theta q^{-t}$ for some $\theta>0$ . Then, for any distinct $i_{1},\ldots,i_{t}\in[m]$ , it holds that $\Pr[Z_{i_{1}}=\ldots=Z_{i_{t}}=1]\leq(1+\theta)(m/q)^{t}$ .

Proof.

Fix indices $j_{1},\ldots,j_{t}$ , where each $j_{\ell}<i_{\ell}$ . The probability that $X_{i_{\ell}}=X_{j_{\ell}}$ for all $\ell\in[t]$ is at most $q^{-t}+\varepsilon\leq(1+\theta)q^{-t}$ , since this event depends on at most $2t\leq b$ random variables. Union-bounding over all choices of $j$ -s incurs a multiplicative factor of $\prod_{\ell\in[t]}(i_{\ell}-1)\leq m^{t},$ so overall, $\Pr[Z_{i_{1}}=\ldots=Z_{i_{t}}=1]\leq(1+\theta)(m/q)^{t}$ . ∎

Now, 3.6 is sufficient to give us good tail bounds (see, e.g., [HH15, Section 3]). In particular, denoting $\mu=(1+\theta)\frac{m}{q}$ there exists a universal constant $c>0$ such that

\Pr\mathopen{}\mathclose{{}\left[\sum_{i\in[m]}Z_{i}\geq(1+\theta)\mu m}\right]\leq 2^{-c\theta b},

which implies Item 2 when $n=q$ . Finally, we need to argue that we can also handle the case where $n$ is not a power of $2$ (and so $q>n$ ). In this case, we can take our $\gamma$ -biased set to be over $n_{\mathsf{b}}=\lceil\varepsilon^{-1}\log n\rceil n$ bits, and each consecutive $\lceil\varepsilon^{-1}\log n\rceil$ bits are mapped to $[n]$ by simply taking the corresponding integer modulo $n$ . The correctness can be found, e.g., in [Rao07]. ∎

Towards introducing our sampler, we will need the following tail bound for $(b,\varepsilon)$ -wise independent random variables.

Lemma 3.7 ([XZ24]).

Let $X\sim\Sigma^{m}$ be a $(b,\gamma)$ -wise independent distribution, and fix some $\varepsilon>0$ . Then, $X$ is also a $(\delta,\varepsilon)$ sampling distribution, where

\delta=\mathopen{}\mathclose{{}\left(\frac{5\sqrt{b}}{\varepsilon\sqrt{m}}}\right)^{b}+\frac{\gamma}{\varepsilon^{b}}.

While the error in Item 2 above is small, it is not small enough for us to simply combine Lemmas 3.7 and 3.5, and we will need to do a mild error reduction. We do this via random walks on expanders and discarding repeating symbols, as was also done in [Vad04]. This gives us the following bounded-independence based sampler.

Lemma 3.8.

For any positive integers $m\leq n$ , any $\delta_{\Gamma}\in(0,1)$ , and any constant $\eta\in(0,1)$ such that $m\leq\frac{\eta}{8}n$ , there exists an explicit $(\delta_{\Gamma},\varepsilon_{\Gamma}=2\eta)$ sampler $\Gamma\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\rightarrow[n]^{m}$ with $d=O\mathopen{}\mathclose{{}\left(\frac{\log n}{\log m}\cdot\log\frac{1}{\delta_{\Gamma}}}\right)$ , that satisfies the following additional properties.

1.

Every output of $\Gamma$ contains distinct symbols of $[n]$ , and,
2.

Given $y\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}$ , $\Gamma(y)$ is computable in time $\widetilde{O}(n+\log^{2}\frac{1}{\delta_{\Gamma}}\cdot\frac{\log n}{\log m})$ .

Proof.

Set $b$ to be the smallest integer such that $b\log\frac{\eta\sqrt{m}}{5\sqrt{b}}\geq\log\frac{8}{\delta_{\Gamma}}$ , set $m^{\prime}=(1+\eta)m$ , $\theta=\eta/4$ , and $\gamma=\min\mathopen{}\mathclose{{}\left\{{\frac{1}{8}\eta^{b}\cdot\delta_{\Gamma},\theta\cdot n^{-b/2}}}\right\}$ . Notice that $b=O\mathopen{}\mathclose{{}\left(\frac{\log(1/\delta_{\Gamma})}{\log m}}\right)$ and $\log\frac{1}{\gamma}=O\mathopen{}\mathclose{{}\left(\frac{\log n}{\log m}\cdot\log\frac{1}{\delta_{\Gamma}}}\right)$ . Let

\mathsf{BI}_{b,\gamma}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d^{\prime}}\rightarrow[n]^{m^{\prime}}

be the $(b,\gamma)$ -wise independent generator guaranteed to us by Lemma 3.5, with $d^{\prime}=O(b\log n+\log(1/\gamma))=O(\log(1/\gamma))$ . By Lemma 3.7, $X=\mathsf{BI}_{b,\varepsilon}(U_{d^{\prime}})$ is a $(\delta_{\mathsf{b}},\eta)$ sampling distribution, where

\delta_{\mathsf{b}}=\mathopen{}\mathclose{{}\left(\frac{5\sqrt{b}}{\eta\sqrt{m^{\prime}}}}\right)^{b}+\frac{\gamma}{\eta^{b}}\leq\frac{\delta_{\Gamma}}{8}+\frac{\delta_{\Gamma}}{8}\leq\frac{\delta_{\Gamma}}{4}.

Also, we know from Lemma 3.5 that with probability at least $1-2^{-\Omega(\theta b)}\triangleq 1-p$ , each sample from $X$ has at least $m^{\prime}-(1+4\theta)\frac{m^{\prime 2}}{n}\geq m$ distinct symbols, using the fact that $\frac{n}{m}\geq\frac{(1+\eta)^{3}}{\eta}$ . Conditioned on seeing at least $m$ distinct symbols, $X$ as a sampling distribution, when we remove the non-distinct elements, has confidence $\frac{\delta_{\Gamma}/4}{1-p}\leq\frac{\delta_{\Gamma}}{2}$ and accuracy $2\eta$ (where the second $\eta$ comes from the fact that $\eta m$ symbols were removed).

Next, in order to improve the probability of sampling a good sequence, let $G=(V=\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d^{\prime}},E)$ be the $D$ -regular $\lambda$ -spectral expander of Corollary 2.18, instantiated with $\lambda=p$ , so $D\leq p^{-c}$ for some universal constant $c$ . Write $d=d^{\prime}+\ell^{\prime}$ for $\ell^{\prime}=\ell\cdot\log D$ , where $\ell=c_{\ell}\cdot\frac{\log(1/\delta_{\Gamma})}{b}$ for some constant $c_{\ell}$ soon to be determined. Given $y=(z,w)\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d^{\prime}}\times[D]^{\ell}$ , let $z=v_{0},v_{2},\ldots,v_{\ell}$ denote the corresponding random walk over $G$ . Our sampler $\Gamma$ , on input $y$ , computes $\mathsf{BI}_{b,\gamma}(v_{i})$ and outputs the first sequence with at least $m$ distinct symbols. If no such sequence was found, $\Gamma$ simply outputs $(1,\ldots,m)$ (in which case we say it failed). By the expander hitting property (see, e.g., [Vad12, Section 4]), $\Gamma$ fails with probability at most

(p+\lambda)^{\ell}=(2p)^{\ell}\leq\frac{\delta_{\Gamma}}{2}

over $y\sim U_{d}$ , upon choosing the appropriate constant $c_{\ell}=c_{\ell}(\eta)$ . We then have that $\Gamma(U_{d})$ is indeed a $(\delta_{\Gamma},2\eta)$ sampling distribution, that can be generated using a seed of length $d^{\prime}+\ell^{\prime}=O(\log(1/\gamma))$ . In terms of runtime, computing $v_{1},\ldots,v_{\ell}$ can be done in time

\ell\cdot\log\frac{1}{p}\cdot\widetilde{O}(d^{\prime})=\widetilde{O}\mathopen{}\mathclose{{}\left(\log^{2}\frac{1}{\delta_{\Gamma}}\cdot\frac{\log n}{\log m}}\right),

and computing the sequences themselves takes $\ell\cdot\widetilde{O}(n)$ time. Observing that $\ell=O(\log m)$ , the proof is concluded. ∎

We will need to somewhat extend Lemma 3.8 and use the simple, yet crucial, property of our bounded independence sampling: A subset of the coordinates of a $(b,\varepsilon)$ -wise independent distribution with distinct samples is itself a $(b,\varepsilon)$ -wise independent distribution with distinct samples.¹³¹³13We note that the distinct-samples sampler given in [Vad04] does not seem to enjoy a similar property. Thus, if we wish to sample multiple times, say using $m_{1}\leq\ldots\leq m_{t}<n$ samples, we can use one sample from a sampler that outputs $m_{t}$ coordinates, and truncate accordingly to create the other samples. We only need to note that: (1) the sampling parameters are determined by the different $m_{i}$ -s (and in particular, $m_{1}$ should be large enough), and (2) $m_{t}$ needs to be small enough compared to $n$ , so that we can get enough distinct symbols. We summarize this observation in the next lemma.

Lemma 3.9.

For any positive integers $n$ and $m_{1}<\ldots<m_{t}\leq n$ , any $\delta\in(0,1)$ and any constant $\varepsilon$ such that $m_{t}\leq\frac{\varepsilon}{16}n$ , there exists an explicit function $\Gamma\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\rightarrow[n]^{m_{t}}$ with $d=O\mathopen{}\mathclose{{}\left(\frac{\log n}{\log m_{1}}\cdot\log\frac{1}{\delta_{\Gamma}}}\right)$ that satisfies the following.

1.

For any $i\in[t]$ , the function $\Gamma_{i}$ , that on input $y\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}$ outputs $\Gamma(y)|_{[1,m_{i}]}$ , is a $(\delta,\varepsilon)$ sampler, and each sample contains distinct symbols.
2.

On input $y\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}$ , $\Gamma(y)$ can be computed in time $\widetilde{O}(n+\log^{2}(1/\delta))$ .

3.3 Nearly-Linear Time Condensers

We first give the condenser based on multiplicity codes, due to Kalev and Ta-Shma [KT22].

Theorem 3.10 (the lossless KT condenser, [KT22]).

For any constant $\alpha\in(0,1)$ the following holds, for every $n\in\mathbb{N}$ , and any $0<\varepsilon\leq\frac{1}{n}$ and $k\geq\frac{256}{\alpha^{2}}\log^{2}\frac{n}{\varepsilon}$ . There exists an explicit strong $(k,k^{\prime}=k+\ell,\varepsilon)$ -condenser

\mathsf{KTCond}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{\ell}\rightarrow\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m}

where $\ell=\mathopen{}\mathclose{{}\left(1+\frac{1}{\alpha}}\right)\log\frac{nk}{\varepsilon}=O_{\alpha}(\log\frac{1}{\varepsilon})$ and $m=(1+\alpha)k$ . Note that the output entropy rate satisfies $\frac{k^{\prime}}{m}\geq 1-\alpha$ . Moreover, given $x\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}$ and $y\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{\ell}$ , the output $\mathsf{KTCond}(x,y)$ can be computed in $\widetilde{O}(n)$ time.

In particular, if $\varepsilon^{\prime}=\sqrt{\varepsilon}$ , then for all $(n,k)$ -sources $X$ and a $(1-\varepsilon^{\prime})$ -fraction of seeds $y$ it holds that $\mathsf{KTCond}(X,y)\approx_{\varepsilon^{\prime}}Z_{y}$ , where $Z_{y}$ is an $(m=(1+\alpha)k,k^{\prime}-\ell=k\geq(1-\alpha)m)$ -source. Note that the seed length is $\ell=O_{\alpha}(\log\frac{1}{\varepsilon^{\prime}})$ .

Proof.

For the first part of the theorem statement we only need to establish the construction’s runtime. Given $x\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}$ and $y\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{\ell}$ , set a prime $p=\operatorname{poly}_{\alpha}(\frac{n}{\varepsilon})$ ,¹⁴¹⁴14More precisely, they set $h=(2nk/\varepsilon)^{1/\alpha}$ , and take $p$ to be a prime between $\frac{1}{2}h^{1+\alpha}$ and $h^{1+\alpha}$ . and interpret $x$ as a polynomial $f_{x}\in\mathds{F}_{q}[X]$ of degree at most $d-1$ , and $y$ as an element of $\mathds{F}_{p}$ . Thus, $n=d\log q$ , and we can safely ignore rounding issues, which can easily be addressed. The output $\mathsf{KTCond}(x,y)$ is the sequence of derivatives

\mathopen{}\mathclose{{}\left(f(y),f^{\prime}(y),\ldots,f^{(m^{\prime})}(y)}\right),

where $m^{\prime}=\frac{m}{\log q}$ . By Lemma 2.1, computing the derivatives takes $\widetilde{O}(d)\cdot\log p=\widetilde{O}(n)$ time. The rest of the auxiliary operations are negligible compared to computing the derivatives.

To see the “In particular” part of the theorem statement, fix an $(n,k)$ -source $X$ and note that $Y\circ\mathsf{KTCond}(X,Y)\approx_{\varepsilon}Y\circ Z$ for some $Z$ such that $\mathbf{H}_{\infty}(Y\circ Z)\geq k^{\prime}$ . Let $Z_{y}=(Z|Y=y)$ . Then, an averaging argument gives that for a $(1-\sqrt{\varepsilon})$ -fraction of seeds $y$ we have $\mathsf{RSCond}(X,y)\approx_{\sqrt{\varepsilon}}Z_{y}$ . Since $Y$ is uniformly random over $\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{\ell}$ , we get that $\mathbf{H}_{\infty}(Z_{y})\geq k^{\prime}-\ell$ , as desired. ∎

The downside of Theorem 3.10 is that it requires the entropy in the source to be $\Omega(\log^{2}(1/\varepsilon))$ , instead of the optimal $\Omega(\log(1/\varepsilon))$ . Instead, we can use a lossy condenser¹⁵¹⁵15Our extractor will lose a small constant fraction of the entropy, so losing a small constant fraction of the entropy in the condensing step will not make much difference. based on Reed–Solomon codes. Unfortunately, this comes at the expense of computing a generator of a field of size $\operatorname{poly}(1/\varepsilon)$ , which we do not know how to do in nearly-linear time for arbitrary $\varepsilon$ -s. We consider it a one-time preprocessing step, as it does not depend on the inputs to the condenser.

Theorem 3.11 (the lossy RS condenser, [GUV09]).

For any constant $\alpha\in(0,1)$ the following holds, for every $n\in\mathbb{N}$ , and any $0<\varepsilon\leq\frac{1}{n}$ and $k\geq(2+\alpha)\log(1/\varepsilon)$ . There exists an explicit strong $(k,k^{\prime},\varepsilon)$ -condenser

\mathsf{RSCond}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{\ell}\rightarrow\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m}

where $\ell=\mathopen{}\mathclose{{}\left(1+\frac{1}{\alpha}}\right)\log\frac{nk}{\varepsilon}=O_{\alpha}(\log\frac{1}{\varepsilon})$ , $m=k$ , and $k^{\prime}=\frac{k-\log(1/\varepsilon)}{1+\alpha}+\ell\geq(1-\alpha)k$ . Note that the output entropy rate satisfies $\frac{k^{\prime}}{m}\geq 1-2\alpha$ . Moreover, given $x\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}$ , $y\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{\ell}$ , and a primitive element for $\mathds{F}_{2^{\ell}}$ , the output $\mathsf{RSCond}(x,y)$ can be computed in time $\widetilde{O}(n)$ .

In particular, if $\varepsilon^{\prime}=\sqrt{\varepsilon}$ and $k\geq\frac{\log(1/\varepsilon)}{\alpha(1+2\alpha)}$ , then for all $(n,k)$ -sources $X$ and a $(1-\varepsilon^{\prime})$ -fraction of seeds $y$ it holds that $\mathsf{RSCond}(X,y)\approx_{\varepsilon^{\prime}}Z_{y}$ , where $Z_{y}$ is an $(m=k,k^{\prime}-\ell\geq(1-2\alpha)m)$ -source. Note that the seed length is $\ell=O_{\alpha}(\log\frac{1}{\varepsilon^{\prime}})$ .

Proof.

We set $q=2^{\ell}$ , and let $\zeta\in\mathds{F}_{q}$ be the generator of the multiplicative group $\mathds{F}_{q}^{\star}$ given to us as input.¹⁶¹⁶16Working with fields of characteristic $2$ is not necessary, but may help in efficiently computing $\zeta$ . For example, Shoup [Sho90] showed that given an irreducible polynomial $f\in\mathds{F}_{2}[X]$ of degree at most $d-1$ , there exists a primitive element $h\in\mathds{F}_{2}[X]/\langle f\rangle$ of $\mathds{F}_{2}[X]/\langle f\rangle\equiv\mathds{F}_{2^{d}}$ such that $h$ is a monic polynomial of degree $O(\log d)$ . Given $x\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}$ and $y\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{\ell}$ , similarly to Theorem 3.10, interpret $x$ as a univariate polynomial $f_{x}$ of degree at most $d-1$ , and $y$ as an element of $\mathds{F}_{q}$ . The output $\mathsf{Cond}(x,y)$ is the sequence of evaluations

\mathopen{}\mathclose{{}\left(f(y),f(\zeta y),\ldots,f(\zeta^{m^{\prime}}y)}\right),

where $m^{\prime}=\frac{m}{\log q}$ .

The correctness proof, as well as the exact choice of parameters, are given in [GUV09, Section 6], so we proceed to bounding the runtime. Towards that end, since we rely on a specific primitive element $\zeta$ , we assume that the irreducible polynomial used to construct $\mathds{F}_{q}$ is known, either (and there are several ). Computing the evaluation points $y,\zeta y,\ldots,\zeta^{m^{\prime}}y$ can then be done naively in time $m^{\prime}\cdot M_{q}^{\mathsf{b}}(\ell)=\widetilde{O}(n)$ . Then, using Lemma 2.1, the evaluation can be done in time $\widetilde{O}(d)\cdot\log q=\widetilde{O}(n)$ as well.

The “In particular” part of the theorem statement follows analogously to that of Theorem 3.10, using also the fact that if $k\geq\frac{\log(1/\varepsilon)}{\alpha(1+2\alpha)}$ , then $k^{\prime}-\ell=\frac{k-\log(1/\varepsilon)}{1+\alpha}\geq(1-2\alpha)k=(1-2\alpha)m$ . ∎

4 A Faster Instantiation of Trevisan’s Extractor

We first recall Trevisan’s extractor [Tre01, RRV02], $\mathsf{Tre}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\rightarrow\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m}$ , set to some designated error $\varepsilon>0$ . We will need the notion of weak designs, due to Raz, Reingold, and Vadhan [RRV02].

Definition 4.1 (weak design).

A collection of sets $S_{1},\dots,S_{m}\subseteq[d]$ is an $(\ell,\rho)$ -weak design if for all $i\in[m]$ we have $|S_{i}|=\ell$ and

\sum_{j<i}2^{|S_{i}\cap S_{j}|}\leq\rho(m-1).

We will also need a $\delta$ -balanced code $\mathcal{C}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\rightarrow\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{\bar{n}}$ . The parameters of the weak design affect the extractor’s parameters and can be set in a couple of different ways. The parameter $\ell$ is set to be $\log\bar{n}$ , typically $\rho$ is chosen according to $m$ , $\varepsilon$ , and the desired entropy $k$ , and then $d$ is chosen as a function of $\ell$ , $m$ , and $\rho$ according to the weak design (see [RRV02]). Given $x\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}$ and $y\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}$ , Trevisan’s extractor outputs

\mathsf{Tre}(x,y)=\bar{x}|_{y_{S_{1}}}\circ\ldots\circ\bar{x}|_{y_{S_{m}}},

(1)

where we denote $\bar{x}=\mathcal{C}(x)$ and interpret each length- $\log\bar{n}$ bit-string $y_{S_{i}}$ as a location in $[\bar{n}]$ . For the runtime analysis, it will be important to recall that $\delta$ is set to be $\frac{\varepsilon}{cm}$ for some universal constant $c$ .

Theorem 4.2.

Trevisan’s extractor of Equation 1, set to extract $m$ bits with any error $\varepsilon>0$ , is computable in time $\widetilde{O}(n+m\log(1/\varepsilon))$ .

On a RAM in the logarithmic cost model, Trevisan’s extractor is computable in time $O(n)+m\log(1/\varepsilon)\cdot\operatorname{polylog}(n)$ with a preprocessing time of $\widetilde{O}(m\log(n/\varepsilon))$ . In particular, there exists a universal constant $c$ , such that whenever $m\leq\frac{n}{\log^{c}(n/\varepsilon)}$ , it runs in time $O(n)$ , without the need for a separate preprocessing step.

Proof.

Looking at Equation 1, note that we only need to compute $m$ coordinates of $\mathcal{C}(x)$ . To compute those $m$ coordinates, $y_{S_{1}},\ldots,y_{S_{m}}$ , we first need to compute the weak design itself. Note that this can be seen as a preprocessing step, since it only depends on the parameters of the extractor, and not on $x$ or $y$ . We will use the following result.

Claim 4.3 ([FYEC24], Section A.5).

For every $\ell,m\in\mathbb{N}$ and $\rho>1$ , there exists an $(\ell,\rho)$ -weak design $S_{1},\ldots,S_{m}\subseteq[d]$ with $d=O(\frac{\ell^{2}}{\log\rho})$ , computable in time $\widetilde{O}(m\ell)$ .

Once we have our preprocessing step, we are left with computing the code. By Corollary 3.3, we can choose $\bar{n}$ so that $n/\bar{n}=\delta^{c}$ for some universal constant $c$ , and so $\bar{n}=n\cdot\operatorname{poly}(m,1/\varepsilon)$ and $\ell=\log\bar{n}=O(\log(n/\varepsilon))$ . Generating the design can then be done in time $\widetilde{O}(m\log(n/\varepsilon))$ . Now, Corollary 3.3 tells us that any $m$ bits of $\mathcal{C}(x)$ can be computed in time

\widetilde{O}(n)+O(m\log(1/\delta)\log n\operatorname{loglog}n)=\widetilde{O}(n+m\log(1/\varepsilon)).

On a RAM in the logarithmic cost model, we can use the variant of $\mathcal{C}$ that uses Spielman’s code as a base code (see Remark 3.4) and get a runtime of $O(n)+m\log(1/\varepsilon)\cdot\operatorname{polylog}(n)$ . This gives a truly linear time construction whenever $m$ is at most $\frac{n}{\log(1/\varepsilon)\operatorname{polylog}(n)}$ . ∎

We conclude by noting that there is a natural setting of parameters under which Trevisan’s extractor gives logarithmic seed and linear (or near-linear) time. When $m=k^{\Omega(1)}$ , the parameters can be set so that $d=O\mathopen{}\mathclose{{}\left(\frac{\log^{2}(n/\varepsilon)}{\log k}}\right)$ . We thus have the following corollary.

Corollary 4.4.

For every $n\in\mathbb{N}$ , any constant $c>1$ , and any constants $\alpha,\beta\in(0,1)$ , Trevisan’s extractor $\mathsf{Tre}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\rightarrow\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m}$ can be instantiated as a $(k=n^{\alpha},\varepsilon=n^{-c})$ extractor with $d=O(\log n)$ , $m=k^{\beta}$ , and given $x\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}$ and $y\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}$ , $\mathsf{Tre}(x,y)$ is computable in time $\widetilde{O}(n)$ (or $O(n)$ time, depending on the model).

5 Nearly-Linear Time Extractors with Order-Optimal Seed Length

5.1 A Non-Recursive Construction

In this section, we use the various previously introduced building blocks to construct a seeded extractor with order-optimal seed length $O(\log(n/\varepsilon))$ computable in time $\widetilde{O}(n)$ . In a nutshell, our extractor proceeds as follows on input an $(n,k)$ -source $X$ :

1.

Using a fresh seed, apply the lossless KT condenser from Theorem 3.10 to $X$ . This yields an $(n^{\prime},k)$ -source $X^{\prime}$ of length $n^{\prime}\approx k$ and constant entropy rate $\delta$ which can be arbitrarily close to $1$ .
2.

Using the fact that $X^{\prime}$ has high min-entropy rate, use the bounded-independence sampler from Lemma 3.9 to sample subsources from $X^{\prime}$ using a fresh seed. Specific properties of the bounded-independence sampler allow us to obtain a block source $Z=Z_{1}\circ Z_{2}\circ\cdots\circ Z_{t}$ with a seed of length only $O(\log(1/\varepsilon))$ . The number of blocks is $t=O(\log n)$ and the blocks $Z_{i}$ have geometrically increasing lengths, up to an $n^{\alpha}$ length threshold.
3.

Now, to prepare for the hash-based iterative extraction, we need to make our blocks decreasing. Again, using a short seed, of length $O(\log(n/\varepsilon))$ , we transform $Z$ into $S=S_{1}\circ\cdots S_{t}$ , where the blocks are now geometrically decreasing. The blocks lengths will vary from $n^{\beta_{1}}$ to some $n^{\beta_{2}}$ , for some constants $\beta_{1}>\beta_{2}$ .
4.

Using a fresh seed, apply the fast hash-based extractor from Lemma 2.14 to perform block source extraction from $S$ . Noting that the first block has length $n^{\Omega(1)}$ , the block source extraction only outputs $n^{\Omega(1)}$ bits. We are able to use only $O(\log(n/\varepsilon))$ random bits here, since we do not output $n^{\Omega(1)}$ bits already at the beginning of the iterative extraction process, but instead output logarithmically many bits, and gradually increasing the output length.

These steps will culminate in the following theorem.

Theorem 5.1 (non-recursive construction).

There exists a constant $c\in(0,1)$ such that for every positive integers $n$ and $k\leq n$ , any $\varepsilon\geq 2^{-k^{c}}$ , and any constant $\eta\in(0,1)$ , there exists a strong $(k,\varepsilon)$ extractor

\mathsf{Ext}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\rightarrow\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m},

where $d=O(\log(n/\varepsilon))$ , and $m=(1-\eta)k$ . Moreover, given inputs $x\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}$ and $y\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}$ , we can compute $\mathsf{Ext}(x,y)$ in time $\widetilde{O}(n)$ .

5.1.1 Item 2: Generating the block source

Because of the initial condensing step, we will assume from here onwards that our input source $X$ is an $(n,k=\delta n)$ -source with constant $\delta$ . In order to generate the desired block source, we first use a fresh seed $Y$ as input to an appropriate instantiation of the bounded-independence sampler $\Gamma$ from Lemma 3.9. This yields a tuple of coordinates $\Gamma(Y)=j_{1},\dots,j_{m_{t}}$ from $[n]$ , such that $\Gamma(Y)|_{[1,m_{i}]}$ is an appropriate averaging sampler for every $i$ . Then, we use these coordinates to sample subsources from $X\sim\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}$ , and get a block source with increasing blocks.

Lemma 5.2 (sampling a block source).

There exists a deterministic procedure that given an $(n,k)$ -source $X$ with $k\geq\delta n$ , $\delta$ being constant, and:

•

A constant loss parameter $\zeta\in(0,1)$ ,
•

A closeness parameter $\varepsilon\in(0,1)$ that satisfies $\varepsilon\geq 2^{-c_{\varepsilon}n}$ where $c_{\varepsilon}=c_{\varepsilon}(\zeta,\delta)$ is constant,
•

Number of desired blocks $t\in\mathbb{N}$ ,
•

A final, maximal, block length $\Delta_{t}\leq c_{\mathsf{t}}\cdot n$ where $c_{\mathsf{t}}=c_{\mathsf{t}}(\zeta,\delta)$ is constant, and,

takes an independent and uniform random seed $Y\sim\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d_{\mathsf{samp}}}$ and outputs a random variable $Z$ that is $\varepsilon$ -close to a

\mathopen{}\mathclose{{}\left((\Delta_{1},\ldots,\Delta_{t}),(1-\zeta)\delta}\right)

block-source, where each $\Delta_{i-1}=\alpha\cdot\Delta_{i}$ for $\alpha=\frac{\zeta\delta}{4}$ . Moreover, the seed length $d=O\mathopen{}\mathclose{{}\left(\frac{\log n}{\log\Delta_{1}}\cdot\log\frac{t}{\varepsilon}}\right)$ , and the procedure runs in time $\widetilde{O}(n+\log^{2}(t/\varepsilon))$ .

Note that for any constants $0<\theta_{1}<\theta_{2}<1$ , and any $\varepsilon=\Omega(2^{-\sqrt{n}})$ , we can have $\Delta_{t}=n^{\theta_{2}}$ and $\Delta_{1}=n^{\theta_{1}}$ for some $t=O(\log n)$ , with seed length $O(\log(1/\varepsilon))$ and runtime $\widetilde{O}(n)$ .

Proof.

Given our $\Delta_{1},\ldots,\Delta_{t}$ , we let $m_{i}=\sum_{j=1}^{i}\Delta_{j}$ for $j\in[t]$ . Note that for $i\in[t-1]$ , each $m_{i}=\sum_{j=1}^{i}\Delta_{j}\leq\frac{\alpha}{1-\alpha}\Delta_{i+1}$ , so in particular

m_{t}=m_{t-1}+\Delta_{t}\leq\frac{\alpha}{1-\alpha}\Delta_{t}+\Delta_{t}\leq n,

by choosing the constant $c_{\mathsf{t}}$ appropriately. Let $\Gamma\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d_{\mathsf{samp}}}\rightarrow[n]^{m_{t}}$ be the $(\gamma,\varepsilon_{\Gamma})$ sampler of Lemma 3.9, set with $\varepsilon_{\Gamma}=\frac{1}{\log(\frac{6}{\zeta\delta})}\cdot\frac{\zeta\delta}{6}=O(1)$ and $\gamma=\frac{\varepsilon}{2t}$ . Note that then,

d_{\mathsf{samp}}=O\mathopen{}\mathclose{{}\left(\frac{\log n}{\log m_{1}}\cdot\log\frac{1}{\gamma}}\right)=O\mathopen{}\mathclose{{}\left(\frac{\log n}{\log\Delta_{1}}\cdot\log\frac{t}{\varepsilon}}\right),

and indeed $m_{t}\leq\frac{\varepsilon_{\Gamma}}{16}\cdot n$ can be met by, again, setting the constant $c_{\mathsf{t}}$ appropriately. Moreover, we have that for any $i\in[t]$ ,

W_{i}=\Gamma(Y)|_{[1,m_{i}]}

is a $(\gamma,\varepsilon_{\Gamma})$ sampler, where $w\sim W_{i}$ has distinct symbols. Set $\beta=\frac{\zeta}{2}$ .

Now, Lemma 2.16, instantiated with $\tau=\frac{\beta\delta}{3}$ (notice that indeed $\varepsilon_{\Gamma}\leq\frac{\tau}{\log(1/\tau)}$ ), tells us that for every $i\in[t]$ , denoting $A_{i}=X_{W_{i}}$ , there exists a set $\mathbf{B}_{i}\subseteq\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d_{\mathsf{samp}}}$ of bad $y$ -s of density at most $\gamma+2^{-\Omega(\tau n)}$ , such that for any $y\notin\mathbf{B}_{i}$ ,

A_{i}|\mathopen{}\mathclose{{}\left\{{Y=y}}\right\}\sim\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m_{i}}

has entropy rate $\delta-3\tau\geq(1-\beta)\delta$ for every $y$ . Letting $Z=A_{t}$ , union-bounding over the bad $y$ -s tells us that $Z$ is $t\cdot(\gamma+2^{-\Omega(n)})\leq\varepsilon$ close to some $Z^{\prime}\sim\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m_{t}}$ such that for any $i\in[t]$ , $Z^{\prime}_{i}=Z^{\prime}_{[1,m_{i}]}\sim\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m_{i}}$ has entropy rate $(1-\beta)\delta$ .

Next, we apply the chain rule for min-entropy to argue that $Z^{\prime}$ (and hence $Z$ ) is close to a block source. To do that, we apply the chain rule for min-entropy $t-1$ times. For simplicity, abbreviate $Z^{(i)}=Z^{\prime}_{[m_{i-1}+1,m_{i}]}$ (so note that $Z^{\prime}_{i}$ is the longer block, $Z^{\prime}_{[1,m_{i}]}$ , whereas $Z^{(i)}$ is its length- $\Delta_{i}$ suffix), so

Z^{\prime}=\mathopen{}\mathclose{{}\left(Z^{(1)},Z^{(2)},\ldots,Z^{(t)}}\right).

We will argue that $Z^{\prime}$ is a block source. Applying Lemma 2.5, we know that for any $i\in[t]$ ,

\widetilde{\mathbf{H}}_{\infty}\mathopen{}\mathclose{{}\left(Z^{(i)}\mid Z^{(1)},\ldots,Z^{(i-1)}}\right)\geq\mathbf{H}_{\infty}(Z^{(i)})-\sum_{j=1}^{i-1}\Delta_{j}=\mathbf{H}_{\infty}(Z^{(i)})-m_{i-1}\geq\mathbf{H}_{\infty}(Z^{(i)})-\frac{\alpha}{1-\alpha}\Delta_{i}.

Now, $Z^{\prime}_{i}=(Z^{\prime}_{i-1},Z^{(i)})$ , so $\mathbf{H}_{\infty}(Z^{(i)})\geq\mathbf{H}_{\infty}(Z^{\prime}_{i})-m_{i-1}$ , and notice that

(1-\beta)\delta\cdot\Delta_{i}-m_{i-1}\geq(1-\beta)\delta\cdot\Delta_{i}-\frac{\alpha}{1-\alpha}\Delta_{i}\geq(1-\zeta)\delta\cdot\Delta_{i},

where we used the fact that $\alpha\leq\frac{(\zeta-\beta)\delta}{1-(\zeta-\beta)\delta}$ .

The bound on the runtime follows easily, recalling that $\Gamma$ runs in time $\widetilde{O}\mathopen{}\mathclose{{}\left(n+\log^{2}(1/\gamma)}\right)$ . ∎

5.1.2 Item 3: Subsampling from the block source

To apply iterative extraction, we will our block source to have decreasing blocks. Here, we will use a sampler to sample from each block, using the same seed accross the blocks.

Lemma 5.3 (subsampling from a block source).

There exists a deterministic procedure that given a

\mathopen{}\mathclose{{}\left((\Delta_{1},\ldots,\Delta_{t}),\delta}\right)

block-source $Z=(Z_{1},\ldots,Z_{t})$ , for every $\Delta_{1}\leq\ldots\leq\Delta_{t}$ and a constant $\delta$ , and:

•

A constant shrinkage parameter $\alpha\in(0,1)$ ,
•

A constant loss parameter $\zeta\in(0,1)$ ,
•

A closeness parameter $\varepsilon\in(0,1)$ ,
•

An initial, maximal, block length $\ell_{1}\leq\Delta_{1}$ , and,

takes an independent and uniform random seed $Y\sim\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d_{\mathsf{samp}}}$ and outputs a random variable $S$ that is $\varepsilon$ -close to a $\mathopen{}\mathclose{{}\left((\ell_{1},\ldots,\ell_{t}),(1-\zeta)\delta}\right)$ block-source, where each $\ell_{i+1}=\alpha\cdot\ell_{i}$ , and assuming that $\ell_{t}\geq c_{1}\log(t/\varepsilon)$ where $c_{1}=c_{1}(\zeta,\delta)$ is a constant. Moreover, the seed length $d=\log\frac{\Delta_{t}}{\ell_{1}}+O\mathopen{}\mathclose{{}\left(t+\log\frac{1}{\varepsilon}}\right)$ , and the procedure runs in time $\operatorname{polylog}(\Delta_{t})\cdot\ell_{1}$ .

Note that when $\Delta_{1}=n^{\theta_{1}}$ and $\ell_{t}=n^{\beta}$ for some constants $0<\beta<\theta_{1}<2$ , $d_{\mathsf{samp}}=O(\log(n/\varepsilon))$ , the procedure runs in time $O(n)$ , and we can take any $\varepsilon\geq 2^{-c\cdot\ell_{t}}$ for some constant $c$ that depends on $\zeta$ and $\delta$ .

Proof.

For $i\in[t]$ , let $m_{i}=\sum_{j=1}^{i}\ell_{i}$ , recalling that $\ell_{i}=\alpha^{i-1}\ell_{1}$ . For each $i\in[t]$ , let $\Gamma_{i}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d_{i}}\rightarrow[\Delta_{i}]^{\ell_{i}}$ be the $(\gamma,\varepsilon_{\Gamma})$ be the distinct-samplers sampler of Lemma 2.21, where $\gamma=\frac{\varepsilon}{2t}$ and $\varepsilon_{\Gamma}=\frac{1}{\log(\frac{6}{\zeta\delta})}\cdot\frac{\zeta\delta}{6}=O(1)$ . We need to make sure that each $\ell_{i}\geq c\cdot\frac{\log(1/\gamma)}{\varepsilon^{2}_{\Gamma}}$ for some universal constant $c$ , and indeed that is the case, by our constraint on $\ell_{t}$ . Also, $d_{i}=\log(\Delta_{i}/\ell_{i})+O(\log\frac{1}{\gamma}\cdot\operatorname{poly}(1/\varepsilon_{\Gamma}))$ and we set $d_{\mathsf{samp}}$ to be the maximal over the $d_{i}$ -s, so

d_{\mathsf{samp}}=d_{t}=\log\frac{\Delta_{t}}{\ell_{1}}+t\cdot\log\frac{1}{\alpha}+O\mathopen{}\mathclose{{}\left(\log\frac{t}{\varepsilon}}\right).

We denote the corresponding samples by $W_{i}=\Gamma_{i}(Y|_{[1,d_{i}]})$ , and let $S_{i}=Z_{i}|_{W_{i}}$ . Setting $\varepsilon_{i}^{\prime}=2^{-(\zeta/2)\delta\Delta_{i}}$ and observing that $\delta\Delta_{i}=(1-\frac{\zeta}{2})\delta\Delta_{i}+\log(1/\varepsilon^{\prime}_{i})$ , we get that $Z$ is $\varepsilon^{\prime}=\sum_{i}\varepsilon^{\prime}_{i}$ close to some $Z^{\prime}$ , an exact $((\Delta_{1},\ldots,\Delta_{t}),(1-\zeta)\delta)$ -source. From here onwards, assume that $Z$ is the exact block source, and aggregate the error.

Next, we invoke Lemma 2.16 with $\tau=\frac{\zeta\delta}{6}$ (notice that indeed $\varepsilon_{\Gamma}\leq\frac{\tau}{\log(1/\tau)}$ ), and get that for every $i\in[t]$ , and $z_{\mathsf{pre}}\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{\Delta_{1}+\ldots+\Delta_{i-1}}$ ,

S_{i}\mid\mathopen{}\mathclose{{}\left\{{(Z_{1},\ldots,Z_{i-1})=z_{\mathsf{pre}}}}\right\}

is $\varepsilon^{\prime\prime}_{i}=\gamma+2^{-\Omega(\tau\Delta_{i})}$ -close to having min-entropy $(1-\frac{\zeta}{2})^{2}\delta\cdot\ell_{i}\geq(1-\zeta)\delta\cdot\ell_{i}$ . Thus, in particular, it holds if we condition on any sample from $(S_{1},\ldots,S_{i-1})$ , and so we have that for every $i\in[t]$ ,

\mathopen{}\mathclose{{}\left(S_{1},\ldots,S_{i-1},S_{i}}\right)\approx_{\varepsilon^{\prime\prime}_{i}}\mathopen{}\mathclose{{}\left(S_{1},\ldots,S_{i-1},S^{\prime}_{i}}\right),

where $S^{\prime}_{i}$ has $(1-\zeta)\delta$ entropy rate. This means¹⁷¹⁷17In what follows, we use the fact that we can couple any two $X\approx_{\varepsilon}X^{\prime}$ with $(X,Y)\approx_{\varepsilon}(X^{\prime},Y)$ , for any joint distribution $(X,Y)$ . See, e.g., [Li15, Lemma 3.20]. that $(S_{1},\ldots,S_{t})$ has distance

\varepsilon^{\prime}+\sum_{i=1}^{t}\varepsilon_{i}^{\prime\prime}\leq t\cdot(\varepsilon^{\prime}_{1}+\varepsilon^{\prime\prime}_{1})\leq\varepsilon

from an $((\ell_{1},\ldots,\ell_{t}),(1-\zeta)\delta)$ block source, where we used the fact that the $2^{-\Omega(\tau\Delta_{1})}$ and $2^{-(\zeta/2)\delta\Delta_{1}}$ terms are at most $\frac{\varepsilon}{4t}$ , which follows from the fact that $c_{1}\log(t/\varepsilon)\leq\Delta_{1}$ for a suitable choice of $c_{1}$ .

To establish the runtime, note that we simply apply $\Gamma_{i}$ for each $i\in[t]$ , which takes

\sum_{i=1}^{t}\ell_{i}\cdot\operatorname{polylog}(\Delta_{i})=\operatorname{polylog}(\Delta_{t})\cdot\ell_{1}

time. This concludes our lemma. ∎

5.1.3 Item 4: Applying a block source extractor

We now wish to extract from our decreasing-blocks block source, and for that we combine Lemmas 5.3 and 5.2 with the block source extraction of Lemma 2.23, which will give us a nearly linear-time logarithmic-seed extractor that outputs $n^{\Omega(1)}$ bits. For the $\mathsf{Ext}_{i}$ -s in Lemma 2.23, we will use the fast hash-based extractors from Lemma 2.14.

Lemma 5.4.

There exists a small constant $c>0$ such that the following holds. For every large enough $n$ , any constant $\delta\in(0,1)$ , any $k\geq\delta n$ , and any $\varepsilon\geq 2^{-n^{c}}$ , there exists a $(k,\varepsilon)$ extractor

\mathsf{Ext}_{\mathsf{short}}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\rightarrow\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m}

where $d=O(\log(n/\varepsilon))$ , and $m=n^{c}$ . Moreover, given inputs $x\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}$ and $y\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}$ , we can compute $\mathsf{Ext}_{\mathsf{short}}(x,y)$ in time $\widetilde{O}(n)$ .

Proof.

Let $X$ be an $(n,k=\delta n)$ -source. Set $\varepsilon^{\prime}=\varepsilon/3$ , $\theta_{1}=8/10$ , $\theta_{2}=9/10$ , and $\zeta=1/10$ . We first apply Lemma 5.2 with $\Delta_{t}=n^{\theta_{2}}$ , $\Delta_{1}=n^{\theta_{1}}$ , and error $\varepsilon^{\prime}$ , where $t=O(\log n)$ is as guaranteed from the lemma’s statement. This requires a seed of length $d_{1}=O(\log(1/\varepsilon^{\prime}))=O(\log(1/\varepsilon))$ , and in time $\widetilde{O}(n)$ we output a random variable $Z_{1}$ which is $\varepsilon^{\prime}$ -close to a $((\Delta_{1},\ldots,\Delta_{t}),(1-\zeta)\delta)$ block source. Assume that $Z_{1}$ is exactly a block source, and aggregate the error.

Set $\beta=7/10$ , and $\gamma=6/10<\beta$ . Set $\alpha$ to be the constant such that $n^{\beta}\cdot\alpha^{t-1}=n^{\gamma}$ . We then apply Lemma 5.3 on $Z_{1}$ with that $\alpha$ , the same $\zeta$ , closeness $\varepsilon^{\prime}$ and an initial block length $\ell_{1}=n^{\beta}$ .This gives us a random variable $Z_{2}$ that is $2\varepsilon^{\prime}$ -close to a

\mathopen{}\mathclose{{}\left((\ell_{1}=n^{\beta},\ldots,\ell_{t}=n^{\gamma}),\delta^{\prime}\triangleq(1-\zeta)^{2}\delta}\right)

block source, requires a seed of length $d_{2}=O(\log(n/\varepsilon^{\prime}))=O(\log(n/\varepsilon))$ , and runs in time $O(n)$ . Again, assume that $Z_{2}$ is exactly a block source, and aggregate the error.

For our next and final step, set $d_{3}=c_{\mathsf{E}}\log(\ell_{t}/\varepsilon_{\mathsf{Ext}})$ where $c_{\mathsf{E}}$ is the constant guaranteed by Lemma 2.14. Also, let $\varepsilon_{\mathsf{Ext}}=\frac{\varepsilon^{\prime}}{6t}$ , and $\theta$ will be a constant whose value will be later determined. We will use the following extractors:

•

Let $\mathsf{Ext}_{t}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{\ell_{t}}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d_{3}}\rightarrow\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m_{t}=(1+\theta)d_{3}}$ be the $(k_{t}=(\delta^{\prime}/2)\ell_{t},\varepsilon_{\mathsf{Ext}})$ extractor guaranteed to us by Lemma 2.14. Notice that we need to satisfy $k_{t}\geq\theta d_{3}+c_{\mathsf{E}}\log(1/\varepsilon_{\mathsf{Ext}})$ . Looking forward, we will also need that $(\delta^{\prime}/2)\ell_{t}\leq\delta^{\prime}\ell_{t}-\log(1/\varepsilon_{\mathsf{Ext}})$ . Those constraints can be satisfied making sure that $\varepsilon$ is at most $2^{-\Omega(\ell_{t})}$ , where the hidden constant depends on $c_{\mathsf{E}}$ .

•

For each $i\in[t-1]$ , let

\mathsf{Ext}_{i}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{\ell_{i}}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m_{i+1}}\rightarrow\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m_{i}}

be the $(k_{i}=(\delta^{\prime}/2)\ell_{i},\varepsilon_{\mathsf{Ext}})$ extractor guaranteed to us by Lemma 2.14, where $m_{i}=(1+\theta)m_{i+1}$ . We need to make sure that $m_{i+1}\geq c_{\mathsf{E}}\log(\ell_{i}/\varepsilon_{\mathsf{Ext}})$ and that $k_{i}\geq\theta m_{i+1}+c_{\mathsf{E}}\log(1/\varepsilon_{\mathsf{Ext}})$ . To see that the latter holds, note that $k_{i}=(\delta^{\prime}/2)\ell_{1}\cdot\alpha^{i-1}\geq n^{\gamma/2}$ and that $\theta m_{i+1}+c_{\mathsf{E}}\log(1/\varepsilon_{\mathsf{Ext}})=\theta(1+\theta)^{t-i}d_{3}+c_{\mathsf{E}}\log(1/\varepsilon_{\mathsf{Ext}})<n^{\gamma/2},$ if we choose $\theta$ to be a small enough constant (with respect to the constant $\frac{\log n}{t}$ ) and $\varepsilon$ to be, again, at most $2^{-\Omega(\ell_{t})}$ . Also, here too, record that $(\delta^{\prime}/2)\ell_{i}\leq\delta^{\prime}\ell_{i}-\log(1/\varepsilon_{\mathsf{Ext}})$ , which follows easily, since the $\ell_{i}$ -s increase.

Everything is in place to apply our block source extraction, Lemma 2.23, on $Z_{2}$ and an independent and uniform seed of length $d_{3}$ .¹⁸¹⁸18Note that here, we use Lemma 2.23 with $n_{i}=(1+\theta)^{-i}n_{1}$ and $k_{i}\geq\theta n_{i}-\log(1/\varepsilon_{i})$ . The slack in entropy is needed since we work with the notion of block sources that also allows average conditional min-entropy. We can thus use the fact that under such setting of parameters, every extractor is an average case extractor with only a slight loss in parameters (see, e.g., [DORS08]). We omit the easy proof. We get that $\mathsf{BSExt}$ outputs $Z_{3}$ of length $m_{1}=n^{\Omega(1)}$ , which is $2t\varepsilon_{\mathsf{Ext}}\leq\varepsilon^{\prime}$ close to uniform, and runs in time $O\mathopen{}\mathclose{{}\left(\sum_{i=1}^{t}\ell_{i}\log\ell_{i}}\right)=O(n).$

To conclude, note that the overall error of our extractor is at most $3\varepsilon^{\prime}=\varepsilon$ , and the seed length is $d_{1}+d_{2}+d_{3}=O(\log(n/\varepsilon))$ . ∎

5.1.4 Improving the output length

The extractor $\mathsf{Ext}_{\mathsf{short}}$ from Lemma 5.4 only outputs $n^{\Omega(1)}$ bits. Here, we will use an extractor $\mathsf{Ext}_{\mathsf{aux}}$ that outputs a linear fraction of the entropy but requires a (relatively) long seed, and use Lemma 2.26 to boost the output length. For $\mathsf{Ext}_{\mathsf{aux}}$ , we will again use a sample-then-extract extractor, however this time, we can use independent samples to create a block source with exponentially decreasing blocks. This setting is easier, and we can simply use the original [NZ96] construction. Since a similar construction will be analyzed later in the paper (including a time complexity analysis), we choose to employ it instead of revisiting [NZ96].

Corollary 5.5.

There exist constants $\tau,c\in(0,1)$ and $C>1$ , such that for every positive integer $n$ , and any $\varepsilon\geq 2^{-n^{c}}$ , there exists a strong $(k=(1-\tau)n,\varepsilon)$ extractor

\mathsf{Ext}_{\mathsf{out}}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\rightarrow\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m}

where $d=O(\log n\cdot\log(n/\varepsilon))$ , and $m=ck-C\log(1/\varepsilon)$ . Moreover, given inputs $x\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}$ and $y\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}$ , we can compute $\mathsf{Ext}_{\mathsf{out}}(x,y)$ in time $\widetilde{O}(n)$ .

The correctness follows from Lemma 5.9 (without the need for a preliminary condensing step), employed with the hash functions of Lemma 2.14.

Plugging-in $\mathsf{Ext}_{\mathsf{out}}$ and $\mathsf{Ext}_{\mathsf{short}}$ into Lemma 2.26 readily gives the following result.

Lemma 5.6.

There exist constants $\tau,c\in(0,1)$ such that for every positive integer $n$ , and any $\varepsilon\geq 2^{-n^{c}}$ , there exists a $(k=(1-\tau)n,\varepsilon)$ extractor $\mathsf{Ext}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\rightarrow\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m}$ where $d=O(\log(n/\varepsilon))$ , and $m=ck$ . Moreover, given inputs $x\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}$ and $y\in\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}$ , we can compute $\mathsf{Ext}(x,y)$ in time $\widetilde{O}(n)$ .

To boost the output length from $\Omega(k)$ to $(1-\eta)k$ for any constant $\eta>0$ , we apply Lemma 2.22 a constant number of times depending only on $\eta$ (that is, we simply apply $\mathsf{Ext}$ with independent seeds and concatenate the outputs). To go from any min-entropy $k$ to entropy rate $1-\tau$ , we first apply a condenser, either the one from Theorem 3.10 or the one from Theorem 3.11. Specifically, when $k\geq C\log^{2}(n/\varepsilon)$ , we can use Theorem 3.10 which takes $\widetilde{O}(n)$ time. When $k$ is smaller, we can use Theorem 3.11, but this requires an extra preprocessing time which takes $T_{\mathsf{pre}}=\operatorname{polylog}(1/\varepsilon)$ times. Note that the bound on $\varepsilon$ from Lemma 5.6 translates to $\varepsilon\geq 2^{-k^{c}}$ , so we can (if needed) modify $c$ so that $T_{\mathsf{pre}}=O(n)$ . This finally gives us our main theorem for this section, Theorem 5.1, apart from the strongness property, which we now discuss.

The non-recursive construction is strong.

In what follows, we refer to the itemized list in the beginning of the section. The condensing step, Item 1, is strong, since we use strong condensers. Next, inspecting the proofs of Lemmas 5.2 and 5.3, we see that both samplings procedures yield a good sample with high probability over the fixing of the seed, so Items 2 and 3 hold in a strong manner as well. Item 4 follows by applying a block source extractor, which is strong since the extraction steps output the seed. Thus, the extractor $\mathsf{Ext}_{\mathsf{short}}$ from Lemma 5.4 is in fact strong. For the output-extending phase, Lemma 2.26 readily tells us that the extractor from Lemma 5.6 is strong. Finally, we apply that extractor several times with independent seeds, and the strongness of that procedure is guaranteed from Lemma 2.22.

5.2 A Recursive Construction

In this section, we prove the following.

Theorem 5.7 (recursive construction).

For any constant $\eta>0$ there exists a constant $C>0$ such that the following holds. For any positive integers $n$ , $k\leq n$ , and any $\varepsilon>0$ such that $k\geq C\log(n/\varepsilon)$ there exists a strong $(k,\varepsilon)$ -seeded extractor

\mathsf{Ext}\colon\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m}

with seed length $d\leq C\log(n/\varepsilon)$ and output length $m\geq(1-\eta)k$ . Furthermore,

•

if $k\geq 2^{C\log^{*}\!n}\cdot\log^{2}(n/\varepsilon)$ , then $\mathsf{Ext}$ is computable in time $\widetilde{O}(n)$ ;
•

if $k<2^{C\log^{*}\!n}\cdot\log^{2}(n/\varepsilon)$ , then $\mathsf{Ext}$ is computable in time $\widetilde{O}(n)$ after a preprocessing step that corresponds to finding primitive elements of $O(\log\log n)$ fields $\mathds{F}_{q}$ with orders $q\leq\operatorname{poly}(n/\varepsilon)$ powers of $2$ .

In a nutshell, our construction behind Theorem 5.7 works by considering two cases. If $\varepsilon>Cn^{3}\cdot 2^{-k/\log k}$ , then we instantiate the recursive approach of Srinivasan and Zuckerman [SZ99] appropriately. Otherwise, we apply the recursive approach of Guruswami, Umans, and Vadhan [GUV09].

5.2.1 The (extremely) low-error case

In this section, we consider the lower error case of Theorem 5.7 where $\varepsilon\leq Cn^{3}\cdot 2^{-k/\log k}$ . We instantiate the recursive approach from [GUV09, Section 4.3.3] appropriately, and analyze its time complexity. Crucially, because of our upper bound on $\varepsilon$ , we will only need to run $O(\log\log n)$ levels of their recursive approach.

In order to obtain the statement of Theorem 5.7 for output length $m\geq(1-\eta)k$ with $\eta$ an arbitrarily small constant, it suffices to achieve output length $m=\Omega(k)$ and then apply Lemma 2.22 a constant number of times depending only on $\eta$ . Therefore, we focus on achieving output length $m=\Omega(k)$ .

Theorem 5.8.

There exist constants $c,C>0$ such that the following holds. For any positive integers $n$ and $k\leq n$ and any $\varepsilon\in(0,Cn^{3}\cdot 2^{-k/\log k}]$ further satisfying $k>C\log(n/\varepsilon)$ , there exists a strong $(k,\varepsilon)$ -seeded extractor $\mathsf{Ext}\colon\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m}$ with seed length $d\leq C\log(n/\varepsilon)$ and output length $m\geq k/3$ .

Furthermore, $\mathsf{Ext}$ is computable in time $\widetilde{O}(n)$ after a preprocessing step that corresponds to finding primitive elements of $O(\log\log n)$ fields $\mathds{F}_{q}$ with orders $q\leq\operatorname{poly}(n/\varepsilon)$ , each a power of $2$ .

Proof.

We discuss our instantiation of the recursive approach from [GUV09] in detail, as it will be relevant to the time complexity analysis. Let $\varepsilon_{0}=\varepsilon/\log^{C}n$ and $d=C\log(n/\varepsilon_{0})=O(\log(n/\varepsilon))$ for a large enough constant $C>0$ to be determined later. For an integer $k\geq 0$ , let $i(k)=\mathopen{}\mathclose{{}\left\lceil\log\mathopen{}\mathclose{{}\left(\frac{k}{8d}}\right)}\right\rceil$ , which determines the number of levels in our recursion. It will be important for bounding the time complexity of this construction to observe that

i(k)=O(\log\log n)

(2)

because $\varepsilon\leq Cn^{3}\cdot 2^{-k/\log k}$ . For each $k$ , we define a family of strong $(k,\varepsilon_{i(k)})$ -seeded extractors $\mathsf{Ext}_{i(k)}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\to\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m}$ with $\varepsilon_{i(k)}\leq 9\varepsilon_{i(k/3)}+63\varepsilon_{0}$ when $i(k)>0$ by induction on $i(k)$ . Solving this recursion yields $\varepsilon_{i(k)}=2^{O(i(k))}\cdot\varepsilon_{0}\leq\varepsilon$ , provided that $\varepsilon_{0}=\varepsilon/\log^{C}n$ for a sufficiently large constant $C>0$ .

Base case.

For the base case $i(k)=0$ , which holds when $k\leq 8d$ , we choose $\mathsf{Ext}_{0}$ to be the $(k,\varepsilon_{0})$ -seeded extractor defined as follows. On input an $(n,k)$ -source $X$ ,

1.

Apply the lossy RS strong condenser $\mathsf{RSCond}$ (Theorem 3.11) on $X$ , instantiated with $\alpha=1/400$ and error $\varepsilon^{\prime}_{0}=\varepsilon_{0}/2$ . When $C$ is large enough we have $k\geq(2+\alpha)\log(1/\varepsilon^{\prime}_{0})$ , and require a seed $Y_{1}$ of length $d_{1}\leq C_{0}\log(n/\varepsilon^{\prime}_{0})$ , for some constant $C_{0}>0$ . The corresponding output $X^{\prime}$ satisfies $Y_{1}\circ X^{\prime}\approx_{\varepsilon^{\prime}_{0}}Y_{1}\circ Z$ , for some $(n^{\prime},k^{\prime})$ -source $Z$ with $k^{\prime}\geq(1-2\alpha)n^{\prime}=(1-1/200)n^{\prime}$ .
2.

Let $\mathsf{Ext}^{\prime}_{0}\colon\{0,1\}^{n^{\prime}}\times\{0,1\}^{d_{2}}\to\{0,1\}^{m^{\prime}}$ be the average-case strong $(k^{\prime},\varepsilon^{\prime}_{0})$ -seeded extractor from Lemma 2.25 instantiated with $t=10$ , which requires a seed $Y_{2}$ of length $d_{2}\leq k^{\prime}/10+C^{\prime}_{0}\log(n^{\prime}/\varepsilon^{\prime}_{0})$ for some constant $C^{\prime}_{0}>0$ and has output length $m^{\prime}\geq k^{\prime}/2$ . The conditions for the invocation of Lemma 2.25 with $t=10$ are satisfied since $k^{\prime}\geq(1-1/200)n^{\prime}=(1-\frac{1}{20t})n^{\prime}$ and

$2^{-n^{\prime}/500}\leq 2^{-k/500}\leq(\varepsilon_{0}/n)^{C/500}\leq\varepsilon^{\prime}_{0},$

where the second inequality uses the theorem’s hypothesis that $k\geq C\log(n/\varepsilon)$ with $C>0$ a sufficiently large constant.

We set $Y=Y_{1}\circ Y_{2}$ and define $\mathsf{Ext}_{0}(X,Y)=\mathsf{Ext}^{\prime}_{0}(\mathsf{RSCond}(X,Y_{1}),Y_{2})$ . From the discussion above, we have

Y\circ\mathsf{Ext}_{0}(X,Y)=Y_{1}\circ Y_{2}\circ\mathsf{Ext}^{\prime}_{0}(\mathsf{RSCond}(X,Y_{1}),Y_{2})\approx_{\varepsilon^{\prime}_{0}}Y_{1}\circ Y_{2}\circ\mathsf{Ext}^{\prime}_{0}(Z,Y_{2})\approx_{\varepsilon^{\prime}_{0}}Y_{1}\circ Y_{2}\circ U_{m^{\prime}}.

Therefore, the triangle inequality implies that $\mathsf{Ext}_{0}$ is an average-case strong $(k,2\varepsilon^{\prime}_{0}=\varepsilon_{0})$ -seeded extractor. It remains to argue about the seed length, output length, and time complexity of $\mathsf{Ext}_{0}$ . The seed length of $\mathsf{Ext}_{0}$ is

d_{1}+d_{2}\leq k^{\prime}/10+(C_{0}+C^{\prime}_{0})\log(n^{\prime}/\varepsilon^{\prime}_{0})\leq 0.8d+(C_{0}+C^{\prime}_{0})\log(n^{\prime}/\varepsilon^{\prime}_{0})\leq d,

provided that $d=C\log(n/\varepsilon)$ with $C$ a sufficiently large constant. The output length of $\mathsf{Ext}_{0}$ is $m^{\prime}\geq k^{\prime}/2\geq k/3$ , since $k^{\prime}\geq(1-1/200)k$ . Finally, both steps above take time $\widetilde{O}(n)$ , and so $\mathsf{Ext}_{0}$ can be computed in time $\widetilde{O}(n)$ after a $\operatorname{polylog}(1/\varepsilon)$ preprocessing step.

Induction step.

When $i(k)>0$ , we assume the existence of the desired average-case strong extractors $\mathsf{Ext}_{i(k^{\prime})}$ for all $i(k^{\prime})<i(k)$ as the induction hypothesis. More precisely, we assume that for all $k^{\prime}$ such that $i(k^{\prime})<i(k)$ there exists a family of average-case strong $(k^{\prime},\varepsilon_{i(k^{\prime})})$ -seeded extractors $\mathsf{Ext}_{i(k^{\prime})}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d}\to\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{k^{\prime}/3}$ parameterized by $n$ computable in time $\widetilde{O}(n)$ after a one-time preprocessing step. We proceed as follows on input an $(n,k)$ -source $X$ :

1.

Apply the lossy RS strong $(k,k^{\prime},\varepsilon_{1}=\varepsilon_{0}^{2})$ -condenser $\mathsf{RSCond}$ (Theorem 3.11) on $X$ with $\alpha=1/20$ and a seed $Y_{\mathsf{RS}}$ of length $d_{\mathsf{RS}}\leq C_{\mathsf{RS}}\log(n/\varepsilon_{0})$ . Since $k>8d\geq\frac{\log(1/\varepsilon_{1})}{\alpha(1+2\alpha)}$ if $C$ is a large enough constant, by the second part of Theorem 3.11 we know that with probability at least $1-\varepsilon_{0}$ over the choice of $Y_{\mathsf{RS}}=y$ it holds that the corresponding condenser output $X^{\prime}$ is $\varepsilon_{0}$ -close to some $(n^{\prime},k^{\prime})$ -source $Z$ with $k^{\prime}\geq(1-2\alpha)n^{\prime}=0.9n^{\prime}$ . For the sake of exposition, from here onwards we work under such a good choice of the seed $Y_{\mathsf{RS}}$ , and we will add the $\varepsilon_{0}$ slack term to the final error.
2.

Split $X^{\prime}=X^{\prime}_{1}\circ X^{\prime}_{2}$ with $|X^{\prime}_{1}|=|X^{\prime}_{2}|=n^{\prime}/2\triangleq n^{\prime\prime}$ . By Lemma 2.24 instantiated with $n^{\prime}$ and $\Delta=0.1n^{\prime}$ and the fact that $X^{\prime}$ is $\varepsilon_{0}$ -close to an $(n^{\prime},k^{\prime})$ -source, we get that $X^{\prime}_{1}\circ X^{\prime}_{2}$ is $(\varepsilon_{\mathsf{RS}}+2\varepsilon_{0}=3\varepsilon_{0})$ -close to an $((n^{\prime\prime},n^{\prime\prime}),k^{\prime\prime}/n^{\prime\prime})$ -block-source $W_{1}\circ W_{2}$ with

$k^{\prime\prime}\geq k^{\prime}/2-\Delta-\log(1/\varepsilon_{0})\geq 0.4n^{\prime}-\log(1/\varepsilon_{0})\geq k/3,$ (3)

since $n^{\prime}\geq k>d=C\log(n/\varepsilon_{0})$ for a sufficiently large constant $C>0$ .

Apply the lossy RS strong $(k^{\prime\prime},k^{\prime\prime\prime},\varepsilon_{1}=\varepsilon_{0}^{2})$ -condenser $\mathsf{RSCond}^{\prime}$ (Theorem 3.11) to $X^{\prime}_{2}$ with $\alpha=1/800$ and a seed $Y^{\prime}_{\mathsf{RS}}$ of length at most $d^{\prime}_{\mathsf{RS}}=C^{\prime}_{\mathsf{RS}}\log(n^{\prime\prime}/\varepsilon_{1})\leq C^{\prime}_{\mathsf{RS}}\log(n/\varepsilon_{0})$ . From Item 2 and the data-processing inequality, we know that

Y^{\prime}_{\mathsf{RS}}\circ X^{\prime}_{1}\circ X^{\prime\prime}_{2}=Y^{\prime}_{\mathsf{RS}}\circ X^{\prime}_{1}\circ\mathsf{RSCond}(X^{\prime}_{2},Y^{\prime}_{\mathsf{RS}})\approx_{3\varepsilon_{0}}Y^{\prime}_{\mathsf{RS}}\circ W_{1}\circ\mathsf{RSCond}(W_{2},Y^{\prime}_{\mathsf{RS}}).

(4)

Since $(W_{2}|W_{1}=w_{1})$ is a $k^{\prime\prime}$ -source for any $w_{1}$ in the support of $W_{1}$ , we conclude from Theorem 3.11 and Equation 4 that

Y^{\prime}_{\mathsf{RS}}\circ W_{1}\circ\mathsf{RSCond}(W_{2},Y^{\prime}_{\mathsf{RS}})\approx_{\varepsilon_{1}}Y^{\prime}_{\mathsf{RS}}\circ W_{1}\circ\widetilde{W_{2}},

where $\widetilde{W_{2}}\sim\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n^{\prime\prime\prime}}$ and $\mathbf{H}_{\infty}(Y^{\prime}_{\mathsf{RS}}\circ\widetilde{W_{2}}|W_{1}=w_{1})\geq k^{\prime\prime\prime}+d^{\prime}_{\mathsf{RS}}$ for all $w_{1}$ in the support of $W_{1}$ , with $n^{\prime\prime\prime}\geq k^{\prime\prime}\geq k^{\prime\prime\prime}\geq(1-1/400)n^{\prime\prime\prime}$ . This is a valid invocation since $k^{\prime\prime}\geq k/3>8d/3>d\geq\frac{\log(1/\varepsilon_{1})}{\alpha(1+2\alpha)}$ by Equation 3. Therefore, by the second part of Theorem 3.11, with probability at least $1-\varepsilon_{0}$ over the choice of of $Y^{\prime}_{\mathsf{RS}}=y^{\prime}$ we get that

(W_{1}\circ\widetilde{W_{2}}|Y^{\prime}_{\mathsf{RS}}=y^{\prime})\approx_{\varepsilon_{0}}W_{1}\circ W^{\prime}_{2},

(5)

where $W^{\prime}_{2}\sim\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n^{\prime\prime\prime}}$ satisfies $\mathbf{H}_{\infty}(W^{\prime}_{2}|W_{1}=w_{1})\geq k^{\prime\prime\prime}\geq(1-1/400)n^{\prime\prime\prime}$ . Fix such a good fixing of $Y^{\prime}_{\mathsf{RS}}$ from now onwards. As before, we will account for the probability $\varepsilon_{0}$ of fixing a bad seed in the final extractor error. Then, by combining Equations 4 and 5 we get that $X^{\prime}_{1}\circ X^{\prime\prime}_{2}$ is $(\varepsilon_{\mathsf{BS}}=4\varepsilon_{0})$ -close to an $((n^{\prime\prime},n^{\prime\prime\prime}),k^{\prime\prime},k^{\prime\prime\prime})$ -block source.

We will now apply block source extraction to $X^{\prime}_{1}\circ X^{\prime\prime}_{2}$ , which we recall is $(\varepsilon_{\mathsf{BS}}=4\varepsilon_{0})$ -close to an $((n^{\prime\prime},n^{\prime\prime\prime}),k^{\prime\prime},k^{\prime\prime\prime})$ -block source. We instantiate Lemma 2.23 with $\mathsf{Ext}_{2}$ being the strong extractor from Lemma 2.25 with source input length $n^{\prime\prime\prime}$ , min-entropy requirement $k^{\prime\prime\prime}$ , error $\varepsilon_{\mathsf{BExt}}=\varepsilon_{0}$ , output length $d$ , and $t=16$ . This requires a seed of length $d_{\mathsf{BExt}}\leq d/16+C^{\prime}_{0}\log(n/\varepsilon_{0})$ . This instantiation of Lemma 2.25 is valid since $k^{\prime\prime\prime}\geq(1-1/400)n^{\prime\prime\prime}>(1-\frac{1}{20t})n^{\prime\prime\prime}$ and

k^{\prime\prime\prime}\geq 0.95n^{\prime\prime\prime}\geq 0.95k^{\prime\prime}\geq\frac{0.95k}{3}>\frac{0.95\cdot 8d}{3}>2d,

where we used the fact that $i(k)>0$ , and so $k>8d$ . For $\mathsf{Ext}_{1}$ we choose the average-case strong extractor $\mathsf{Ext}_{i(k/3)}$ (recall that $k^{\prime\prime}\geq k/3$ and note that $i(k/3)<i(k)$ ) with input length $n^{\prime\prime}$ , entropy requirement $k/3$ , error $\varepsilon_{i(k/3)}$ , output length at least $(k/3)/3=k/9$ , and seed length $d$ guaranteed by the induction hypothesis above.

Items 1, 2, 3 and 4 above yield a strong seeded extractor $\mathsf{Ext}^{\prime}_{i(k)}\colon\{0,1\}^{n}\times\{0,1\}^{d^{\prime}}\to\{0,1\}^{m^{\prime}}$ with min-entropy requirement $k$ , error $\varepsilon^{\prime}=\varepsilon_{i(k/3)}+\varepsilon_{\mathsf{BExt}}+\varepsilon_{\mathsf{BS}}+2\varepsilon_{0}=\varepsilon_{i(k/3)}+7\varepsilon_{0}$ (where the $2\varepsilon_{0}$ term comes from the two fixings of the seeds in the two condensing steps in Items 1 and 3), seed length

d^{\prime}=d_{\mathsf{BExt}}+d^{\prime}_{\mathsf{RS}}+d_{\mathsf{RS}}\leq d/16+C^{\prime}\log(n/\varepsilon_{0}),

for some constant $C^{\prime}>0$ , and output length $m^{\prime}=k/9$ .

To conclude the definition of $\mathsf{Ext}_{i(k)}$ , we need to increase the output length of $\mathsf{Ext}^{\prime}_{i(k)}$ from $k/9$ to $k/3$ . To that end, we use Lemma 2.22. Applying Lemma 2.22 once with $\mathsf{Ext}_{1}=\mathsf{Ext}^{\prime}_{i(k_{1})}$ with $k_{1}=k$ and $\mathsf{Ext}_{2}=\mathsf{Ext}^{\prime}_{i(k_{2})}$ with $k_{2}=k-k/9-1=8k/9-1$ and $g=1$ yields a strong $(k,3\varepsilon^{\prime})$ -seeded extractor $\mathsf{Ext}^{\prime\prime}_{i(k)}$ with output length $(k_{1}+k_{2})/9\geq k(1-(8/9)^{2})-1$ and seed length $2(d/16+C^{\prime}\log(n/\varepsilon_{0}))=d/8+2C^{\prime}\log(n/\varepsilon_{0})$ . Applying Lemma 2.22 again with $\mathsf{Ext}_{1}=\mathsf{Ext}^{\prime\prime}_{i(k_{1})}$ for $k_{1}=k$ and $\mathsf{Ext}_{2}=\mathsf{Ext}^{\prime\prime}_{i(k_{2})}$ for $k_{2}=(8/9)^{2}k$ and $g=1$ yields a strong $(k,9\varepsilon^{\prime})$ -seeded extractor with output length $m\geq k(1-(8/9)^{4})-1\geq k/3$ and seed length $2(d/8+2C^{\prime}\log(n/\varepsilon_{0}))=d/4+4C^{\prime}\log(n/\varepsilon_{0})\leq d$ , which we set as $\mathsf{Ext}_{i(k)}$ . This second invocation of Lemma 2.22 is also valid, since $k_{2}=(8/9)^{2}k=k-(k(1-(8/9)^{2})-1)-1=k_{1}-m_{1}-g$ . Note that the error $\varepsilon_{i(k)}=9\varepsilon^{\prime}=9\varepsilon_{i(k/3)}+63\varepsilon_{0}$ , as desired.

Time complexity and final error.

It remains to analyze the time complexity and the overall error of the recursive procedure above. Evaluating $\mathsf{Ext}_{i(k)}$ requires at most eight evaluations of the condenser from Theorem 3.11, four evaluations of the fast hash-based extractor from Lemma 2.25, four evaluations of $\mathsf{Ext}_{i(k^{\prime\prime})}$ for some $i(k^{\prime\prime})<i(k)$ , and simple operations that can be done in time $\widetilde{O}(n)$ . This means that the overall time complexity is $4^{i(k)}\cdot\widetilde{O}(n)=\widetilde{O}(n)$ after a one-time preprocessing step independent of the source and seed, since $4^{i(k)}=\operatorname{poly}(\log n)$ by Equation 2. This preprocessing step corresponds to finding primitive elements for $O(\log\log n)$ fields $\mathds{F}_{q}$ with orders $q\leq\operatorname{poly}(n/\varepsilon_{0})=\operatorname{poly}(n/\varepsilon)$ powers of $2$ . Furthermore, $\varepsilon_{i(k)}=O(\varepsilon_{0}+\varepsilon_{i(k/3)})$ for all $k$ , and so $\varepsilon_{i(k)}=2^{O(i(k))}\varepsilon_{0}=\operatorname{poly}(\log n)\cdot\varepsilon_{0}\leq\varepsilon$ provided that $\varepsilon_{0}\leq\varepsilon/\log^{C}n$ for a large enough constant $C>0$ . ∎

5.2.2 The (relatively) high-error case

In this section, we consider the higher error case where $\varepsilon\geq Cn^{3}\cdot 2^{-k/\log k}$ . We instantiate the recursive approach of Srinivasan and Zuckerman [SZ99, Section 5.5] appropriately with our building blocks and analyze its complexity.

Lemma 5.9 (analogous to [SZ99, Corollary 5.10], with different instantiation and additional complexity claim).

There exist constants $c,C>0$ such that the following holds. Suppose that for any positive integers $n_{0}$ , $k_{0}=0.7n_{0}$ , and some $\varepsilon_{0}=\varepsilon_{0}(n_{0})\geq 2^{-ck_{0}}$ and $m_{0}=m_{0}(n_{0})$ there exists a strong $(k_{0},\varepsilon_{0})$ -seeded extractor $\mathsf{Ext}_{0}\colon\{0,1\}^{n_{0}}\times\{0,1\}^{d_{0}}\to\{0,1\}^{m_{0}}$ with seed length $d_{0}\leq u\cdot\log(n_{0}/\varepsilon_{0})\leq k_{0}$ . Then, for any positive integers $n$ and $k\leq n$ there exists a family of strong $(k,\varepsilon)$ -seeded extractors $\mathsf{Ext}\colon\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m}$ with error $\varepsilon\leq C\log u\cdot\varepsilon_{0}(ck)$ , seed length $d\leq C\log u\cdot\log(n/\varepsilon_{0}(ck))$ , and output length $m\geq m_{0}(ck)$ . Furthermore,

1.

If $\mathsf{Ext}_{0}$ is computable in time $\widetilde{O}(n_{0})$ and $k\geq C\log^{2}(n/\varepsilon)$ , then $\mathsf{Ext}$ is computable in time $\widetilde{O}(n)$ ;
2.

If $\mathsf{Ext}_{0}$ is computable in time $\widetilde{O}(n_{0})$ after a preprocessing step corresponding to finding primitive elements of $j$ fields $\mathds{F}_{q}$ of orders $q\leq\operatorname{poly}(n/\varepsilon_{0})$ , then $\mathsf{Ext}$ is computable in time $\widetilde{O}(n)$ after a preprocessing step corresponding to finding primitive elements of $j+1$ fields $\mathds{F}_{q}$ of orders $q\leq\operatorname{poly}(n/\varepsilon_{0})$ .

Proof.

We begin by setting up relevant notation:

•

Let $C_{\mathsf{blocks}}\geq 1$ be a constant to be determined. Set $\ell_{0}=\frac{k}{100\cdot C_{\mathsf{blocks}}}$ and $k_{0}=0.7\ell_{0}$ . For $\varepsilon_{0}=\varepsilon_{0}(\ell_{0})$ and $m_{0}=m_{0}(\ell_{0})$ , we define $\ell_{1}=C_{\mathsf{blocks}}\cdot u\log(\ell_{0}/\varepsilon_{0})$ . Then, we define $\ell_{i}=0.9\ell_{i-1}$ for all $i\geq 2$ . The $\ell_{i}$ ’s will be block lengths for a block source $Z$ . In particular, when performing block source extraction from $Z$ we will instantiate $\mathsf{Ext}_{0}$ with input length $n_{0}=\ell_{0}$ .
•

Define $m_{1}=u\cdot\log(\ell_{0}/\varepsilon_{0})$ and $m_{i}=0.9m_{i-1}$ for all $i\geq 2$ . The $m_{i}$ ’s will be output lengths for block source extraction from $Z$ .
•

Set $t=1+\frac{\log\mathopen{}\mathclose{{}\left(u/\log u}\right)}{\log(1/0.9)}$ . This will be the number of blocks of $Z$ . We have $m_{t}=0.9^{t-1}m_{1}=\log u\cdot\log(\ell_{0}/\varepsilon_{0})$ . Furthermore, since $\ell_{1}=C_{\mathsf{blocks}}\cdot m_{1}$ , we also have that $\ell_{i}=C_{\mathsf{blocks}}\cdot m_{i}$ for all $i\geq 1$ .

Let $X$ be an arbitrary $(n,k)$ -source. The extractor $\mathsf{Ext}\colon\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m}$ proceeds as follows on input $X$ :

1.

Using a fresh seed $Y_{\mathsf{Cond}}$ of length $C_{\mathsf{Cond}}\log(n/\varepsilon_{0})$ , apply a strong $(k,k^{\prime},\varepsilon_{0}^{2})$ -condenser $\mathsf{Cond}$ to $X$ . If $k\geq C\log^{2}(n/\varepsilon_{0})$ for an apropriately large constant $C>0$ , then we instantiate $\mathsf{Cond}$ with the lossless KT $(k,k^{\prime}=k,\varepsilon_{\mathsf{Cond}})$ -condenser (Theorem 3.10). Otherwise, we instantiate $\mathsf{Cond}$ with the lossy RS $(k,k^{\prime}\geq 0.95k,\varepsilon_{\mathsf{Cond}})$ -condenser (Theorem 3.11) instantiated with $\alpha=0.05$ . By the second part of either Theorem 3.10 or Theorem 3.11, we get that with probability at least $1-\varepsilon_{0}$ over the choice of $Y_{\mathsf{Cond}}=y$ it holds that $X^{\prime}=\mathsf{Cond}(X,y)$ is $\varepsilon_{0}$ -close to an $(n^{\prime},k^{\prime})$ -source with $k^{\prime}\geq 0.95n^{\prime}$ . From here onwards we work under such a good fixing $Y_{\mathsf{Cond}}=y$ , and will account for the $\varepsilon_{0}$ error term in the final extractor error later on.

We use $X^{\prime}$ and Lemma 2.16 to generate a block source $Z$ with geometrically decreasing block lengths $\ell_{0},\ell_{1},\dots,\ell_{t}$ defined above.

For each $i=0,1,\dots,t$ , let $\mathsf{Samp}_{i}\colon\{0,1\}^{r_{i}}\to[n^{\prime}]^{\ell_{i}}$ be the $(\theta=1/100,\gamma=\varepsilon_{0})$ -averaging sampler from Lemma 2.21 with input length $r_{i}=C_{\mathsf{Samp}}\log(n^{\prime}/\varepsilon_{0})$ for some constant $C_{\mathsf{Samp}}>0$ . We choose the constant $C_{\mathsf{blocks}}$ above to be large enough so that $n^{\prime}\geq\ell_{i}\geq\ell_{t}\geq C^{\prime}_{\mathsf{Samp}}\log(1/\varepsilon_{0})/\theta^{2}$ for all $i\in[t]$ , where $C^{\prime}_{\mathsf{Samp}}$ is the constant $C$ from Lemma 2.21. To see that $\ell_{i}\leq n^{\prime}$ for $i=0,\dots,t$ (and so indeed Lemma 2.21 can be applied to obtain $\ell_{i}$ samples), note that

\sum_{i=0}^{t}\ell_{i}\leq\sum_{i=0}^{\infty}\ell_{i}=10\ell_{1}+\ell_{0}\leq k/9<n^{\prime}.

(6)

The second-to-last inequality uses the fact that

\ell_{1}=C_{\mathsf{blocks}}\cdot u\log(\ell_{0}/\varepsilon_{0})\leq C_{\mathsf{blocks}}\cdot k_{0}\leq C_{\mathsf{blocks}}\cdot\ell_{0}=k/100,

where the first inequality holds since $u\log(\ell_{0}/\varepsilon_{0})\leq k_{0}$ is an hypothesis in the lemma statement. We also assume that $\varepsilon_{0}\geq 2^{-ck_{0}}$ for a constant $c>0$ small enough so that

\ell_{0}=\frac{k}{100C_{\mathsf{blocks}}}\geq C^{\prime}_{\mathsf{Samp}}\cdot ck_{0}/\theta^{2}\geq C^{\prime}_{\mathsf{Samp}}\log(1/\varepsilon_{0})/\theta^{2},

where we recall that $k_{0}=0.7\ell_{0}$ , meaning that the conditions of Lemma 2.21 are satisfied for all $i=0,\dots,t$ .

For each $i=0,1,\dots,t$ , let $Y_{i}$ be a fresh seed of length $r_{i}$ . We set the $i$ -th block as $Z_{i}=X^{\prime}_{\mathsf{Samp}(Y_{i})}$ . By Lemma 2.16 instantiated with $X^{\prime}$ and $\mathsf{Samp}_{0}$ , we conclude that

Y_{0}\circ Z_{0}\approx_{\varepsilon_{0}+2^{-c_{\mathsf{Samp}}k^{\prime}}}Y_{0}\circ Z^{\prime}_{0},

with $c_{\mathsf{Samp}}>0$ an absolute constant guaranteed by Lemma 2.16, where $(Z^{\prime}_{0}|Y_{0}=y)$ is an $(\ell_{0},0.9\ell_{0})$ -source for every $y$ . We now argue how this guarantee extends to more blocks. Consider an arbitrary $i$ and fixings $Y_{0}=y_{0},\dots,Y_{i-1}=y_{i-1}$ . Then, Lemma 2.6 with $\delta=2^{-c_{\mathsf{Samp}}k}$ and $\ell=k/9$ (from the upper bound in Equation 6) implies that

\mathbf{H}_{\infty}(X|(Z^{\prime}_{0}|Y_{0}=y_{0})=z_{0},\dots,(Z^{\prime}_{i-1}|Y_{i-1}=y_{i-1})=z_{i-1})\geq 0.8n^{\prime}

except with probability at most $2^{-c_{\mathsf{Samp}}k}$ over the choice of $z_{0},\dots,z_{i-1}$ , which we can absorb into the statistical distance, since $k^{\prime}\geq 0.95n^{\prime}\geq 0.95k$ . Consequently, from Lemma 2.16 we get that

Y_{0},Z^{\prime}_{0},\dots,Y_{i-1},Z^{\prime}_{i-1},Y_{i},Z_{i}=X_{\mathsf{Samp}(Y_{i})}\approx_{\varepsilon_{0}+2\cdot 2^{-c_{\mathsf{Samp}}k}}Y_{0},Z^{\prime}_{0},\dots,Y_{i-1},Z^{\prime}_{i-1},Y_{i},Z^{\prime}_{i},

(7)

where $(Z^{\prime}_{i}|Y_{0}=y_{0},Z^{\prime}_{0}=z_{0},\dots,Y_{i-1}=y_{i-1},Z^{\prime}_{i-1}=z_{i-1},Y_{i}=y_{i})$ is an $(\ell_{i},0.7\ell_{i})$ -source for any choice of $y_{0},z_{0},\dots,y_{i-1},z_{i-1},y_{i}$ . Combining Equation 7 with the triangle inequality over all $0\leq i\leq t$ , we conclude that $Z=Z_{0}\circ Z_{1}\circ\cdots\circ Z_{t}$ is $\varepsilon_{\mathsf{block}}$ -close to an exact $(\ell_{0},\dots,\ell_{t},0.7)$ -block-source $Z^{\prime}$ , where $\varepsilon_{\mathsf{block}}=(t+1)(\varepsilon_{0}+2\cdot 2^{-c_{\mathsf{Samp}}k})$ .

We apply block source extraction (Lemma 2.23) to $Z=Z_{0}\circ Z_{1}\circ\cdots\circ Z_{t}$ . More precisely, let $\mathsf{BExt}\colon\{0,1\}^{\ell_{0}}\times\cdots\times\{0,1\}^{\ell_{t}}\times\{0,1\}^{d_{t}}\to\{0,1\}^{m_{0}}$ be the strong $(k_{0},k_{1},\dots,k_{t},(t+1)\varepsilon_{0})$ -block-source extractor with $k_{i}=0.7\ell_{i}$ obtained via Lemma 2.23 as follows. We instantiate $\mathsf{Ext}_{0}$ with the strong extractor promised by the lemma statement with seed length $d_{0}\leq u\cdot\log(\ell_{0}/\varepsilon_{0})=m_{1}$ . For $i\in[t]$ , we instantiate $\mathsf{Ext}_{i}\colon\{0,1\}^{\ell_{i}}\times\{0,1\}^{d_{i}}\to\{0,1\}^{m_{i}}$ as the strong $(k_{i}=0.7\ell_{i},\varepsilon_{0})$ -seeded extractor from Lemma 2.14 with seed length $d_{i}=2m_{i}+4\log(\ell_{i}/\varepsilon_{0})+8$ . We choose the constant $C_{\mathsf{blocks}}$ to be large enough so that

m_{i}=\ell_{i}/C_{\mathsf{blocks}}\leq 0.7\ell_{i}-16\log(4/\varepsilon_{0})=k_{i}-16\log(4/\varepsilon_{0}),

as required by Lemma 2.14. This is possible since by choosing $C_{\mathsf{blocks}}$ large enough we have

\ell_{i}\geq\ell_{t}=C_{\mathsf{blocks}}\cdot m_{t}=C_{\mathsf{blocks}}\log u\cdot\log(\ell_{0}/\varepsilon_{0})\geq 100\log(4/\varepsilon_{0})

for all $i\in[t]$ , and so $0.7\ell_{i}-16\log(4/\varepsilon_{0})\geq\ell_{i}/2$ for all $i\in[t]$ . Furthermore, for any $i\geq 2$ the output length $m_{i}$ of $\mathsf{Ext}_{i}$ satisfies

d_{i}+m_{i}=3m_{i}+4\log(n/\varepsilon_{0})+8\geq 2m_{i-1}+4\log(n/\varepsilon_{0})+8\geq d_{i-1},

where we recall that $m_{i}=m_{i-1}/0.9$ for $i\geq 2$ . Finally, the output length of $\mathsf{Ext}_{1}$ satisfies $d_{1}+m_{1}\geq m_{1}\geq d_{0}$ , where we recall that $d_{0}$ is the seed length of $\mathsf{Ext}_{0}$ .

Let $Y_{\mathsf{BExt}}$ be a fresh seed of length $d_{t}$ . With the desired upper bound on the seed length $d$ from the lemma’s statement in mind, we note that

d_{t}\leq 2m_{t}+4\log(\ell_{t}/\varepsilon_{0})+8\leq 2\log u\cdot\log(\ell_{0}/\varepsilon_{0})+4\log(\ell_{0}/\varepsilon_{0})\leq 6\log u\cdot\log(n/\varepsilon_{0}),

(8)

since $\ell_{0}\leq k\leq n$ . By Lemma 2.23, we get that

Y_{\mathsf{BExt}}\circ\mathsf{BExt}(Z,Y_{\mathsf{BExt}})\approx_{\varepsilon_{\mathsf{block}}}Y_{\mathsf{BExt}}\circ\mathsf{BExt}(Z^{\prime},Y_{\mathsf{BExt}})\approx_{(t+1)\varepsilon_{0}}U_{d_{t}+m_{0}}.

Applying the triangle inequality, we conclude that

Y_{\mathsf{BExt}}\circ\mathsf{BExt}(Z,Y_{\mathsf{BExt}})\approx_{\varepsilon_{\mathsf{block}}+(t+1)\varepsilon_{0}}U_{d_{t}+m_{0}}.

We now define our final strong extractor $\mathsf{Ext}\colon\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m_{0}}$ (recall that we abbreviate $m_{0}=m_{0}(\ell_{0})$ ). Choose our overall seed to be $Y=Y_{\mathsf{Cond}}\circ Y_{0}\circ\cdots\circ Y_{t}\circ Y_{\mathsf{BExt}}$ and set $\mathsf{Ext}(X,Y)=\mathsf{BExt}(Z,Y_{\mathsf{BExt}})$ . By the discussion above, $\mathsf{Ext}$ is a strong $(k,\varepsilon)$ -extractor with error (recall that we abbreviate $\varepsilon_{0}=\varepsilon_{0}(\ell_{0})$ )

\varepsilon=2\varepsilon_{0}+\varepsilon_{\mathsf{block}}+(t+1)\varepsilon_{0}\leq(2t+4)(\varepsilon_{0}+2\cdot 2^{-c_{\mathsf{Samp}}k})

for a sufficiently large constant $C$ since $t=O(\log u)$ (where one of the $\varepsilon_{0}$ terms comes from fixing the seed in the condensing step of Item 1), and seed length

d=|Y_{\mathsf{Cond}}|+|Y_{\mathsf{BExt}}|+\sum_{i=0}^{t}|Y_{i}|\leq C_{\mathsf{Cond}}\log(n/\varepsilon_{0})+d_{t}+(t+1)C_{\mathsf{Samp}}\log(n^{\prime}/\varepsilon_{0})\leq C\log u\cdot\log(n/\varepsilon_{0})

provided that $C$ is large enough (again since $t=O(\log u)$ ), as desired. We used Equation 8 to bound $d_{t}$ and obtain the last inequality.

Time complexity.

It remains to analyze the time complexity of $\mathsf{Ext}$ . If $k\geq C\log^{2}(n/\varepsilon_{0})$ with $C$ a sufficiently large constant, then Item 1 takes time $\widetilde{O}(n)$ . Item 2 takes time $t\cdot\widetilde{O}(n)=\widetilde{O}(n)$ , since $t=O(\log u)=O(\log n)$ and each averaging sampler $\mathsf{Samp}_{i}$ is computable in time $\widetilde{O}(n)$ . Item 3 takes time $t\cdot\widetilde{O}(n)=\widetilde{O}(n)$ , since $\mathsf{Ext}_{0}$ and each $\mathsf{Ext}_{i}$ from Lemma 2.14 are computable in time $\widetilde{O}(n)$ . Therefore, $\mathsf{Ext}$ is computable in overall time $\widetilde{O}(n)$ in this case.

Otherwise, if $k<C\log^{2}(n/\varepsilon_{0})$ , then Item 1 takes time $\widetilde{O}(n)$ after a preprocessing step corresponding to finding a primitive element of $\mathds{F}_{q}$ with $q\leq\operatorname{poly}(n/\varepsilon_{0})$ . As discussed above, Item 2 takes time $\widetilde{O}(n)$ . Item 3 takes time $\widetilde{O}(\ell_{0})=\widetilde{O}(n)$ after a preprocessing step, and so $\mathsf{Ext}$ is computable in overall time $\widetilde{O}(n)$ after a preprocessing step. Moreover, if the preprocessing step for $\mathsf{Ext}_{0}$ consists in finding primitive elements of $j$ fields $\mathds{F}_{q}$ with orders $q\leq\operatorname{poly}(n/\varepsilon_{0})$ , then by the above the preprocessing step for $\mathsf{Ext}$ consists in finding primitive elements of $j+1$ fields $\mathds{F}_{q}$ with orders $q\leq\operatorname{poly}(n/\varepsilon_{0})$ . ∎

Denote by $\log^{(i)}$ the function that iteratively applies $\log$ a total of $i$ times (so $\log^{(1)}\!n=\log n$ , $\log^{(2)}\!n=\log\log n$ , and so on). Denote by $\log^{*}$ the iterated logarithm. Then, we have the following corollary.

Corollary 5.10.

There exists a constant $C>0$ such that the following holds. Let $n$ be any positive integer and $i$ any positive integer such that $\log^{(i)}\!n\geq 6C$ . Then, for any $k\leq n$ and any $\varepsilon\geq n^{3}\cdot 2^{-k/2^{C\cdot i}}$ there exists a strong $(k,\varepsilon)$ -seeded extractor $\mathsf{Ext}\colon\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m}$ with seed length $d\leq C\log^{(i)}\!n\cdot\log(n/\varepsilon)$ and output length $m\geq k/2^{C\cdot i}$ . Furthermore,

1.

if $k\geq 2^{C\cdot i}\cdot\log^{2}(n/\varepsilon)$ , then $\mathsf{Ext}$ is computable in time $\widetilde{O}(n)$ ;
2.

if $k<2^{C\cdot i}\cdot\log^{2}(n/\varepsilon)$ , then $\mathsf{Ext}$ is computable in time $\widetilde{O}(n)$ after a preprocessing step which corresponds to finding primitive elements of $i$ fields $\mathds{F}_{q}$ of orders $q\leq\operatorname{poly}(n/\varepsilon)$ powers of $2$ .

Consequently, if we choose $i$ to be the largest integer such that $\log^{(i)}\!n\geq 6C$ (which satisfies $i\leq\log^{*}\!n$ ) we get a strong $(k,\varepsilon)$ -seeded extractor $\mathsf{Ext}\colon\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m}$ with seed length $d\leq 6C^{2}\log(n/\varepsilon)$ and output length $m\geq k/2^{C\log^{*}\!n}$ for any error $\varepsilon\geq n^{3}\cdot 2^{-k/2^{C\log^{*}\!n}}$ . If $k\geq 2^{C\log^{*}\!n}\cdot\log^{2}(n/\varepsilon)$ , then $\mathsf{Ext}$ is computable in time $\widetilde{O}(n)$ . Otherwise, $\mathsf{Ext}$ is computable in time $\widetilde{O}(n)$ after a preprocessing step which corresponds to finding primitive elements of $i\leq\log^{*}\!n$ fields $\mathds{F}_{q}$ of orders $q\leq\operatorname{poly}(n/\varepsilon)$ .

Proof.

We iteratively apply Lemma 5.9 $i$ times. Let $c,C>0$ be the constants guaranteed by Lemma 5.9. For the first application of the lemma, we take $\mathsf{Ext}_{0}\colon\{0,1\}^{n}\times\{0,1\}^{d_{0}}\to\{0,1\}^{m_{0}}$ to be the strong $(k_{0}=0.7n,\varepsilon_{0})$ extractor from Lemma 2.14 with $m_{0}=k_{0}/20$ and $\varepsilon_{0}\geq 2^{-ck_{0}/100}$ to be defined later. The corresponding seed length is $d_{0}\leq 2m_{0}+4\log(n/\varepsilon_{0})+4$ , which satisfies $d_{0}\leq k_{0}$ , and so the initial value of $u$ is $u_{0}=d_{0}/\log(n/\varepsilon_{0})\leq k_{0}$ . Denote by $\mathsf{Ext}_{1}$ the resulting strong seeded extractor. In the second application of Lemma 5.9, we instantiate $\mathsf{Ext}_{0}$ with $\mathsf{Ext}_{1}$ instead to obtain a new strong seeded extractor $\mathsf{Ext}_{2}$ , and so on. For each $j\in[i]$ , we obtain a family of strong $(k,\varepsilon_{j})$ -seeded extractors $\mathsf{Ext}_{j}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d_{j}}\to\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{m_{j}}$ parameterized by $k$ with output length $m_{j}=m_{j-1}(ck)$ , error

\varepsilon_{j}=C\log u_{j-1}\cdot\varepsilon_{j-1}(ck)

and seed length

\displaystyle d_{j}=C\log u_{j-1}\cdot\log(n/\varepsilon_{j-1}(ck))=C\log u_{j-1}\cdot\log\mathopen{}\mathclose{{}\left(\frac{n\cdot C\log u_{j-1}}{\varepsilon_{j}}}\right),

where

	$\displaystyle u_{j}$	$\displaystyle=\frac{d_{j}}{\log(n/\varepsilon_{j})}$
		$\displaystyle=C\log u_{j-1}\cdot\mathopen{}\mathclose{{}\left(1+\frac{\log C}{\log(n/\varepsilon_{j})}+\frac{\log\log u_{j-1}}{\log(n/\varepsilon_{j})}}\right)$
		$\displaystyle\leq C\log u_{j-1}\cdot\mathopen{}\mathclose{{}\left(1+\frac{\log C}{\log n}+\frac{\log\log u_{j-1}}{\log n}}\right)$
		$\displaystyle\leq 3C\log u_{j-1}.$

The last inequality uses the fact that $u_{j-1}\leq u_{0}\leq n$ for all $j$ .

Recall that from the corollary statement that $i$ is such that $\log^{(i)}\!n\geq 6C$ . We show by induction that $u_{j}\leq 3C\log^{(j)}n+3C\log(6C)$ for all $j=0,\dots,i$ . This is immediate for the base case $j=0$ , since $u_{0}\leq k_{0}\leq n$ . For the induction step, note that

u_{j+1}\leq 3C\log u_{j}\leq 3C\log(3C\log^{(j)}n+3C\log(6C))\\ \leq 3C\log(2\cdot 3C\log^{(j)}n)=3C\log^{(j+1)}n+3C\log(6C),

as desired. This implies that

d_{j}=u_{j}\cdot\log(n/\varepsilon_{j})\leq 6C\log^{(j)}n\cdot\log(n/\varepsilon_{j})

and

\varepsilon_{j}=C\log u_{j-1}\cdot\varepsilon_{j-1}(ck)\leq(6C)^{j}\mathopen{}\mathclose{{}\left(\prod_{j^{\prime}=0}^{j-1}\log^{(j^{\prime})}n}\right)\cdot\varepsilon_{0}(c^{j}k)

for all $j\in[i]$ . We may assume that $C$ is large enough that $\log a\leq\sqrt{a}$ for all $a\geq C$ , in which case $\prod_{j^{\prime}=0}^{j-1}\log^{(j^{\prime})}n\leq\prod_{j^{\prime}=0}^{j-1}n^{2^{-j^{\prime}}}\leq n^{2}$ since $\log^{(j^{\prime})}n\geq C$ for all $j^{\prime}\leq i$ by hypothesis. Therefore, we obtain final output length

m_{i}=m_{0}(c^{i}k)=k/2^{O(i)},

final error $\varepsilon_{i}$ satisfying

\varepsilon_{0}(ck)\leq\varepsilon_{i}\leq(6C)^{i}\cdot n^{2}\cdot\varepsilon_{0}(c^{i}k)\leq n^{3}\cdot\varepsilon_{0}(c^{i}k),

where the last inequality uses that $\log^{(i)}\!n\geq 6C$ , and final seed length

d_{i}\leq 6C\log^{(i)}\!n\cdot\log(n/\varepsilon_{i}).

We now instantiate $\varepsilon_{0}(c^{i}k)=\varepsilon/n^{3}$ . Note that $\varepsilon_{0}(c^{i}k)\geq 2^{-0.7c^{i+1}k/100}$ as required for the choice of $\mathsf{Ext}_{0}$ above so long as $\varepsilon\geq n^{3}\cdot 2^{-0.7c^{i+1}k}$ , which holds by the corollary’s hypothesis if $C$ is a large enough constant. With this choice of $\varepsilon_{0}(c^{i}k)$ we get final error $\varepsilon_{i}\leq n^{3}\cdot\varepsilon_{0}(c^{i}k)=\varepsilon$ . In fact, we can make $\varepsilon_{i}$ larger so that $\varepsilon_{i}=\varepsilon$ , in which case the final seed length satisfies

d_{i}\leq 6C\log^{(i)}\!n\cdot\log(n/\varepsilon),

as desired.

Time complexity.

Finally, we discuss the time complexity of $\mathsf{Ext}$ . Note that the initial choice for $\mathsf{Ext}_{0}$ is computable in time $\widetilde{O}(n_{0})$ . Therefore, if $k\geq 2^{C\cdot i}\log^{2}(n/\varepsilon)$ for a sufficiently large constant $C>0$ , then the conditions of Item 1 of Lemma 5.9 are satisfied for all $i$ applications of this lemma, and so $\mathsf{Ext}$ will be computable in time $\widetilde{O}(n)$ . Otherwise, the condition in Item 1 holds and so $\mathsf{Ext}$ is computable in time $\widetilde{O}(n)$ after a preprocessing step, since we always have $u\leq n$ in each application of the lemma. By Lemma 5.9, the preprocessing amounts to finding primitive elements of $i$ fields $\mathds{F}_{q}$ with orders $q\leq\operatorname{poly}(n/\varepsilon_{0})=\operatorname{poly}(n/\varepsilon)$ . ∎

To obtain our final theorem, we use block source extraction to increase the output length of the extractor from Corollary 5.10, following a strategy of Zuckerman [Zuc97].

Theorem 5.11.

There exist constants $c,C>0$ such that the following holds. For any integers $n$ and $k\leq n$ and any $\varepsilon\geq Cn^{3}\cdot 2^{-k/\log k}$ there exists a strong $(k,\varepsilon)$ -seeded extractor $\mathsf{Ext}\colon\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m}$ with seed length $d\leq C\log(n/\varepsilon)$ and output length $m\geq ck$ . Furthermore,

1.

if $k\geq 2^{C\log^{*}\!n}\cdot\log^{2}(n/\varepsilon)$ , then $\mathsf{Ext}$ is computable in time $\widetilde{O}(n)$ ;
2.

if $k<2^{C\log^{*}\!n}\cdot\log^{2}(n/\varepsilon)$ , then $\mathsf{Ext}$ is computable in time $\widetilde{O}(n)$ after a preprocessing step which corresponds to finding $\log^{*}n$ primitive elements of fields $\mathds{F}_{q}$ of orders $q\leq\operatorname{poly}(n/\varepsilon)$ powers of $2$ .

Proof.

Define $\varepsilon^{\prime}=\varepsilon/6$ and let $X$ be an arbitrary $(n,k)$ -source. The extractor $\mathsf{Ext}$ behaves as follows on input $X$ :

1.

Apply a strong $(k,k^{\prime},(\varepsilon^{\prime})^{2})$ -condenser $\mathsf{Cond}\colon\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n}\times\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{d_{\mathsf{Cond}}}\to\mathopen{}\mathclose{{}\left\{{0,1}}\right\}^{n^{\prime}}$ to $X$ , with output min-entropy rate $k^{\prime}\geq 0.95n^{\prime}$ and seed length $d_{\mathsf{Cond}}=C_{\mathsf{Cond}}\log(n/\varepsilon^{\prime})$ . If $k\geq 2^{C\log^{*}\!n}\cdot\log^{2}(n/\varepsilon)$ , we instantiate $\mathsf{Cond}$ with the lossless KT strong $(k,k^{\prime},\varepsilon^{\prime})$ -condenser (Theorem 3.10). Otherwise, we instantiate $\mathsf{Cond}$ with the lossy RS strong $(k,k^{\prime},\varepsilon^{\prime})$ -condenser (Theorem 3.11). By the second part of either Theorem 3.10 or Theorem 3.11, we get that with probability at least $1-\varepsilon^{\prime}$ over the choice of the seed $y$ we obtain an output $X^{\prime}$ that is $\varepsilon^{\prime}$ -close to an $(n^{\prime},k^{\prime})$ -source with $k^{\prime}\geq 0.95n^{\prime}$ . As in previous arguments, we work under such a good fixing of $y$ from here onwards and account for the probability $\varepsilon^{\prime}$ of selecting a bad seed in the final extractor error later on.
2.

Write $X^{\prime}=X_{1}\circ X_{2}$ with $|X_{1}|=|X_{2}|=n^{\prime}/2$ . Choose the constant $c>0$ in the theorem statement small enough so that $\log(1/\varepsilon^{\prime})\leq\log(1/\varepsilon)+3\leq ck+3\leq 0.05k$ , which means that $n^{\prime}/2-0.05k-\log(1/\varepsilon^{\prime})\geq 0.4n^{\prime}$ . Then, combining Item 1 with Lemma 2.24, (instantiated with $t=2$ , $\Delta=0.05k$ , and $\varepsilon=\varepsilon^{\prime}$ ) via the triangle inequality, $X^{\prime}$ is $3\varepsilon^{\prime}$ -close to an $((n^{\prime}/2,n^{\prime}/2),0.8)$ -block source.

Apply block source extraction to $X_{1}\circ X_{2}$ . More precisely, let $\mathsf{Ext}_{1}\colon\{0,1\}^{n_{1}}\times\{0,1\}^{d_{1}}\to\{0,1\}^{m_{1}}$ be the strong $(k_{1}=0.8n_{1},\varepsilon_{1})$ -seeded extractor from Corollary 5.10 instantiated with $i=2$ and $n_{1}=n^{\prime}/2$ , which yields $\varepsilon_{1}=\varepsilon\geq n_{1}^{3}\cdot 2^{-c_{1}k_{1}}$ , $d_{1}\leq C_{1}\log\log k_{1}\cdot\log(n^{\prime}/\varepsilon)$ , and $m_{1}\geq c_{1}k_{1}$ , for constants $c_{1},C_{1}>0$ guaranteed by Corollary 5.10. Furthermore, let $\mathsf{Ext}_{2}\colon\{0,1\}^{n_{2}}\times\{0,1\}^{d_{2}}\to\{0,1\}^{m_{2}}$ be the strong $(k_{2}=0.8n_{2},\varepsilon_{2})$ -seeded extractor from the “Consequently” part of Corollary 5.10 and $n_{2}=n^{\prime}/2$ , which yields $\varepsilon_{2}=n_{2}^{3}\cdot 2^{-k_{2}/2^{C_{2}\log^{*}\!k_{2}}}$ , $d_{2}\leq C_{2}\log(n^{\prime}/\varepsilon)$ , and $m_{2}\geq k_{2}/2^{C_{2}\log^{*}\!k_{2}}$ , for a constant $C_{2}>0$ guaranteed by Corollary 5.10. This choice of parameters ensures that $m_{2}\geq d_{1}$ . Indeed, since $k\geq k_{1}=k_{2}\geq 0.4n^{\prime}$ , to see that $m_{2}\geq d_{1}$ it suffices to check that

\frac{0.4k}{2^{C_{2}\log^{*}\!k}}\geq d_{1}=C_{1}\log\log k\cdot\log(n^{\prime}/\varepsilon_{1}).

Since $\varepsilon_{1}=\varepsilon^{\prime}=\varepsilon/5$ and $\log(n^{\prime}/\varepsilon_{1})=O(\log(k/\varepsilon^{\prime}))=O(\log k+k/\log k)=O(k/\log k)$ , it is enough that

k\geq C^{\prime}_{1}\cdot 2^{C_{2}\log^{*}\!k}\log\log k\cdot\frac{k}{\log k}

for a sufficiently large constant $C^{\prime}_{1}>0$ , which holds whenever $k$ is larger than some appropriate absolute constant. Instantiating Lemma 2.23 with $\mathsf{Ext}_{1}$ and $\mathsf{Ext}_{2}$ above yields a strong $(k_{1}=0.8n_{1},k_{2}=0.8n_{2},\varepsilon_{1}+\varepsilon_{2})$ -block-source extractor $\mathsf{BExt}\colon\{0,1\}^{n_{1}}\times\{0,1\}^{n_{2}}\times\{0,1\}^{d_{2}}\to\{0,1\}^{m_{1}}$ .

Since $X^{\prime}$ is $3\varepsilon^{\prime}$ -close to an $(n_{1},n_{2},0.8)$ -block source, we conclude that

Y_{\mathsf{BExt}}\circ\mathsf{BExt}(X^{\prime},Y_{\mathsf{BExt}})\approx_{3\varepsilon^{\prime}+\varepsilon_{1}+\varepsilon_{2}}U_{d_{2}+m_{1}}.

(9)

We define the output of our final strong extractor $\mathsf{Ext}\colon\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m_{1}}$ to be $\mathsf{BExt}(X^{\prime},Y_{\mathsf{BExt}})$ . Since $\varepsilon_{1},\varepsilon_{2}\leq\varepsilon^{\prime}$ , Equation 9 implies that

Y_{\mathsf{Cond}}\circ Y_{\mathsf{BExt}}\circ\mathsf{Ext}(X,Y_{\mathsf{Cond}}\circ Y_{\mathsf{BExt}})\approx_{5\varepsilon^{\prime}}U_{d+m_{1}}.

This means that $\mathsf{Ext}$ is a strong $(k,\varepsilon^{\prime}+5\varepsilon^{\prime}=\varepsilon)$ -seeded extractor with seed length $d=|Y_{\mathsf{Cond}}|+|Y_{\mathsf{BExt}}|=O(\log(n/\varepsilon))$ and output length $m_{1}\geq c_{1}k_{1}\geq c^{\prime}_{1}k$ for an absolute constant $c^{\prime}_{1}>0$ , where one of the $\varepsilon^{\prime}$ terms in the error comes from fixing the seed in the condensing step of Item 1.

Time complexity.

Finally, we analyze the time complexity of $\mathsf{Ext}$ . If $k\geq 2^{C\log^{*}\!n}\cdot\log^{2}(n/\varepsilon)$ , then Item 1 runs in time $\widetilde{O}(n)$ . In Item 3, $\mathsf{Ext}_{1}$ and $\mathsf{Ext}_{2}$ are both computable in time $\widetilde{O}(n)$ under this lower bound on $k$ , and thus so is $\mathsf{BExt}$ . We conclude that $\mathsf{Ext}$ runs in time $\widetilde{O}(n)$ . Otherwise, if $k<2^{C\log^{*}\!n}\cdot\log^{2}(n/\varepsilon)$ , then Item 1 runs in time $\widetilde{O}(n)$ after a preprocessing step, and $\mathsf{Ext}_{1}$ and $\mathsf{Ext}_{2}$ in Item 3 run in time $\widetilde{O}(n)$ after a preprocessing step. Therefore, overall, $\mathsf{Ext}$ runs in time $\widetilde{O}(n)$ after a preprocessing step. ∎

References

[ACG⁺22] Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, and João Ribeiro. Low-degree polynomials extract from local sources. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 10:1–10:20, 2022.
[AGHP92] Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple constructions of almost $k$ -wise independent random variables. Random Structures & Algorithms, 3(3):289–304, 1992.
[AGMR24] Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, and João Ribeiro. Low-degree polynomials are good extractors. ECCC, 2024. https://eccc.weizmann.ac.il/report/2024/093/ (manuscript).
[Alo21] Noga Alon. Explicit expanders of every degree and size. Combinatorica, pages 1–17, 2021.
[BBCM95] Charles H. Bennett, Gilles Brassard, Claude Crépeau, and Ueli M. Maurer. Generalized privacy amplification. IEEE Transactions on Information Theory, 41(6):1915–1923, 1995.
[BG13] Andrej Bogdanov and Siyao Guo. Sparse extractor families for all the entropy. In Innovations in Theoretical Computer Science (ITCS), pages 553–560. ACM, 2013.
[BM74] Allan Borodin and Robert Moenck. Fast modular transforms. Journal of Computer and System Sciences, 8(3):366–386, 1974.
[Bog12] Andrej Bogdanov. Topics in (and out) the theory of computing: Lecture notes. https://andrejb.net/csc5060/notes/12L12.pdf, 2012. [Online; accessed October 2024].
[BRST02] Ziv Bar-Yossef, Omer Reingold, Ronen Shaltiel, and Luca Trevisan. Streaming computation of combinatorial objects. In Annual Conference on Computational Complexity (CCC), pages 165–174. IEEE, 2002.
[CG88] Benny Chor and Oded Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing, 17(2):230–261, 1988.
[CL18] Kuan Cheng and Xin Li. Randomness extraction in AC0 and with small locality. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 37:1–37:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
[CRSW13] L. Elisa Celis, Omer Reingold, Gil Segev, and Udi Wieder. Balls and bins: Smaller hash families and faster evaluation. SIAM Journal on Computing, 42(3):1030–1050, 2013.
[CT65] James W. Cooley and John W. Tukey. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 19(90):297–301, 1965.
[CW24] Kuan Cheng and Ruiyang Wu. Randomness extractors in AC⁰ and NC¹: Optimal up to constant factors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 69:1–69:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
[DD06] Jacques Dubrois and Jean-Guillaume Dumas. Efficient polynomial time algorithms computing industrial-strength primitive roots. Information Processing Letters, 97(2):41–45, 2006.
[DKSS13] Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan. Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. SIAM Journal on Computing, 42(6):2305–2328, 2013.
[DMOZ22] Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman. Nearly optimal pseudorandomness from hardness. J. ACM, 69(6), November 2022.
[DORS08] Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM Journal on Computing, 38(1):97–139, 2008.
[DPVR12] Anindya De, Christopher Portmann, Thomas Vidick, and Renato Renner. Trevisan’s extractor in the presence of quantum side information. SIAM Journal on Computing, 41(4):915–940, 2012.
[DT23] Dean Doron and Roei Tell. Derandomization with minimal memory footprint. In Computational Complexity Conference (CCC), pages 11:1–11:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
[Für09] Martin Fürer. Faster integer multiplication. SIAM Journal on Computing, 39(3):979–1005, 2009.
[FWE⁺23] Cameron Foreman, Sherilyn Wright, Alec Edgington, Mario Berta, and Florian J. Curchod. Practical randomness amplification and privatisation with implementations on quantum computers. Quantum, 7:969, March 2023.
[FYEC24] Cameron Foreman, Richie Yeung, Alec Edgington, and Florian J. Curchod. Cryptomite: A versatile and user-friendly library of randomness extractors. arXiv e-prints, February 2024. https://arxiv.org/abs/2402.09481.
[GGH⁺24] Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, and Chao Yan. Hilbert functions and low-degree randomness extractors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 41:1–41:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
[Gil98] David Gillman. A Chernoff bound for random walks on expander graphs. SIAM Journal on Computing, 27(4):1203–1220, 1998.
[GUV09] Venkatesan Guruswami, Christopher Umans, and Salil Vadhan. Unbalanced expanders and randomness extractors from Parvaresh–Vardy codes. J. ACM, 56(4), jul 2009.
[GVW15] Oded Goldreich, Emanuele Viola, and Avi Wigderson. On randomness extraction in AC0. In Conference on Computational Complexity (CCC), page 601–668. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015.
[Hea08] Alexander D. Healy. Randomness-efficient sampling within $\textnormal{NC}^{1}$ . Computational Complexity, 17:3–37, 2008.
[HH15] Jan Hązła and Thomas Holenstein. Upper tail estimates with combinatorial proofs. In Symposium on Theoretical Aspects of Computer Science (STACS). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015.
[HIV22] Xuangui Huang, Peter Ivanov, and Emanuele Viola. Affine extractors and AC0-parity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 9:1–9:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
[HT16] Masahito Hayashi and Toyohiro Tsurumaru. More efficient privacy amplification with less random seeds via dual universal hash function. IEEE Transactions on Information Theory, 62(4):2213–2232, 2016.
[HV06] Alexander Healy and Emanuele Viola. Constant-depth circuits for arithmetic in finite fields of characteristic two. In Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 672–683. Springer, 2006.
[HvdH19] David Harvey and Joris van der Hoeven. Faster polynomial multiplication over finite fields using cyclotomic coefficient rings. Journal of Complexity, 54:101404, 2019.
[HvdH21] David Harvey and Joris van der Hoeven. Integer multiplication in time $O(n\mathrm{log}\,n)$ . Annals of Mathematics, 193(2):563 – 617, 2021.
[HvdH22] David Harvey and Joris van der Hoeven. Polynomial multiplication over finite fields in time $O(n\mathrm{log}\,n)$ . J. ACM, 69(2):1–40, 2022.
[Jus72] Jørn Justesen. Class of constructive asymptotically good algebraic codes. IEEE Transactions on Information Theory, 18(5):652–656, 1972.
[KT22] Itay Kalev and Amnon Ta-Shma. Unbalanced expanders from multiplicity codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 12:1–12:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
[Li15] Xin Li. Non-malleable condensers for arbitrary min-entropy, and almost optimal protocols for privacy amplification. In Theory of Cryptography Conference (TCC), pages 502–531. Springer, 2015.
[LRVW03] Chi-Jen Lu, Omer Reingold, Salil Vadhan, and Avi Wigderson. Extractors: Optimal up to constant factors. In Symposium on Theory of Computing (STOC), pages 602–611. ACM, 2003.
[Lu02] Chi-Jen Lu. Hyper-encryption against space-bounded adversaries from on-line strong extractors. In Advances in Cryptology — CRYPTO, pages 257–271. Springer, 2002.
[MPS12] Wolfgang Mauerer, Christopher Portmann, and Volkher B. Scholz. A modular framework for randomness extraction based on Trevisan’s construction. arXiv e-prints, December 2012. https://arxiv.org/abs/1212.0520.
[MRRR14] Raghu Meka, Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Fast pseudorandomness for independence and load balancing. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 859–870. Springer, 2014.
[MW97] Ueli Maurer and Stefan Wolf. Privacy amplification secure against active adversaries. In Advances in Cryptology — CRYPTO, pages 307–321. Springer, 1997.
[NN90] Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. In Symposium on Theory of Computing (STOC), pages 213–223. ACM, 1990.
[NT99] Noam Nisan and Amnon Ta-Shma. Extracting randomness: A survey and new constructions. Journal of Computer and System Sciences, 58(1):148–173, 1999.
[NZ96] Noam Nisan and David Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43–52, 1996.
[Rao07] Anup Rao. An exposition of Bourgain’s 2-source extractor. ECCC, 2007. https://eccc.weizmann.ac.il//report/2007/034/ (manuscript).
[RRV02] 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.
[RSW06] Omer Reingold, Ronen Shaltiel, and Avi Wigderson. Extracting randomness via repeated condensing. SIAM Journal on Computing, 35(5):1185–1209, 2006.
[RT00] Jaikumar Radhakrishnan and Amnon Ta-Shma. Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM Journal on Discrete Mathematics, 13(1):2–24, 2000.
[Sch77] Arnold Schönhage. Schnelle multiplikation von polynomen über körpern der charakteristik 2. Acta Informatica, 7(4):395–398, 1977.
[Sho90] Victor Shoup. Searching for primitive roots in finite fields. In Symposium on Theory of Computing (STOC), pages 546–554. ACM, 1990.
[Shp92] Igor E. Shparlinski. On primitive elements in finite fields and on elliptic curves. Mathematics of the USSR-Sbornik, 71(1):41, feb 1992.
[Spi96] Daniel A. Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory, 42(6):1723–1731, 1996.
[SU05] Ronen Shaltiel and Christopher Umans. Simple extractors for all min-entropies and a new pseudorandom generator. J. ACM, 52(2):172–216, 2005.
[SZ99] Aravind Srinivasan and David Zuckerman. Computing with very weak random sources. SIAM Journal on Computing, 28(4):1433–1459, 1999.
[Ta-17] Amnon Ta-Shma. Explicit, almost optimal, epsilon-balanced codes. In Symposium on Theory of Computing (STOC), page 238–251. ACM, 2017.
[Tre01] Luca Trevisan. Extractors and pseudorandom generators. J. ACM, 48(4):860–879, jul 2001.
[TSSR11] Marco Tomamichel, Christian Schaffner, Adam Smith, and Renato Renner. Leftover hashing against quantum side information. IEEE Transactions on Information Theory, 57(8):5524–5535, 2011.
[TU12] Amnon Ta-Shma and Christopher Umans. Better condensers and new extractors from Parvaresh-Vardy codes. In Conference on Computational Complexity (CCC), pages 309–315. IEEE, 2012.
[TZS06] Amnon Ta-Shma, David Zuckerman, and Shmuel Safra. Extractors from Reed–Muller codes. Journal of Computer and System Sciences, 72(5):786–812, 2006.
[Vad04] Salil Vadhan. Constructing locally computable extractors and cryptosystems in the bounded-storage model. Journal of Cryptology, 17:43–77, 2004.
[Vad12] Salil Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1–3):1–336, 2012.
[vzGG13] Joachim von zur Gathen and Jürgen Gerhard. Modern Computer Algebra. Cambridge University Press, 2013.
[WZ99] Avi Wigderson and David Zuckerman. Expanders that beat the eigenvalue bound: Explicit construction and applications. Combinatorica, 19(1):125–138, 1999.
[XZ24] Zhiyang Xun and David Zuckerman. Near-optimal averaging samplers. ECCC, 2024. https://eccc.weizmann.ac.il/report/2024/097/ (manuscript).
[Zuc97] David Zuckerman. Randomness-optimal oblivious sampling. Random Structures & Algorithms, 11(4):345–367, 1997.

Nearly-Linear Time Seeded Extractors with Short Seeds

Abstract

1 Introduction

1.1 Our Contributions

Seeded extractors with order-optimal seed length and large output length.

Theorem 1.

A new non-recursive construction.

Faster instantiations of Trevisan’s extractor.

Theorem 2.

1.2 Other Related Work

1.3 Technical Overview

Observations about nearly-linear time condensers.

The “ideal” approach to seeded extraction from high min-entropy sources.

Getting around the limitation of the ideal approach.

1.4 Future Work

1.5 Acknowledgements

2 Preliminaries

2.1 Notation

2.2 Model of Computation

2.3 Fast Finite Fields Operations

Lemma 2.1 ([BM74], see also [vzGG13, Chapter 10]).

2.4 Statistical Distance, Entropy

Definition 2.2 (statistical distance).

Definition 2.3 (min-entropy).

Definition 2.4 (average conditional min-entropy).

Lemma 2.5 (see, e.g., [DORS08]).

Lemma 2.6 (see, e.g., [MW97]).

Definition 2.7 (smooth min-entropy).

2.5 Extractors and Condensers

Definition 2.8 ((n,k)(n,k)-source).

Definition 2.9 (block source).

Definition 2.10 (seeded extractor).

Remark 2.11.

Definition 2.12 (condenser).

Definition 2.13 (block source extractor).

Lemma 2.14 (fast hash-based extractors [TSSR11, Theorem 10], adapted. See also [HT16, Table I]).

2.6 Averaging Samplers

Definition 2.15 (averaging sampler).

Lemma 2.16 ([Vad04, Lemma 6.2]).

The “expander random walk” sampler.

Lemma 2.17 ([Alo21, Theorem 1.2], adapted).

Corollary 2.18.

Lemma 2.19 ([Vad04, Lemma 8.2], appropriately instantiated).

Lemma 2.20 ([Vad04, Lemma 8.3]).

Lemma 2.21 ([Vad04, Lemma 8.4], with additional complexity claim).

2.7 Standard Composition Techniques for Extractors

Lemma 2.22 (boosting the output length [WZ99, RRV02]).

Lemma 2.23 (block source extraction).

Lemma 2.24 ([GUV09, Corollary 4.16]).

Lemma 2.25 (fast extractors with seed shorter than output [GUV09, Lemma 4.11]).

Proof.

Lemma 2.26.

3 Additional Building Blocks

3.1 Fast Generation of Small-Bias Sets

Lemma 3.1 (RWs amplify bias [Ta-17]101010The argument for t=2t=2 was suggested already by Rozenman and Wigderson (see [Bog12]).).

Lemma 3.2 ([Jus72]).

Proof.

Corollary 3.3.

Proof.

Remark 3.4.

3.2 A Sampler from Bounded Independence

Lemma 3.5.

Proof.

Claim 3.6.

Proof.

Lemma 3.7 ([XZ24]).

Lemma 3.8.

Proof.

Lemma 3.9.

3.3 Nearly-Linear Time Condensers

Theorem 3.10 (the lossless KT condenser, [KT22]).

Proof.

Theorem 3.11 (the lossy RS condenser, [GUV09]).

Proof.

4 A Faster Instantiation of Trevisan’s Extractor

Definition 4.1 (weak design).

Theorem 4.2.

Proof.

Claim 4.3 ([FYEC24], Section A.5).

Corollary 4.4.

Definition 2.8 ( $(n,k)$ -source).

Lemma 3.1 (RWs amplify bias [Ta-17]¹⁰¹⁰10The argument for $t=2$ was suggested already by Rozenman and Wigderson (see [Bog12]).).