Multiplicative Extractors for Samplable Distributions

Shaltiel, Ronen

doi:10.4230/LIPIcs.CCC.2025.22

Multiplicative Extractors for Samplable Distributions¹¹1In memory of Luca Trevisan.

Ronen Shaltiel University of Haifa, Israel

Abstract

Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions as a way to extract random keys for cryptographic protocols from weak sources of randomness. They showed that under a very strong complexity theoretic assumption, there exists a constant $\alpha>0$ such that for every constant $c\geq 1$ , there is an extractor $\mathsf{Ext}:\{0,1\}^{n}\to\{0,1\}^{\Omega(n)}$ , such that for every distribution $X$ over $\{0,1\}^{n}$ with $H_{\infty}(X)\geq(1-\alpha)\cdot n$ that is samplable by size $n^{c}$ circuits, the distribution $\mathsf{Ext}(X)$ is $\epsilon$ -close to uniform for $\epsilon=\frac{1}{n^{c}}$ , and furthermore, $\mathsf{Ext}$ is computable in time ${\mathsf{poly}}(n^{c})$ .

Recently, Ball, Goldin, Dachman-Soled and Mutreja (FOCS 2023) gave a substantial improvement, and achieved the same conclusion under the weaker (and by now standard) assumption that there exists a constant $\beta>0$ , and a problem in ${\mathsf{E}}={\mathsf{DTIME}}(2^{O(n)})$ that requires size $2^{\beta n}$ nondeterministic circuits.
In this paper we give an alternative proof of this result with the following advantages:

$\blacksquare$

Our extractors have “multiplicative error”: It is guaranteed that for every event $A\subseteq\{0,1\}^{m}$ , $\Pr[\mathsf{Ext}(X)\in A]\leq(1+\epsilon)\cdot\Pr[U_{m}\in A]$ . (This should be contrasted with the standard notion that only implies $\Pr[\mathsf{Ext}(X)\in A]\leq\epsilon+\Pr[U_{m}\in A]$ ).

Consequently, unlike the (additive) extractors of Trevisan and Vadhan, and Ball et al., our multiplicative extractors guarantee that in the application of selecting keys for cryptographic protocols, if when choosing a random key, the probability that an adversary can steal the honest party’s money is $n^{-\omega(1)}$ , then this also holds when using the output of the extractor as a key.

Our multiplicative extractors are a key component in the recent subsequent work of Ball, Shaltiel and Silbak (STOC 2025) that constructs extractors for samplable distributions with low min-entropy. This is another demonstration of the usefulness of multiplicative extractors.

We remark that a related notion of multiplicative extractors was defined by Applebaum, Artemenko, Shaltiel and Yang (CCC 2015) who showed that black-box techniques cannot yield extractors with additive error $\epsilon=n^{-\omega(1)}$ , under the assumption assumed by Ball et al. or Trevisan and Vadhan. This motivated Applebaum et al. to consider multiplicative extractors, and they gave constructions based on the original hardness assumption of Trevisan and Vadhan.
$\blacksquare$

Our proof is significantly simpler, and more modular than that of Ball et al. (and arguably also than that of Trevisan and Vadhan). A key observation is that the extractors that we want to construct, easily follow from a seed-extending pseudorandom generator against nondeterministic circuits (with the twist that the error is measured multiplicatively, as in computational differential privacy). We then proceed to construct such pseudorandom generators under the hardness assumption. This turns out to be easier (utilizing amongst other things, ideas by Trevisan and Vadhan, and by Ball et al.)

Trevisan and Vadhan also asked whether lower bounds against nondeterministic circuits are necessary to achieve extractors for samplable distributions. While we cannot answer this question, we show that the proof techniques used in our paper (as well as those used in previous work) produce extractors which imply seed-extending PRGs against nondeterministic circuits, which in turn imply lower bounds against nondeterministic circuits.

Keywords and phrases:

Randomness Extractors, Samplable Distributions, Hardness vsRandomness

Funding:

Ronen Shaltiel: Ronen Shaltiel was supported by ISF grant 1006/23 and by the European Union (ERC-2022-ADG) under grant agreement no.101097959 NFITSC.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Pseudorandomness and derandomization

Acknowledgements:

I want to thank Alon Dermer and anonymous referees for valuable comments a corrections.

DOI:

10.4230/LIPIcs.CCC.2025.22

Event:

40th Computational Complexity Conference (CCC 2025)

Editors:

Srikanth Srinivasan

Series and Publisher:

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

1 Introduction

1.1 Multiplicative Pseudorandomness

Pseudorandomness is a viewpoint that says that a distribution $Z$ over $\{0,1\}^{m}$ is “similar” to the uniform distribution $U_{m}$ from the point of view of a function $C:\{0,1\}^{m}\to\{0,1\}$ , if the quantities $p_{1}=\Pr[C(U_{m})=1]$ and $p_{2}=\Pr[C(Z)=1]$ are “similar”. Typically, this similarity is measured by choosing a parameter $0<\epsilon\leq 1$ and using the relation $\stackrel{{\scriptstyle ad}}{{\sim}}_{\epsilon}$ on $[0,1]$ defined as follows:

p_{1}\stackrel{{\scriptstyle ad}}{{\sim}}_{\epsilon}p_{2}\iff|p_{2}-p_{1}|\leq\epsilon,

We can generalize this approach to define pseudorandomness with respect to different relations.

Definition 1 (Pseudorandomness with respect to a relation).

Let $\sim$ be a relation on $[0,1]$ . Given a function $C:\{0,1\}^{m}\to\{0,1\}$ , a distribution $Z$ over $\{0,1\}^{m}$ is pseudorandom for $C$ with respect to $\sim$ , if

\Pr[C(U_{m})=1]\sim\Pr[C(Z)=1].

We will abbreviate “with respect to” as “w.r.t.” for brevity. Given a class $\mathcal{C}$ of functions $C:\{0,1\}^{m}\to\{0,1\}$ , we say that $Z$ is pseudorandom for $\mathcal{C}$ w.r.t. $\sim$ , if it is pseudorandom for every $C$ in $\mathcal{C}$ w.r.t. $\sim$ . $Z$ is close to uniform w.r.t. $\sim$ , if it is pseudorandom w.r.t. $\sim$ for the class of all boolean functions on $m$ bits.

The standard notion of $\epsilon$ -pseudorandomness is obtained when taking the relation $\stackrel{{\scriptstyle ad}}{{\sim}}_{\epsilon}$ . If the class $\mathcal{C}$ is closed under complement then the standard notion is also obtained when using the (one sided) relation

p_{1}\stackrel{{\scriptstyle a}}{{\sim}}_{\epsilon}p_{2}\iff p_{2}\leq p_{1}+\epsilon,

in which the absolute value is removed. The generalized formulation of Definition 1 allows other relations. This generality is used in differential privacy [16] that uses the following multiplicative relation:

p_{1}\stackrel{{\scriptstyle m}}{{\sim}}_{\epsilon}p_{2}\iff p_{2}\leq e^{% \epsilon}\cdot p_{1}.

Note that for $0\leq\epsilon\leq 1$ , $e^{\epsilon}=1+\Theta(\epsilon)$ , and therefore, pseudorandomness with respect to $\stackrel{{\scriptstyle m}}{{\sim}}_{\epsilon}$ , implies pseudorandomness with respect to $\stackrel{{\scriptstyle a}}{{\sim}}_{\epsilon}$ .²²2Pseudorandomness w.r.t. $\stackrel{{\scriptstyle m}}{{\sim}}_{\epsilon}$ makes sense also for $\epsilon\geq 1$ , and such choices are sometimes used in differential privacy. However, in this paper we will only consider the case where $0\leq\epsilon\leq 1$ , so that $1+\epsilon\leq e^{\epsilon}\leq 1+3\epsilon$ . The field of differential privacy also considers a generalization of $\stackrel{{\scriptstyle m}}{{\sim}}$ with two parameters: a “large” multiplicative $\epsilon$ , and a “small” additive $\delta$ , defined as follows:

p_{1}\stackrel{{\scriptstyle m}}{{\sim}}_{({\epsilon},{\delta})}p_{2}\iff p_{2% }\leq e^{\epsilon}\cdot p_{1}+\delta.

Note that $\stackrel{{\scriptstyle m}}{{\sim}}_{\epsilon}$ is obtained as $\stackrel{{\scriptstyle m}}{{\sim}}_{({\epsilon},{0})}$ , and pseudorandomness w.r.t. $\stackrel{{\scriptstyle m}}{{\sim}}_{({\epsilon},{\delta})}$ implies pseudorandomness w.r.t. $\stackrel{{\scriptstyle a}}{{\sim}}_{\epsilon+\delta}$ . We call the pseudorandomness obtained by these relations “multiplicative pseudorandomness”.³³3It is known that in the standard definition (w.r.t. $\stackrel{{\scriptstyle ad}}{{\sim}}_{\epsilon}$ or $\stackrel{{\scriptstyle a}}{{\sim}}_{\epsilon}$ ) $Z$ is $\epsilon$ -close to uniform iff $Z$ has statistical distance at most $\epsilon$ from $U_{m}$ . The multiplicative notion also has a natural information theoretic meaning, specifically note that $Z$ is close to uniform w.r.t. $\stackrel{{\scriptstyle m}}{{\sim}}_{\epsilon}$ iff for every $z\in\{0,1\}^{m}$ , $\Pr[Z=z]\leq e^{\epsilon}\cdot 2^{-m}$ . We can continue and define two fundamental objects of pseudorandomness (pseudorandom generators and seedless extractors) in this generalized way (which we will later use with the multiplicative relations).

Definition 2 (Pseudorandom generators and extractors w.r.t. a relation).

Let $\sim$ be a relation on $[0,1]$ .

$\blacksquare$

$G:\{0,1\}^{d}\to\{0,1\}^{m}$ is a PRG for a class $\mathcal{C}$ w.r.t. to $\sim$ (which we will also shorten to “ $\sim$ -PRG for $\mathcal{C}$ ”) if $G(U_{d})$ is pseudorandom for $\mathcal{C}$ w.r.t. $\sim$ . $G$ is seed-extending if the function $G^{\prime}(x)=(x,G(x))$ is a PRG for the considered class $\mathcal{C}$ , w.r.t. the considered relation $\sim$ .
$\blacksquare$

A function $\mathsf{Ext}:\{0,1\}^{n}\to\{0,1\}^{m}$ is a $(k,\sim)$ -extractor for a class $\mathcal{D}$ of distributions over $\{0,1\}^{n}$ , if for every distribution $X$ in $\mathcal{D}$ with $H_{\infty}(X)\geq k$ , the distribution $\mathsf{Ext}(X)$ is close to uniform w.r.t. $\sim$ .

Once again, the standard notions of extractors and pseudorandom generators are obtained for the relation $\stackrel{{\scriptstyle ad}}{{\sim}}_{\epsilon}$ (the same holds also for $\stackrel{{\scriptstyle a}}{{\sim}}_{\epsilon}$ for extractors, and also for PRGs in case $\mathcal{C}$ is closed under complement).

We will consider multiplicative variants of pseudorandom generators and seedless extractors. Some multiplicative versions of these objects (with a slightly different definition) have been considered before [1, 2, 27, 30] (and we elaborate on these works below). The main contribution of this paper is improved constructions, under weaker hardness assumptions.

A motivating example: using seedless extractors to select keys for cryptographic protocols

Consider a cryptographic protocol which is known to be secure when the key of an honest party is chosen according to $U_{m}$ . That is, the probability that an adversary can steal the honest party’s money is smaller than some “negligible” $\alpha>0$ . A signature application of seedless extractors is choosing keys for cryptographic protocols by extracting randomness from weak random sources. (Indeed, this was the original motivation of Trevisan and Vadhan [37], as seeded extractors do not apply for this application). When using a seedless extractor, the key will be “close to uniform” rather than “truly uniform”.

If the key is chosen according to a distribution that is $\epsilon$ -close to uniform (using to the standard notion) then we are only guaranteed that the adversary’s probability to cheat is smaller than $\alpha+\epsilon$ , which may be unacceptable if $\epsilon$ is “large” compared to $\alpha$ .

In contrast, if we replace the standard notion by the multiplicative notion (w.r.t. $\stackrel{{\scriptstyle m}}{{\sim}}_{\epsilon}$ ), then the probability that the adversary can cheat is bounded by $e^{\epsilon}\cdot\alpha\leq(1+3\epsilon)\cdot\alpha$ , which is still very small even for constant $\epsilon$ . (This argument applies to “unpredictability security games” where one bounds the probability that the adversary can cheat, but not necessarily to “indistinguishability security games” where one bounds the probability that the adversary can distinguish between two distributions. See e.g. [13] for a discussion). The same argument applies when using the multiplicative version with two parameters $\epsilon$ and $\delta$ (that is w.r.t. $\stackrel{{\scriptstyle m}}{{\sim}}_{({\epsilon},{\delta})}$ ), even if $\epsilon$ is large, as long as $\delta$ is sufficiently small and is comparable to $\alpha$ .

Indeed, this advantage of the multiplicative notion over the additive notion is the rational for using these multiplicative relations in differential privacy (where it is often impossible or expensive to obtain small $\epsilon$ ).

1.2 Extractors for Samplable Distributions

An influential paper by Trevisan and Vadhan [37] introduced the notion of (seedless) extractors for samplable distributions. Their goal was to identify a class of distributions that contains “sources of randomness that are available to computers” and allows seedless extractors that run in poly-time.

We say that a distribution $X$ over $\{0,1\}^{n}$ is sampled by a circuit $A:\{0,1\}^{r}\to\{0,1\}^{n}$ if $X=A(U_{r})$ (See more formal definition in Section 2.1). Trevisan and Vadhan considered extractors for distributions that are samplable by poly-size circuits, namely distributions samplable by circuits of size $n^{c}$ for some constant parameter $c$ . They showed that such extractors cannot run in time smaller than $n^{c}$ , and considered extractors that run in time ${\mathsf{poly}}(n^{c})$ . They showed that such extractors imply circuit lower bounds, and so, motivated by the hardness vs. randomness paradigm, they gave a conditional construction based on hardness assumptions.

Hardness assumptions against various types of nondeterministic circuits

We say that “ ${\mathsf{E}}$ is hard for exponential size circuits of some type”, if there exist a problem $L\in{\mathsf{E}}={\mathsf{DTIME}}(2^{O(n)})$ and a constant $\beta>0$ , such that for every sufficiently large $n$ , circuits of size $2^{\beta\cdot n}$ (of the specified type) fail to compute the characteristic function of $L$ on inputs of length $n$ . (See Section 2.3 for a more formal definition).

The assumptions that ${\mathsf{E}}$ is hard for exponential size (deterministic) circuits was used by the celebrated paper of Impagliazzo and Wigderson [24] to imply that $\text{BPP}=\text{P}$ . The stronger assumption that ${\mathsf{E}}$ is hard for exponential size nondeterministic circuits⁴⁴4A precise definition of nondeterministic circuits appears in Section 2.2., originated in works on hardness versus randomness for ${\mathsf{AM}}$ , and is now standard, and used in many results [4, 26, 28, 31, 9, 18, 21, 32, 33, 15, 1, 11, 2, 22, 14, 5, 12, 6, 7, 30]. It can be viewed as a scaled, nonuniform version of the widely believed assumption that ${\mathsf{EXP}}\neq{\mathsf{NP}}$ .

In their seminal paper on extractors for samplable distributions, Trevisan and Vadhan [37] introduced a version of the assumption for a stronger circuit class. A $\Sigma_{i}$ -circuit, is a circuit that in addition to the standard gates, is also allowed to use a special gate (with large fan-in) that solves the canonical complete language for the class $\Sigma_{i}^{{\mathsf{P}}}$ (the $i$ ’th level of the polynomial time hierarchy).⁵⁵5A $\Sigma_{i}$ -circuit is a nonuniform analogue of the class $P^{\Sigma_{i}^{{\mathsf{P}}}}$ that contains $\Sigma_{i}^{{\mathsf{P}}}$ , and recall that ${\mathsf{P}}=\Sigma_{0}^{{\mathsf{P}}}$ and ${\mathsf{NP}}=\Sigma_{1}^{{\mathsf{P}}}$ . See Section 2.2 for a formal definition. The extractor of Trevisan and Vadhan [37] relies on the extremely strong assumption that ${\mathsf{E}}$ is hard for exponential size $\Sigma_{5}$ -circuits.⁶⁶6We remark that following [37] there is some later work that relies on hardness for $\Sigma_{i}$ -circuits for $i>1$ [18, 3, 1, 2, 5, 8].

Previous work on extractors for samplable distributions

The main result of Trevisan and Vadhan [37] is that under a hardness assumption for $\Sigma_{5}$ -circuits, there is an extractor for distributions samplable by poly-size circuits with $k=n-\Delta$ , where $\Delta=\alpha n$ for some constant $\alpha>0$ . Below is a precise statement

Theorem 3 ([37]).

If ${\mathsf{E}}$ is hard for exponential size $\Sigma_{5}$ -circuits then there exists a constant $\alpha>0$ , such that for every constant $c>1$ , and for every sufficiently large $n$ , there is a function $\mathsf{Ext}:\{0,1\}^{n}\to\{0,1\}^{\alpha n}$ that is a $((1-\alpha)\cdot n,\stackrel{{\scriptstyle a}}{{\sim}}_{\epsilon})$ -extractor for distributions samplable by circuits of size $n^{c}$ , where $\epsilon=n^{-c}$ . Furthermore, $\mathsf{Ext}$ is computable in time ${\mathsf{poly}}(n^{c})$ .⁷⁷7The result stated in [37] gives an extractor with shorter output length of $m=\Theta(\log n)$ . Nevertheless, Applebaum et al. [1] observe that the result of [37] extends to larger output length, as stated in Theorem 3.

Note that this extractor only achieves an additive error of $\epsilon=n^{-c}$ . It is not known how to achieve a smaller error of $\epsilon=n^{-\omega(1)}$ . Moreover, Applebaum et al. [1] showed that “black-box techniques” cannot be used to achieve $\epsilon=n^{-\omega(1)}$ in Theorem 3, even if one replaces $\Sigma_{5}$ -circuits with $\Sigma_{i}$ -circuits for any number $i$ . We note that all previous results (including the one in this paper) use “black-box techniques”.

This led Applebaum et al. [1] to consider multiplicative extractors.⁸⁸8Applebaum et al. [1] use a more stringent definition of multiplicative extractors than the one we use here. In our terminology, they consider extractors w.r.t to the (double-sided) relation: $p_{1}\stackrel{{\scriptstyle md}}{{\sim}}_{\epsilon}p_{2}\iff p_{1}\stackrel{{% \scriptstyle m}}{{\sim}}_{\epsilon}p_{2}\mbox{ and }p_{2}\stackrel{{% \scriptstyle m}}{{\sim}}_{\epsilon}p_{1},$ which they call “relative-error extractors”. However, for the suggested applications of such extractors (for example, the motivating application of selecting keys for cryptographic protocols), extractors w.r.t. $\stackrel{{\scriptstyle m}}{{\sim}}_{\epsilon}$ suffice, and one does not benefit from considering extractors w.r.t. $\stackrel{{\scriptstyle md}}{{\sim}}_{\epsilon}$ . For this reason, we focus on extractors w.r.t. $\stackrel{{\scriptstyle m}}{{\sim}}_{\epsilon}$ in this paper. Jumping ahead, we remark that our technique is also applicable to construct extractors w.r.t. $\stackrel{{\scriptstyle md}}{{\sim}}_{\epsilon}$ , and we discuss the two notions in the full version. Applebaum et al. [1] showed that the construction and proof of Trevisan and Vadhan [37] can be extended to yield multiplicative extractors in Theorem 3. Recently, Ball et al. [6] improved upon Theorem 3 in two respects:

$\blacksquare$

The assumption was significantly improved to assuming that ${\mathsf{E}}$ is hard for exponential size nondeterministic circuits. This is a significant improvement as this assumption is weaker and more standard.
$\blacksquare$

The class of distributions was extended to include “samplable distributions with postselection”. (Ball et al. [6] also consider distributions samplable by quantum circuits with postselection, and we elaborate on such extractors in the full version). Samplable distributions with postselection is a richer class of distributions. More specifically, a distribution $X$ over $\{0,1\}^{n}$ is samplable with postselection by size $s$ circuits, if there is a size $s$ “sampling circuit” $A:\{0,1\}^{r}\to\{0,1\}^{n}$ and a size $s$ “postselection circuit” $P:\{0,1\}^{r}\to\{0,1\}$ , such that $X=(A(Y)|P(Y)=1)$ for $Y\leftarrow U_{r}$ . (See precise definition in Section 2.1). Loosely speaking, this allows $A$ to first sample $A(Y)$ , and then, “postselect” the obtained distribution, and condition it on the event $\left\{{P(Y)=1}\right\}$ . This class of distributions contains samplable distributions, as well as recognizable distributions (Defined in [29] and studied in [25, 1, 27, 30], see precise definition in Section 2.1).

Ball et al. [6] use the same construction as [37, 1], however their analysis is much more complicated, and introduces new conceptual ideas, as well as considerable technical sophistication. The price of achieving a weaker hardness assumption is that the proof is less modular, and significantly more complicated than that of [37]. Additionally, Ball et al. [6] only achieve standard (additive) extractors.

1.3 Our Results

1.3.1 Multiplicative Extractors for Samplable Distributions

In this paper we prove a version of Theorem 3 that achieves multiplicative extractors w.r.t. $\stackrel{{\scriptstyle m}}{{\sim}}_{\epsilon}$ , together with the two improvements of Ball et al. [6]. This achieves the best of both worlds. The precise result (stated below) is identical to Theorem 3, except for the weaker hardness assumption, the addition of “postselection”, and that $\stackrel{{\scriptstyle a}}{{\sim}}_{\epsilon}$ is replaced by $\stackrel{{\scriptstyle m}}{{\sim}}_{\epsilon}$ .

Theorem 4 (Multiplicative extractors for samplable distributions).

If ${\mathsf{E}}$ is hard for exponential size nondeterministic circuits then there exists a constant $\alpha>0$ , such that for every constant $c>1$ , and for every sufficiently large $n$ , there is a function $\mathsf{Ext}:\{0,1\}^{n}\to\{0,1\}^{\alpha n}$ that is a $((1-\alpha)\cdot n,\stackrel{{\scriptstyle m}}{{\sim}}_{\epsilon})$ -extractor for distributions samplable with postselection by circuits of size $n^{c}$ , where $\epsilon=n^{-c}$ . Furthermore, $\mathsf{Ext}$ is computable in time ${\mathsf{poly}}(n^{c})$ .

We use (essentially) the same construction as the previous papers [37, 1, 6] but suggest a different analysis that is more modular, and significantly simpler than the approach of Ball et al. [6]. In fact, in our opinion, this approach is simpler and more natural than that of the original work of Trevisan and Vadhan [37]. Loosely speaking, our proof borrows some of the new ideas of Ball et al. [6], but avoids the technical complications by considering an intermediate object that is a “multiplicative seed-extending PRG”. (We elaborate on our approach and compare it to that of [37, 6] in Section 3).

The role of our extractor in recent extractor for low min-entropy of [8]

In a subsequent work, Ball, Shaltiel and Silbak [8] gave the first construction of (additive) extractors for samplable distributions with low min-entropy. More specifically, they proved a version of Theorem 3 in which the min-entropy threshold $k=(1-\alpha)\cdot n$ is replaced with $k=n^{1-\alpha}$ . This is the first construction that improves the min-entropy threshold achieved by Trevisan and Vadhan [37], bypassing a well known barrier at $k=n/2$ .

The extractor construction of Ball, Shaltiel and Silbak [8] uses the multiplicative extractor of our Theorem 4 as a component, and critically relies on the multiplicativity of our extractor. In our opinion, this is another demonstration of the usefulness of multiplicative extractors.

We remark that the result of Ball, Shaltiel and Silbak [8] is incomparable to Theorem 4, as the assumption used in [8] is stronger, and the extractor achieved in [8] is additive rather than multiplicative. See discussion in the full version for some open problems.

Extracting more bits w.r.t. a multiplicative relation with two parameters

Theorem 4 achieves $m=\Omega(n)$ bits. As in previous work [37, 6], we can also obtain extractors that extract almost all the randomness (rather than a constant fraction) under the same assumption. In this result we obtain multiplicative extractors w.r.t $\stackrel{{\scriptstyle m}}{{\sim}}_{({\epsilon},{\delta})}$ , for an exponentially small additive error term $\delta$ .

Theorem 5 (Multiplicative extractors with larger output length).

If ${\mathsf{E}}$ is hard for exponential size nondeterministic circuits then for every sufficiently small constant $\gamma>0$ , every constant $c>1$ , and for every sufficiently large $n$ , there is a function $\mathsf{Ext}:\{0,1\}^{n}\to\{0,1\}^{(1-O(\gamma))\cdot n}$ that is a $((1-\gamma)\cdot n,\stackrel{{\scriptstyle m}}{{\sim}}_{({\epsilon},{\delta})})$ -extractor for distributions samplable with postselection by circuits of size $n^{c}$ , where $\epsilon=n^{-c}$ and $\delta=2^{-\Omega(\gamma\cdot n)}$ . Furthermore, $\mathsf{Ext}$ is computable in time ${\mathsf{poly}}(n^{c})$ .

Both [37] and [6] got extractors with the same output length. However, their extractor is additive (w.r.t. $\stackrel{{\scriptstyle a}}{{\sim}}_{\epsilon}$ for $\epsilon=n^{-c}$ ) and are not suitable for the application of selecting keys for cryptographic protocols. In contrast, our extractors are mutliplicative w.r.t $\stackrel{{\scriptstyle m}}{{\sim}}_{({\epsilon},{\delta})}$ for the same $\epsilon$ , and an exponentially small $\delta=2^{-\Omega(n)}$ which (as explained before) is suitable for the intended application.

As in the previous works [37, 6], enlarging the output length is achieved by composing the basic extractor with a seeded-extractor (which can be set up to have exponentially small additive error $\delta$ ). We observe that when the basic extractor is multiplicative (as in the case of Theorem 4) one obtains a multiplicative extractor (with two parameters $\epsilon$ and $\delta$ ) as in Theorem 5 (see full version).

1.3.2 Consequences and Necessary Assumptions for Extractors for Samplable Distributions

Hardness assumptions for extractors for samplable distributions

As mentioned previously, Trevisan and Vadhan [37] observed that extractors for samplable distributions imply circuit lower bounds. Specifically that if $\mathsf{Ext}:\{0,1\}^{n}\to\{0,1\}$ is an $(n-1,\stackrel{{\scriptstyle a}}{{\sim}}_{\frac{1}{5}})$ -extractor for distributions samplable by size $s$ circuits, then $\mathsf{Ext}$ cannot be computed by circuits of size slightly smaller than $s$ . This lower bound seems significantly weaker than the hardness assumption used in Theorem 4. A natural question is whether hardness against nondeterministic circuits (as in Theorem 4) is necessary for obtaining extractors for samplable distributions?

Following [6], we observe that our proof of Theorem 4 (as well as the proofs of the previous results [37, 6]) yield extractors for a richer class of distributions: The class of distributions that are samplable by size $s=n^{c}$ deterministic circuits, with postselection by size $s$ nondeterministic circuits.⁹⁹9Loosely speaking, the property of samplable distributions that is used in [37, 6] (and this paper) is that for a samplable distribution $X$ sampled by a poly-size circuit $A$ , a nondeterministic poly-size circuit can check whether a given $x$ is in the support of $X$ (or more generally that a poly-size $\Sigma_{1}$ -circuit can compute a multiplicative approximation to $\Pr[X=x]$ ). These properties also hold for postselecting samplable distributions even if one allows nondeterministic postselection. This is a richer class than both distributions samplable by size $n^{c}$ circuits (as in Theorem 3) and distributions samplable with postselection by size $n^{c}$ circuits (as in [6] and Theorem 4). See precise definition of this class in Section 2.1, and a formal statement and discussion in the full version.

We show that an extractor for this richer class of distributions does imply circuit lower bounds against nondeterministic circuits. More specifically, that $\mathsf{Ext}$ cannot be computed by nondeterministic circuits of size slightly smaller than $s$ .

In fact, we get the stronger conclusion that computing the extractor is hard on average for nondeterministic circuits. Specifically, we show that an $(n-\log(1/\epsilon),\stackrel{{\scriptstyle a}}{{\sim}}_{\epsilon})$ -extractor for this richer class is a function that is hard on average for nondeterministic circuits, meaning that every nondeterministic circuit of size slightly smaller than $s$ , computes the extractor correctly on at most a $(\frac{1}{2}+O(\epsilon))$ -fraction of the inputs. (In the case of extractors for the original class, this result gives average-case lower bounds against deterministic circuits).

Summing up, our results imply that hardness assumptions against nondeterministic circuits cannot be avoided as long as one uses proof techniques that immediately give extractors against this richer class of distributions (as is the case for all previous work). We remark that the lower bounds that we get are quantitatively weaker than the hardness assumption used in Theorem 4. See discussion in the full version.

Extractors for samplable distributions and seed-extending PRGs

We show that extractors for the richer class imply a stronger object than a hard on average function. Specifically, an extractor w.r.t $\stackrel{{\scriptstyle m}}{{\sim}}_{\epsilon}$ (rather than $\stackrel{{\scriptstyle a}}{{\sim}}_{\epsilon})$ for the richer class (as is the case in Theorem 4) is a seed-extending $\stackrel{{\scriptstyle a}}{{\sim}}_{O(\epsilon)}$ -PRG for nondetrministic circuits of size slightly smaller than $s$ . This result holds for every output length $m$ , and is achieved by adapting an argument of Kinne, van Melkebeek and Shaltiel [25].

Jumping ahead, we remark that the key idea in our construction of multiplicative extractors of Theorem 4, is to construct (multiplicative) seed-extending PRGs for nondeterministic circuits, and show that such PRGs are multiplicative extractors. See Section 3 for a detailed explanation.

Together, these results give a formal connection between seed-extending PRGs for nondeterministic circuits and extractors (at least for some ranges of parameters) and we believe that it may be beneficial to explore further connections between these objects. See the full version for a detailed discussion.

Paper Organization

This version is an extended abstract, and contains only a high level overview of the results and technique. The full version appears on [34] and contains precise proofs, as well as more discussion and some open problems.

In Section 2 we review some of the definitions and components used in this paper. In Section 3 we give a high level overview of our results.

2 Preliminaries

Probabilistic notation

For a distribution $D$ , we use the notation $X\leftarrow D$ to denote the experiment in which $X$ is chosen according to $D$ . For a set $A$ , we use $X\leftarrow A$ to denote the experiment in which $X$ is chosen uniformly from the set $A$ . We often also identify a distribution $X$ , with the random variable $X$ chosen from this distributions. For a random variable $X$ and an event $A$ we use $(X|A)$ to denote the distribution which chooses an element according to $X$ , conditioned on $A$ . We use $U_{n}$ to be the uniform distribution on $n$ elements.

Relations from the introduction

For completeness, we repeat the definition of the various relations defined in the Section 1.

Definition 6 (Definitions of relations from Section 1).

Given numbers $p_{1},p_{2},\epsilon,\delta\in[0,1]$ , we define the following relations:

$\displaystyle p_{1}\stackrel{{\scriptstyle ad}}{{\sim}}_{\epsilon}p_{2}$	$\displaystyle\iff$	$\displaystyle\|p_{2}-p_{1}\|\leq\epsilon.$
$\displaystyle p_{1}\stackrel{{\scriptstyle a}}{{\sim}}_{\epsilon}p_{2}$	$\displaystyle\iff$	$\displaystyle p_{2}\leq p_{1}+\epsilon.$
$\displaystyle p_{1}\stackrel{{\scriptstyle m}}{{\sim}}_{\epsilon}p_{2}$	$\displaystyle\iff$	$\displaystyle p_{2}\leq e^{\epsilon}\cdot p_{1}.$
$\displaystyle p_{1}\stackrel{{\scriptstyle m}}{{\sim}}_{({\epsilon},{\delta})}% p_{2}$	$\displaystyle\iff$	$\displaystyle p_{2}\leq e^{\epsilon}\cdot p_{1}+\delta.$
$\displaystyle p_{1}\stackrel{{\scriptstyle md}}{{\sim}}_{\epsilon}p_{2}$	$\displaystyle\iff$	$\displaystyle p_{1}\stackrel{{\scriptstyle m}}{{\sim}}_{\epsilon}p_{1}\mbox{ % and }p_{2}\stackrel{{\scriptstyle m}}{{\sim}}_{\epsilon}p_{1}.$

Note that while some of these relations (e.g. $\stackrel{{\scriptstyle m}}{{\sim}}_{\epsilon}$ ) are interesting for $\epsilon>1$ , in this paper we will always have that $0\leq\epsilon\leq 1$ so that $1+\epsilon\leq e^{\epsilon}\leq 1+3\epsilon$ , and $1-\epsilon\leq e^{-\epsilon}\leq 1-\frac{\epsilon}{3}$ . We will use these inequalities throughout this paper.

2.1 Samplable Distributions and Postselection

Samplable distributions

We use the following standard definition of samplable distributions. In the definition below, we will typically be interested in the case where $\mathcal{C}$ is the class of functions computable by size $n^{c}$ circuits for a constant parameter $c$ .

Definition 7 (Samplable distributions).

We say that a distribution $X$ over $\{0,1\}^{n}$ is sampled by a function $A:\{0,1\}^{r}\to\{0,1\}^{n}$ , if $X=A(U_{r})$ . Let $\mathcal{C}$ be a class of functions. A distribution $X$ over $\{0,1\}^{n}$ is samplable by $\mathcal{A}$ , if there exists a function $A:\{0,1\}^{r}\to\{0,1\}^{n}$ in the class $\mathcal{A}$ such that $X$ is sampled by $A$ .

Samplable distributions with postselection

Ball et al. [6] consider a more general class which allows the sampling circuit to perform “postselection”. More specifically, given a “sampling procedure” $A:\{0,1\}^{r}\to\{0,1\}^{n}$ and a “postselection” procedure $P:\{0,1\}^{r}\to\{0,1\}$ , we will say that the distribution sampled by the pair $(A,P)$ is the distribution $X$ over $\{0,1\}^{n}$ obtained by taking $Y\leftarrow U_{r}$ and setting $X=(A(Y)|P(Y)=1)$ . A formal definition appears below.

Definition 8 (Samplable distributions with postselection).

We say that a distribution $X$ over $\{0,1\}^{n}$ is sampled by a function $A:\{0,1\}^{r}\to\{0,1\}^{n}$ with postselection by $P:\{0,1\}^{n}\to\{0,1\}$ , if $X=(A(Y)|P(Y)=1)$ for $Y\leftarrow U_{r}$ . Let $\mathcal{A}$ and $\mathcal{P}$ be classes of functions. A distribution $X$ over $\{0,1\}^{n}$ is samplable by $\mathcal{C}$ with postselection by $\mathcal{P}$ if there exists a function $A:\{0,1\}^{r}\to\{0,1\}^{n}$ in the class $\mathcal{A}$ , and $P:\{0,1\}^{r}\to\{0,1\}$ in the class $\mathcal{P}$ such that $X$ is sampled by $A$ with postselection by $P$ . In the case that $\mathcal{A}$ and $\mathcal{P}$ coincide, we will say that $X$ is samplable with postselection by $\mathcal{A}$ .

Following Ball et al. [6] we are interested in distributions that are samplable with postselection by size $s=n^{c}$ circuits. Obviously, every distribution that is samplable by circuits of size $s$ is also samplable with postselection by circuits of size $s$ . However, sampling with postelection allows conditioning on events $\left\{{Y:P(Y)=1}\right\}\subseteq\{0,1\}^{r}$ that occur with low probability, and seems to give a richer class of distribution.

Distributions samplable by deterministic circuits with postselection by nondeterministic circuits

The reason that we allow the class $\mathcal{A}$ (of sampling circuits) to be different than the class $\mathcal{P}$ (of postselecting circuits) is that we want to consider the yet richer class of distributions that are samplable by size $s$ (deterministic) circuits with postselection by size $s$ nondeterministic circuits. See discussion in the full version.

Recognizable distributions

Distributions that are Samplable with postselection can also be seen as a generalization of the notion of “recognizable distribution” defined by Shaltiel [29], see also [25, 1, 27, 30], which in this terminology is the special case of distribution samplable with postselection, but restricted to the case that the sampling circuit $A$ is the identity function (so that $A(U_{n})$ samples the uniform distribution on $n$ bits).

2.2 Definition of Circuits of Various Types

We formally define the circuit types that will be used in this paper.

Definition 9 (randomized circuits, nondeterministic circuits, oracle circuits and $\Sigma_{i}$ -circuits).

A randomized circuit $C$ has additional wires that are instantiated with uniform and independent bits.

A nondeterministic circuit $C$ has additional “nondeterministic input wires”. We say that the circuit $C$ evaluates to 1 on $x$ iff there exist an assignment to the nondeterministic input wires that makes $C$ output 1 on $x$ .

An oracle circuit $C^{(\cdot)}$ is a circuit which in addition to the standard gates uses an additional gate (which may have large fan in). When instantiated with a specific boolean function $A$ , $C^{A}$ is the circuit in which the additional gate is $A$ . Given a boolean function $A(x)$ , an $A$ -circuit is a circuit that is allowed to use $A$ gates (in addition to the standard gates). An $A_{||}$ -circuit is a circuit that makes nonadaptive queries to its oracle $A$ . (Namely, on every path from input to output, there is at most a single $A$ gate).

An NP-circuit is a SAT-circuit (where SAT is the satisfiability function) a $\Sigma_{i}$ -circuit is an $A$ -circuit where $A$ is the canonical $\Sigma_{i}^{\text{P}}$ -complete language. The size of all circuits is the total number of wires and gates.¹⁰¹⁰10An alternative approach to define these circuit classes is using the Karp-Lipton notation for Turing machines with advice. For $s\geq n$ , a size $s^{\Theta(1)}$ deterministic circuit is equivalent to ${\mathsf{DTIME}}(s^{\Theta(1)})/s^{\Theta(1)}$ , a size $s^{\Theta(1)}$ nondeterministic circuit is equivalent to ${\mathsf{NTIME}}(s^{\Theta(1)})/s^{\Theta(1)}$ , a size $s^{\Theta(1)}$ NP-circuit is equivalent to ${\mathsf{DTIME}}^{{\mathsf{NP}}}(s^{\Theta(1)})/s^{\Theta(1)}$ , and a size $s^{\Theta(1)}$ $\Sigma_{i}$ -circuit is equivalent to ${\mathsf{DTIME}}^{\Sigma_{i}^{P}}(s^{\Theta(1)})/s^{\Theta(1)}$ .

2.3 Hardness Assumptions

We will rely on assumptions of the following form, introduced by Impagliazzo and Wigderson [24]

Definition 10 ( ${\mathsf{E}}$ is hard for exponential size circuits).

We say that “ ${\mathsf{E}}$ is hard for exponential size circuits of type X” if there exist constants $0<\beta<B$ , and a language $L$ in ${\mathsf{E}}={\mathsf{DTIME}}(2^{B\cdot n})$ , such that for every sufficiently large $n$ , the characteristic function of $L$ on inputs of length $n$ is hard for circuits of size $2^{\beta n}$ of type X.

2.4 Sudan’s List-Decoding Algorithm

We will rely on Sudan’s celebrated list-decoding algorithm for the Reed-Solomon code [35].

Theorem 11 (Sudan’s list-decoding algorithm [35]).

Let $\mathsf{prs},\mathsf{agr},\mathsf{deg}$ be integers. Given $\mathsf{prs}$ distinct pairs $(x_{i},y_{i})$ in field $F$ with $\mathsf{agr}>\sqrt{2\cdot\mathsf{deg}\cdot\mathsf{prs}}$ , there are at most $2\mathsf{prs}/\mathsf{agr}$ polynomials $g$ of degree $\mathsf{deg}$ such that $g(x_{i})=y_{i}$ for at least $\mathsf{agr}$ pairs. Furthermore, a list of all such polynomials can be computed in time ${\mathsf{poly}}(\mathsf{prs},\log|F|)$ .

We remark that in this paper (as in the previous work [37, 6]) we will rely only existence of small lists, and do not use the efficiency of list-decoding algorithm.

2.5 Seeded Extractors

We use the following standard definition of seeded extractors. We remark that in many cases these are called “extractors” and this paper we use the term “seeded extractor” to differentiate them from seedless extractors.

Definition 12 (Seeded extractors).

A function $\mathsf{SExt}:\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m}$ is a $(k,\epsilon)$ -seeded extractor if for every distribution $X$ over $\{0,1\}^{n}$ , with $H_{\infty}(X)\geq k$ , $\mathsf{SExt}(X)$ is $\epsilon$ -close to $U_{m}$ .

$\mathsf{SExt}$ is a strong $(k,\epsilon)$ -seeded extractor if the function $\mathsf{SExt}^{\prime}:\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{d+m}$ defined by $\mathsf{SExt}^{\prime}(x,y)=(y,\mathsf{SExt}(x,y))$ is a $(k,\epsilon)$ -seeded extractor.

We use the following result known as the “leftover hash lemma” by Impagliazzo, Levin and Luby [23]

Theorem 13 (Leftover hash lemma [23]).

For every integers $m\leq n$ , and $\epsilon>0$ , there is a $(m+2\log(1/\epsilon),\epsilon)$ -strong extractor $\mathsf{SExt}:\{0,1\}^{n}\times\{0,1\}^{n}\to\{0,1\}^{m}$ . Furthermore, $\mathsf{SExt}$ can be computed in time ${\mathsf{poly}}(n)$ .

We remark that in some sources this lemma is stated with $d=2n$ rather than $d=n$ , but the statement also holds for $d=n$ (as stated above).

We also use the following result by Guruswami, Umans and Vadhan [20].

Theorem 14 ([20]).

For every constant $\alpha>0$ , and for every $k\leq n$ and $\epsilon>0$ , there is a $(k,\epsilon)$ -seeded extractor $\mathsf{SExt}:\{0,1\}^{n}\times\{0,1\}^{d}\to\{0,1\}^{m}$ for $d=O(\log n+\log(1/\epsilon))$ and $m=(1-\alpha)k$ . Furthermore, $\mathsf{SExt}$ can be computed in time ${\mathsf{poly}}(n)$ .

2.6 The Low Degree Extension

Many results in complexity theory and derandomization rely on the low-degree extension. Loosely speaking, this is a technique to extend a given function $f:\{0,1\}^{\ell}\to\{0,1\}$ to a low-degree $d$ -variate polynomial $\hat{f}:\mathbb{F}_{q}^{d}\to\mathbb{F}_{q}$ . The standard precise statement is given below.

Lemma 15.

Let $f:\{0,1\}^{\ell}\to\{0,1\}$ be a function and $d\leq h\leq q$ be integers such that $h^{d}\geq 2^{\ell}$ and $q$ is a power of $2$ . Given $H\subseteq\mathbb{F}_{q}$ of size $h$ , and a one-to-one map $\phi:\{0,1\}^{\ell}\to H^{d}$ , there is a degree $\hat{h}=h\cdot d$ polynomial $\hat{f}:\mathbb{F}_{q}^{d}\to\mathbb{F}$ such that for every $x\in\{0,1\}^{\ell}$ , $f(x)=\hat{f}(\phi(x))$ . Furthermore, $\hat{f}$ can be computed in time ${\mathsf{poly}}(2^{\ell},\log q)$ given oracle access to $f$ .

2.7 The Goldwasser-Sipser AM Protocol and Consequences

A classical result by Goldwasser and Sipser [19] shows that there is an AM protocol for showing that the fraction of accepting inputs of a given circuit is above some threshold. The same approach translates immediately to the case where the given circuit is nondeterministic (rather than deterministic). Below is a formal definition.

Definition 16 (The nondeterministic large set promise problem).

Given $\lambda>0$ , we define a promise problem $\mathsf{NondetLarge}_{\lambda}$ over pairs $(C,\gamma)$ where $C$ is a nondeterministic circuit, and $0\leq\gamma\leq 1$ .

$\blacksquare$

The Yes instances are pairs $(C,\gamma)$ such that $C$ accepts at least a $\gamma$ -fraction of its inputs.
$\blacksquare$

The No instances are pairs $(C,\gamma)$ such that $C$ accepts less than a $\gamma\cdot e^{-\lambda}$ -fraction of its inputs.

Note that a circuit $C$ of size $s$ can have at most $s$ input bits. Throughout the paper we will always assume w.l.o.g. that $C$ has $s$ input bits (and may ignore some of them). We also note that because the number of possible inputs to $C$ is at most $2^{s}$ , we can always assume that the number of bits needed to represent $\gamma$ is at most $s$ (which implies that the input to the promise problem is of length that is dominated by the length of the description of $C$ , which is $O(s\log s)$ ).

Theorem 17 (Goldwasser and Sipser [19]).

For every integer $s$ and $\lambda>0$ , there is a nondeterministic circuit $A$ of size ${\mathsf{poly}}(s,\frac{1}{\lambda})$ which solves the promise problem $\mathsf{NondetLarge}_{\lambda}$ .

Theorem 17 is stated in a somewhat nonstandard way. The more standard formulation discusses deterministic circuits $C$ , and gives an AM protocol that solves the promise problem. However, the same result immediately applies to nondeterministic circuits. This is because in the Goldwasser-Sipser AM protocol, Merlin sends inputs $x$ to $C$ on which $C(x)=1$ , and if $C$ is nondeterministic, whenever Merlin sends an $x$ , he can also supply a witness showing that $C(x)=1$ . This gives an AM-protocol with time ${\mathsf{poly}}(s,\frac{1}{\lambda})$ for $\mathsf{NondetLarge}_{\lambda}$ , and the result in the theorem follows because one can transform an AM-protocol into a nondeterministic circuit, as in the proof that ${\mathsf{AM}}\subseteq{\mathsf{NP}}/{\mathsf{poly}}$ .

2.8 A Tail Inequality

We need the following tail inequality by Bellare and Rompel [10].

Theorem 18 ( $r$ -wise independent tail inequality [10]).

Let $r>4$ be an even integer. Suppose $X_{1},X_{2},\ldots,X_{n}$ are $r$ -wise independent random variables taking values in $[0,1]$ . Let $X=\sum{X_{i}}$ , $\mu=\operatorname{\mathbb{E}}[X]$ and $A>0$ . Then:

\Pr[|X-\mu|\geq A]\leq 8\cdot\left(\frac{r\mu+r^{2}}{A^{2}}\right)^{r/2}.

In particular, if $r\leq n$ , setting $A=\epsilon n$ , for some $\epsilon>0$ , it follows that:

\Pr[|X-\mu|\geq\epsilon n]\leq 8\cdot\left(\frac{2r}{\epsilon^{2}n}\right)^{r/% 2}.

3 Technique

3.1 A Brief Overview of the Approach Used in the Previous Work

Extractors from functions that are very hard functions on average

Trevisan and Vadhan [37] started from a simple observation that if a function $\mathsf{Ext}:\{0,1\}^{n}\to\{0,1\}$ is sufficiently hard on average (against $\Sigma_{1}$ -circuits) then $\mathsf{Ext}$ is an extractor (that outputs a single bit) for distributions samplable by poly-size (deterministic) circuits. More specifically, using our terminology they showed that:

Lemma 19 (Extractors from very hard on average functions [37]).

Let $f:\{0,1\}^{n}\to\{0,1\}$ be a function such that for every $\Sigma_{1}$ -circuit $C$ of size $s\geq n$ , it holds that $\Pr_{X\leftarrow U_{n}}[C(X)=f(X)]\leq\frac{1}{2}+\frac{\epsilon}{2^{\Delta}}$ . Then, $f$ is an $(n-\Delta,\stackrel{{\scriptstyle a}}{{\sim}}_{4\epsilon})$ -extractor for distributions samplable by circuits of size $s^{\prime}=(s\epsilon)^{\Omega(1)}$ .

This means that constructing extractors for samplable distributions from worst-case assumptions can be potentially achieved by “hardness amplification” which is the task of converting worst-case hard functions (as in hardness assumptions) into functions that are sufficiently hard on average. This seems promising as hardness amplification is a successful paradigm with many classical results [24, 36].

Unfortunately, even if we settle for constant $\epsilon$ , unless the entropy deficiency is very small, and $\Delta=O(\log n)$ , there are no known hardness amplification results with suitable parameters. (Note that in Theorems 3 and 4, a much larger entropy deficiency of $\Delta=\Omega(n)$ is obtained).

In fact, later work [1] shows that it is impossible to use “black-box techniques” to start from the assumption that ${\mathsf{E}}$ is hard for $\Sigma_{i}$ -circuits, and obtain a function that is this hard on average (and this holds for every $i$ ). This means that results like Theorem 3 cannot be obtained by hardness amplification.

Bypassing the barrier of obtaining functions that are very hard on average

Because of this barrier, Trevisan and Vadhan (and following work) could not use Lemma 19 directly. Instead, Trevisan and Vadhan used a construction by Sudan, Trevisan and Vadhan [36] (that is based on error-correcting codes, and was used to obtain hardness amplification) to design their function $\mathsf{Ext}:\{0,1\}^{n}\to\{0,1\}$ .

As they could not show that $\mathsf{Ext}$ is sufficiently hard on average, they instead directly showed that $\mathsf{Ext}$ is an extractor for samplable distributions. This leads to technical complications (that do not arise when analyzing $\mathsf{Ext}$ in the realm of hardness amplification). Specifically, in the case of hardness amplification one is interested in the behavior of $\mathsf{Ext}$ on a uniform $X\leftarrow U_{n}$ . In contrast, when analyzing $\mathsf{Ext}$ as an extractor, one needs to analyze $\mathsf{Ext}$ on an arbitrary samplable distribution $X$ with $H_{\infty}(X)\geq n-\Delta$ .

On a technical level, the function $\mathsf{Ext}$ designed by Trevisan and Vadhan (which we will soon review in detail) relies on an error-correcting code with block length $2^{n}$ . Analyzing it on a distribution $X$ that is substantially different than $U_{n}$ runs into difficulties, as error-correcting codes give the “same importance” to every one of the symbols of the $2^{n}$ bit long codeword, whereas the distribution $X$ does not.

The recent and exciting work of Ball et al. [6] uses the same function $\mathsf{Ext}$ , and uses considerable technical sophistication to analyze the behavior of $\mathsf{Ext}$ on distributions $X$ that have high min-entropy but are not uniform. This indeed allows Ball et al. to make the reduction use “less levels of nondeterminism” and start from a weaker hardness assumption, but leads to a complicated and technical proof (as modularity is sacrificed in order make the reduction use less levels of nondeterminism). Moreover, [6] do not get a multiplicative extractor.

3.2 Multiplicative Extractors from Seed-Extending Multiplicative PRGs

In Lemma 20 of this paper, we introduce a new approach to construct extractors from samplable distributions. More specifically, we prove an analogous result to Lemma 19 with the difference that rather than starting from a function that is hard on average for nondeterministic circuits, we start from a seed-extending multiplicative PRG for nondeterministic circuits (as in Definition 2). This has several advantages:

$\blacksquare$

This approach is applicable to any output length $m$ , and not just to $m=1$ , as is the case of Lemma 19.
$\blacksquare$

The approach gives multiplicative extractors w.r.t. $\stackrel{{\scriptstyle m}}{{\sim}}_{\epsilon}$ rather than additive extractors w.r.t. $\stackrel{{\scriptstyle a}}{{\sim}}_{\epsilon}$ .¹¹¹¹11Note that for small output length $m$ , say $m=1$ , the multiplicative and additive notions of “close to uniform” essentially coincide. The difference between the additive and multiplicative notions increases with $m$ . The fact that the new approach works directly for large $m$ is one of the reasons that allow it to get multiplicative extractors.
$\blacksquare$

Most importantly, as we show in Theorem 21 below, the starting point of the new approach in Lemma 20, can be achieved under the weak assumption that ${\mathsf{E}}$ is hard for exponential size nondeterministic circuits. In contrast (as we explained previously) there are barriers to obtaining the starting point of Lemma 19 even under significantly stronger assumptions against $\Sigma_{i}$ -circuits [1], and these barriers apply even for (additive) extractors that output a single bit.

The new approach is stated in the lemma below.

Lemma 20 (Multiplicative extractors from Multiplicative PRGs).

If $G:\{0,1\}^{n}\to\{0,1\}^{m}$ is a seed-extending PRG for nondeterministic circuits of size $s\geq n\geq m$ w.r.t. $\stackrel{{\scriptstyle m}}{{\sim}}_{({\epsilon},{\frac{\epsilon}{2^{\Delta+m}% }})}$ . Then, $G$ is an $(n-\Delta,\stackrel{{\scriptstyle m}}{{\sim}}_{12\epsilon})$ -extractor for distributions samplable by circuits of size $s^{\prime}=(s\epsilon)^{\Omega(1)}$ .

We will soon show in Section 3.3 that essentially the same function $\mathsf{Ext}$ used by Trevisan and Vadhan, can be shown to be a seed-extending multiplicative PRG, with parameters that yield Theorem 4 using Lemma 20. This approach will lead to a simple and modular proof that produces a multiplicative extractor.

A more general version of Lemma 20 (which applies to the richer class of samplable distributions with postselection) is stated and proven in the full version. Below is a proof sketch.

Proof sketch for Lemma 20

Let us now explain the idea behind the proof of Lemma 20. For this purpose, we will consider a simpler case in which we are only interested in extracting from samplable distributions $W$ over $\{0,1\}^{n}$ which are flat. That is, that $W$ is uniform over a set $T\subseteq\{0,1\}^{n}$ of size $2^{n-\Delta}$ . The advantage of assuming that $W$ is flat, is that this immediately implies that there is a small nondeterministic circuit $B$ which given $x\in\{0,1\}^{n}$ , answers one iff $x\in T$ . This follows because if $A:\{0,1\}^{r}\to\{0,1\}^{n}$ is the size $s^{\prime}$ sampling circuit such that $W=A(U_{r})$ , then when given $x$ , $B$ can verify that $x\in T$ by “guessing” $v\in\{0,1\}^{r}$ such that $A(v)=x$ , and $v$ serves as a witness that $x\in T$ .

Assume that $G:\{0,1\}^{n}\to\{0,1\}^{m}$ is not an $(n-\Delta,\stackrel{{\scriptstyle m}}{{\sim}}_{12\epsilon})$ -extractor for $W$ . This means that there exists $z\in\{0,1\}^{m}$ such that $\Pr[G(W)=z]>e^{12\epsilon}\cdot 2^{-m}$ . We now design a nondeterministic circuit $D:\{0,1\}^{n}\times\{0,1\}^{m}\to\{0,1\}$ of size $s$ that shows that $G^{\prime}(x)=(x,G(x))$ is not a $\stackrel{{\scriptstyle m}}{{\sim}}_{({\epsilon},{\frac{\epsilon}{2^{\Delta+m}% }})}$ -PRG.

On input $(x,y)\in\{0,1\}^{n}\times\{0,1\}^{m}$ , $D(x,y)$ will answer one if $x\in T$ and $y=z$ . (Note that $D$ can do this by using the circuit $B$ ). By construction, $D$ is a nondeterministic circuit of size $s$ for $s$ slightly larger than $s^{\prime}$ . Let us consider the random variables $X\leftarrow U_{n}$ , and $Y\leftarrow U_{m}$ , we compute:

	$\displaystyle p_{1}$	$\displaystyle=\Pr[D(X,Y)=1]=\Pr[X\in T\wedge Y=z]=\Pr[X\in T]\cdot\Pr[Y=z]=2^{% -\Delta}\cdot 2^{-m}.$
	$\displaystyle p_{2}$	$\displaystyle=\Pr[D(G^{\prime}(X))=1]=\Pr[D(X,G(X))=1]=\Pr[X\in T\wedge G(X)=z]$
		$\displaystyle=\Pr[X\in T]\cdot\Pr[G(X)=z\|X\in T]=2^{-\Delta}\cdot\Pr[G(W)=z]>2% ^{-\Delta}\cdot e^{12\epsilon}\cdot 2^{-m},$

In particular, we have that

p_{2}>e^{12\epsilon}\cdot p_{1}\geq(1+12\epsilon)\cdot p_{1}=(1+11\epsilon)% \cdot p_{1}+\epsilon\cdot p_{1}\geq e^{\epsilon}\cdot p_{1}+\epsilon\cdot 2^{-% (\Delta+m)},

and we indeed conclude that $p_{1}\not\stackrel{{\scriptstyle m}}{{\sim}}_{({\epsilon},{\frac{\epsilon}{2^{% \Delta+m}}})}p_{2}$ , and get a contradiction.

The case where $W$ is not flat is handled in the formal proof in the full version by replacing the check whether $x$ is in the support of $W$ , by a quantitative check that approximates $\Pr[W=x]$ , and using the fact that nondeterministic circuits can approximate this quantity (in the sense that using Goldwasser-Sipser protocol [19], nondeterministic circuits can verify that this quantity is approximately larger than a given threshold, see Section 2.7 for details).

3.3 A Construction of Seed-Extending Multiplicative PRGs

In light of Lemma 20, in order to obtain the extractor stated in Theorem 4, it is sufficient to start from the assumption that ${\mathsf{E}}$ is hard for exponential size nondeterministic circuits, and construct multiplicative seed-extending PRGs for nondeterministic circuits.

Our PRG construction (which is specified formally in Figure 1) is essentially the same as that of the extractor of Trevisan and Vadhan [37], which builds on an adaptation of [36]. More specifically, we start from a hard function $f:\{0,1\}^{\ell}\to\{0,1\}$ (which is the characteristic function of the language in the hardness assumption). When shooting to get the extractor of Theorem 4, we set $\ell=O(\log n)$ , so that the assumption gives that $f$ cannot be computed by nondeterministic circuits of size slightly larger than $n^{c}$ . With this choice, $f$ is computable in time $2^{O(\ell)}={\mathsf{poly}}(n^{c})$ . As is common in this area, the first step is to extend $f:\{0,1\}^{\ell}\to\{0,1\}$ into a low degree polynomial $\hat{f}:\mathbb{F}_{q}^{d}\to\mathbb{F}_{q}$ using the “low degree extension” a.k.a. the Reed-Muller code. Specifically, for an appropriately chosen constant $d$ , we set $h=2^{\ell/d}$ , and set $\hat{f}:\mathbb{F}_{q}^{d}\to\mathbb{F}_{q}$ to be a polynomial of individual degree $h$ (and total degree $h d$ ) that coincides with $f$ on a “subcube” of size $h^{d}=2^{\ell}$ of the $q^{d}$ inputs (see Figure 1 for a more formal description). In coding theoretic terms, this means that the truth table of $\hat{f}$ is a Reed-Muller encoding of the truth table of $f$ . As in [37], we choose a non-standard and huge alphabet size $q$ , which will be exponential in $n$ when proving Theorem 4.

The next step is to use “code concatenation” to obtain an $m$ bit output. This concatenation is done using the seeded-extractor $\mathsf{SExt}:\{0,1\}^{\log q}\times\{0,1\}^{\log q}\to\{0,1\}^{m}$ of the leftover hash lemma [23] (see precise statement in Theorem 13).¹²¹²12Here there is a difference from previous work [37, 1, 6] and we can use a seeded-extractor $\mathsf{SExt}$ , whereas previous work required $\mathsf{SExt}$ to be a $2$ -source extractor (which is a stronger requirement). The final PRG $G(x)$ is obtained by thinking of $x\in\{0,1\}^{n}$ as a pair $(w,y)\in\mathbb{F}_{q}^{d}\times\{0,1\}^{\log q}$ and defining $G(x)=\mathsf{SExt}(\hat{f}(w),y)$ . A precise formal description appears in Figure 1. We will prove the following theorem.

Hardness assumption: We are assuming that

{\mathsf{E}}

is hard for exponential size nondeterministic circuits. Namely, that there exist constants

0<\beta<1<B

and a function

f:\{0,1\}^{*}\to\{0,1\}

such that: Easiness:

f

is computable in time

2^{B\ell}

on inputs of length

\ell

. Hardness: For every sufficiently large

\ell

, nondeterministic circuits of size

2^{\beta\ell}

fail to compute

f

on inputs of length

\ell

. Input parameters: We are given integers

m\leq s

and

\rho>0

, such that

\frac{1}{2^{s}}\leq\rho\leq\frac{1}{s}

, and are assuming that

s

is sufficiently large. Goal: A seed-extending

\stackrel{{\scriptstyle m}}{{\sim}}_{({\frac{1}{s}},{\rho})}

-PRG for size

s

nondeterministic circuits, with output length

m

and seed length

O(m+\log(1/\rho))

. Construction: Low degree extension: Let

c_{0},c_{q}

be sufficiently large universal constants that will be chosen in the proof. We set

h=s

,

d=\frac{c_{0}}{\beta}

,

\ell=d\log h

and

q=\frac{2^{m}}{\rho^{c_{q}}}

. Let

\mathbb{F}_{q}

be the field with

q

elements (we will be assuming that

q

is a power of

2

) and fix some set

H\subseteq\mathbb{F}_{q}

of size

h

. Note that

|H^{d}|=2^{\ell}

, and we can identify between

\{0,1\}^{\ell}

and

H^{d}

. We define

\hat{f}:\mathbb{F}_{q}^{d}\to\mathbb{F}_{q}

be the “low degree extension” of

f

(a precise statement is given in Lemma 15). This is a polynomial of degree

\hat{h}=hd

such that for every

x\in\{0,1\}^{\ell}

,

\hat{f}(x)=f(x)

(where in the l.h.s. we view

x

as element in

H^{d}\subseteq\mathbb{F}_{q}^{d}

). We have that

\hat{f}

is computable in time

{\mathsf{poly}}(2^{B\ell},\log q)={\mathsf{poly}}(s)

. Leftover hash lemma seeded extractor: Let

\epsilon=\frac{\rho}{100s}

, and

\mathsf{SExt}:\{0,1\}^{\log q}\times\{0,1\}^{\log q}\to\{0,1\}^{m}

be the

(m+2\log(1/\epsilon),\epsilon)

-strong seeded extractor of the “Leftover hash lemma” (formally specified in Theorem 13). Note that by choosing

c_{q}

to be sufficiently large, we have that the

\log q>m+2\log(1/\epsilon)

. Construction of seed-extending PRG: We define

G:\{0,1\}^{(d+1)\log q}\to\{0,1\}^{m}

as follows: Given a seed

x\in\{0,1\}^{(d+1)\log q}

we interpret it as a pair

(w,v)\in\mathbb{F}_{q}^{d}\times\{0,1\}^{\log q}

and define:

G(x)=\mathsf{SExt}(\hat{f}(w),v).

Note that by our choices, the seed length is

(d+1)\log q=a\cdot(m+\log(1/\rho))

, for some constant

a

that depends only on

\beta

. Furthermore,

G

is computable in time

2^{B\cdot\ell+1}+{\mathsf{poly}}(2^{\ell},\log q)={\mathsf{poly}}(s)

(where the exponent of the polynomial in

s

is a universal constant times

\frac{B}{\beta}

).

Figure 1: Construction of multiplicative PRG.

Theorem 21 (Multiplicative PRG).

If ${\mathsf{E}}$ is hard for exponential size nondeterministic circuits, then there exists a constant $a\geq 1$ such that for every sufficiently large $s$ , $m\leq s$ , and $\frac{1}{2^{s}}\leq\rho\leq\frac{1}{s}$ . The function $G:\{0,1\}^{a\cdot(m+\log(1/\rho))}\to\{0,1\}^{m}$ defined in Figure 1 is a seed-extending $\stackrel{{\scriptstyle m}}{{\sim}}_{({\frac{1}{s}},{\rho})}$ -PRG for nondeterministic circuits of size $s$ . Furthermore, $G$ can be computed in time ${\mathsf{poly}}(s)$ .

Theorem 4 follows directly from Lemma 20 and Theorem 21, the details appear in the full version. Note that in Theorem 21 the output length $m$ is smaller than the input length. While this is suitable for our application, this raises the question of whether PRGs with larger stretch are possible. See full version for a discussion and related results by Artemenko et al. [2].

In the remainder of this section we prove Theorem 21. That is, we will show that given a size $s$ nondeterministic circuit $D$ that breaks the PRG, we can construct a small nondeterministic circuit $A$ that computes $f$ and contradicts the hardness assumption.

The main technical difficulty in this argument is that we want $A$ to have size polynomial in $s$ even though $\frac{1}{\rho}$ and $q$ are not polynomial in $s$ . This means that we cannot run list-decoding algorithms for the underlying code, and this holds also if we restrict $\hat{f}$ to a line in $\mathbb{F}_{q}^{d}$ (which corresponds to a Reed-Solomon code) as the line is of length $q\geq 1/\rho$ . Instead, following Trevisan and Vadhan [37] (who in turn attribute the idea to Feige and Lund [17]) we will use nondeterminism to “speed up” such computation, so that it does run in time ${\mathsf{poly}}(s)$ . Our approach also builds on some of the improvements of Ball et al. [6] to reduce the number of “levels of nondeterminism” used in the argument. The full proof appears in Section 3.3.1 below.

3.3.1 Proof of Theorem 21

Assume that $G$ is not a seed-extending $\stackrel{{\scriptstyle m}}{{\sim}}_{({\frac{1}{s}},{\rho})}$ -PRG for nondeterministic circuits of size $s$ . Let $D:\mathbb{F}_{q}^{d}\times\{0,1\}^{\log q}\times\{0,1\}^{m}\to\{0,1\}$ be a size $s$ nondeterministic circuit that breaks $G$ . Throughout this proof we will consider a probability space with the following independently chosen random variables:

W\leftarrow\mathbb{F}_{q}^{d},V\leftarrow\{0,1\}^{\log q},R\leftarrow U_{m},T% \leftarrow\mathbb{F}_{q}\setminus\left\{{0}\right\}.

We define $p_{1}=\Pr[D(W,V,R)=1]$ and $p_{2}=\Pr[D(W,V,\mathsf{SExt}(\hat{f}(W),V))=1]$ . By the assumption that $D$ breaks $G$ we have that $p_{1}\stackrel{{\scriptstyle m}}{{\not\sim}}_{({\frac{1}{s}},{\rho})}p_{2}$ , meaning that $p_{2}>e^{\frac{1}{s}}\cdot p_{1}+\rho$ .

We will design a nondeterministic circuit $A$ that computes $f$ and contradicts the hardness assumption. This will be done by using (a variant of) the celebrated list-decoding algorithm of Sudan, Trevisan and Vadhan [36]. In this variant we will use “curves” instead of “lines” in a way that resembles the PRG of [31]. This will be simpler to analyze, and will produce a self contained proof.¹³¹³13The argument of [36] requires an additional step of “self correction”, and in our setting, showing that this step can be performed by a nondeterministic circuit (rather than a $\Sigma_{1}$ -circuit) requires repeating the self-correction argument. Moreover, the argument we present here is arguably simpler and more direct than that used in [36, 37]. It should be noted however, that our argument gives slightly inferior parameters as a list-decoding algorithm, but this difference is immaterial when proving Theorem 21.

Definition 22 (Degree $r$ curve passing through given $r+1$ points).

For distinct $r+1$ elements $t_{0},\ldots,t_{r}\in\mathbb{F}_{q}$ and (not necessarily distinct) $y_{0},\ldots,y_{r}\in\mathbb{F}_{q}^{d}$ we define $C_{\genfrac{}{}{0.0pt}{}{t_{0},\ldots,t_{r}}{y_{0},\ldots,y_{r}}}:\mathbb{F}_{% q}\to\mathbb{F}_{q}^{d}$ to be the unique degree $r$ polynomial such that for every $0\leq j\leq r$ , $C_{\genfrac{}{}{0.0pt}{}{t_{0},\ldots,t_{r}}{y_{0},\ldots,y_{r}}}(t_{j})=y_{j}$ .

The main technical lemma in the proof of Theorem 21 is the following lemma. It shows that for every $x\in\mathbb{F}_{q}^{d}$ , there is a low-degree univariate polynomial $\hat{p}_{x}$ such that $\hat{p}_{x}(0)=\hat{f}(x)$ , and furthermore, there is a specific test (specified in the lemma) that $\hat{p}_{x}$ passes, but no other low degree polynomial does.

More specifically, the lemma shows that for some sufficiently large constant $r$ , there exist $t_{1},\ldots,t_{r}\in\mathbb{F}_{q}\setminus\left\{{0}\right\}$ and $y_{1},\ldots,y_{r}\in\mathbb{F}_{q}^{d}$ , such that for every $x\in\mathbb{F}_{q}^{d}$ , if we define $C_{x}=C_{\genfrac{}{}{0.0pt}{}{0,t_{1},\ldots,t_{r}}{x,y_{1},\ldots,y_{r}}}$ to be the degree $r$ curve passing through the points $(0,x)$ , $(t_{1},y_{1}),\ldots,(t_{r},y_{r})$ , then the polynomial $\hat{p}_{x}=\hat{f}\circ C_{x}$ (which indeed satisfies $\hat{p}_{x}(0)=\hat{f}(x)$ ) is the only low-degree polynomial $p$ such that $\Pr[D(C_{x}(T),V,\mathsf{SExt}(p(T),V))=1]$ is large. This is useful (as we will explain in detail below) as we aim to construct a nondeterministic circuit and this circuit will guess a polynomial $p$ , verify that it passes the test, and then we have that $\hat{f}(x)=\hat{p}_{x}(0)$ .

Lemma 23.

Let $r=c_{r}\cdot d=\frac{c_{r}\cdot c_{0}}{\beta}$ for a sufficiently large universal constant $c_{r}$ , let $\gamma_{1}=p_{1}+4\epsilon$ , and $\gamma_{2}=p_{2}-\epsilon$ . There exist distinct $t_{1},\ldots,t_{r}\in\mathbb{F}_{q}\setminus\left\{{0}\right\}$ and $y_{1},\ldots,y_{r}\in\mathbb{F}_{q}^{d}$ such that for every $x\in\mathbb{F}_{q}^{d}$ , setting $C_{x}=C_{\genfrac{}{}{0.0pt}{}{0,t_{1},\ldots,t_{r}}{x,y_{1},\ldots,y_{r}}}$ , we have that $\gamma_{2}>e^{\frac{1}{4s}}\cdot\gamma_{1}$ , and furthermore:

The correct polynomial passes:

For the degree $\hat{h}\cdot r$ polynomial $\hat{p}_{x}:\mathbb{F}_{q}\to\mathbb{F}_{q}$ defined by $\hat{p}_{x}=\hat{f}\circ C_{x}$ , we have that for every $j\in[r]$ , $\hat{p}_{x}(t_{j})=\hat{f}(y_{j})$ , $\hat{p}_{x}(0)=\hat{f}(x)$ and

\Pr[D(C_{x}(T),V,\mathsf{SExt}(\hat{p}_{x}(T),V))=1]\geq\gamma_{2}.

No incorrect polynomial passes:

For every degree $\hat{h}\cdot r$ polynomial $p:\mathbb{F}_{q}\to\mathbb{F}_{q}$ such that $p\neq\hat{p}_{x}$ , that satisfies that for every $j\in[r]$ , $p(t_{j})=\hat{f}(y_{j})$ , we have that

\Pr[D(C_{x}(T),V,\mathsf{SExt}(p(T),V))=1]\leq\gamma_{1}.

Showing that Theorem 21 follows from Lemma 23

We will use the conclusion of Lemma 23 to contradict the hardness assumption, and show that there is a nondeterministic circuit $A$ of size $2^{\beta\ell}$ that computes $f$ . The circuit $A$ will be hardwired with $\gamma_{1},\gamma_{2}$ , $t_{1},\ldots,t_{r}$ , $y_{1},\ldots,y_{r}$ and $\hat{f}(y_{1}),\ldots,\hat{f}(y_{r})$ . Given input $x\in\{0,1\}^{\ell}$ (which we can think of as $x\in\mathbb{F}_{q}^{d}\subseteq H^{d}$ so that it is an input to $\hat{f}$ ) the nondeterministic circuit $A$ will guess a polynomial $p:\mathbb{F}_{q}\to\mathbb{F}_{q}$ of degree $\hat{h}\cdot r$ , (by guessing its coefficients) and do the following:

$\blacksquare$

Verify that for every $j\in[r]$ , $p(t_{j})=\hat{f}(y_{j})$ .
$\blacksquare$

Construct the nondeterministic circuit $D_{x}(t,i)=D(C_{x}(t),i,\mathsf{SExt}(p(t),i))$ , which is of size ${\mathsf{poly}}(s,\log q)$ .
$\blacksquare$

Goldwasser and Sipser [19] showed that there is an ${\mathsf{AM}}$ -protocol that given a circuit $C$ of size $s$ and $\gamma_{2}>e^{1/s}\cdot\gamma_{1}$ solves the promise problem of distinguishing whether $\Pr[C(U_{n})=1]\geq\gamma_{2}$ or $\Pr[C(U_{n})=1]\leq\gamma_{1}$ . It is standard that this protocol extends to the case where $C$ is nondeterministic.¹⁴¹⁴14This follows as the ${\mathsf{AM}}$ protocol of Goldwasser and Sipser [19] works in the framework of “constant round” ${\mathsf{AM}}$ -protocols, which allows Merlin to speak many times, and such protocols are later collapsed to a 2-message public coin ${\mathsf{AM}}$ protocol. See precise statement in Section 2.7. Using Adleman’s argument that ${\mathsf{AM}}\subseteq{\mathsf{NP}}/{\mathsf{poly}}$ , our size ${\mathsf{poly}}(s)$ nondeterministic circuit $A$ , can indeed verify that $\Pr[D_{x}(T,V)=1]\geq\gamma_{2}$ .
$\blacksquare$

If all verification steps pass, then $A$ outputs $p(0)$ .

Overall, using Lemma 23, this gives a nondeterministic circuit $A$ that computes $f$ .¹⁵¹⁵15In fact, the circuit that we construct is a “single-valued nondeterministic circuit”. This means that on every input $x$ there is an accepting nondeterministic guess that outputs $f(x)$ , and there does not exist an accepting nondeterministic guess that outputs a value different than $f(x)$ . This circuit is of size ${\mathsf{poly}}(s,\log q)=s^{c_{0}}$ for some universal constant $c_{0}$ , and we have that $s^{c_{0}}=h^{d\beta}=2^{\beta\ell}$ as required.

3.3.2 Proof of Lemma 23

A calculation gives $\gamma_{2}>e^{\frac{1}{4s}}\cdot\gamma_{1}$ . Specifically, let $\eta=\frac{1}{s}$ , and recall that $p_{2}>e^{\eta}\cdot p_{1}+\rho>\max(\rho,e^{\eta}\cdot p_{1})$ , implying $\epsilon=\frac{\rho\eta}{100}\leq\frac{p_{2}\eta}{100}$ . Using that $\forall x\in[0,1]$ , $1+x\leq e^{x}\leq 1+3x$ and $1-x\leq e^{-x}\leq 1-x/3$ , we get:

\frac{\gamma_{2}}{\gamma_{1}}=\frac{p_{2}-\epsilon}{p_{1}+4\epsilon}>\frac{p_{% 2}-\frac{p_{2}\eta}{100}}{p_{2}\cdot e^{-\eta}+\frac{4p_{2}\eta}{100}}

=\frac{p_{2}\cdot(1-\frac{\eta}{100})}{p_{2}\cdot(e^{-\eta}+\frac{4\eta}{100})% }\geq\frac{e^{-\frac{3\eta}{100}}}{1-\frac{\eta}{3}+\frac{4\eta}{100}}\geq% \frac{e^{-\frac{3\eta}{100}}}{e^{-(\frac{\eta}{3}-\frac{4\eta}{100})}}=e^{% \frac{\eta}{3}-\frac{4\eta}{100}-\frac{3\eta}{100}}>e^{\frac{\eta}{4}}.

We will use the probabilistic method to show the existence of $t_{1},\ldots,t_{r}$ and $y_{1},\ldots y_{r}$ . For this purpose we consider a probability space in which we choose $y_{1},\ldots,y_{r}\leftarrow\mathbb{F}_{q}^{d}$ and distinct $t_{1},\ldots,t_{r}\leftarrow\mathbb{F}_{q}\setminus\left\{{0}\right\}$ . For every $x\in\mathbb{F}_{q}^{d}$ we define (the random variable) $C_{x}=C_{\genfrac{}{}{0.0pt}{}{0,t_{1},\ldots,t_{r}}{x,y_{1},\ldots,y_{r}}}$ . It is standard that the random variables $(C_{x}(t))_{t\neq 0}$ are $r$ -wise independent.¹⁶¹⁶16Note that this holds even though one of the points on the curve (specifically $C_{x}(0)$ ) is fixed to $x$ , and is not random. Indeed this is where we can see the advantage of using curves over lines, as they give us $r$ -wise independence, even when some points are fixed. Another advantage is that by increasing $r$ , we get more independence, which allows us to use stronger tail inequalities. Lemma 23 follows from the following claim by a union bound over the $q^{d}$ choices of $x\in\mathbb{F}_{q}^{d}$ .

Claim 24.

For every $x\in\mathbb{F}_{q}^{d}$ , except for probability $\frac{1}{5q^{d}}$ over the choice of $t_{1},\ldots,t_{r}$ , $y_{1},\ldots,y_{r}$ we have that $\hat{p}_{x}=\hat{f}\circ C_{x}$ satisfies:

$\blacksquare$

For every $j\in[r]$ , $\hat{p}_{x}(t_{j})=\hat{f}(y_{j})$ , and $\Pr[D(C_{x}(T),V,\mathsf{SExt}(\hat{p}_{x}(T),V))=1]\geq\gamma_{2}$ .
$\blacksquare$

For every degree $\hat{h}\cdot r$ polynomial $p\neq\hat{p}_{x}$ such that $\Pr[D(C_{x}(T),V,\mathsf{SExt}(p(T),V))=1]>\gamma_{1}$ , there exists a $j\in[r]$ such that $p(t_{j})\neq\hat{f}(y_{j})$ ,

Proof of Claim 24

By a standard application of an $r$ -wise independent tail inequality [10] we get that for every $x\in\mathbb{F}_{q}^{d}$ , the values $p_{1}=\Pr[D(W,V,R)=1]$ and $p_{2}=\Pr[D(W,V,\mathsf{SExt}(\hat{f}(W),V))=1]$ (which are probabilities over the choice $W\leftarrow\mathbb{F}_{q}^{d}$ ) are approximated by values $p_{x,1},p_{x,2}$ (which are defined below by replacing $W$ with $C_{x}(T)$ for $T\leftarrow\mathbb{F}_{q}\setminus\left\{{0}\right\}$ ). This is stated formally in the next claim.

Claim 25 (Sampling preserves $p_{1}$ and $p_{2}$ ).

For every $x\in\mathbb{F}_{q}^{d}$ , except for probability $\frac{1}{10q^{d}}$ over the choice of $t_{1},\ldots,t_{r}$ , $y_{1},\ldots,y_{r}$ we have that:

$\blacksquare$

$p_{x,1}=\Pr[D(C_{x}(T),V,R)=1]\leq p_{1}+\epsilon$ , and
$\blacksquare$

$p_{x,2}=\Pr[D(C_{x}(T),V,\mathsf{SExt}(\hat{f}(C_{x}(T)),V))=1]\geq p_{2}-% \epsilon=\gamma_{2}>\gamma_{1}$ .

The proof of Claim 25 follows by a straightforward application of the $r$ -wise independent tail inequality of [10] (stated in Theorem 18). The calculation appears in the full version.

We continue with the proof of Claim 24. Fix some $x\in\mathbb{F}_{q}^{d}$ . By Claim 25 with probability $1-\frac{1}{10q^{d}}$ over the choices of $t_{1},\ldots,t_{r}$ and $y_{1},\ldots,y_{r}$ we have that $p_{x,1}\leq p_{1}+\epsilon$ and $p_{x,2}\geq p_{2}-\epsilon$ . Fix some specific choice of $t_{1},\ldots,t_{r}$ and $y_{1},\ldots,y_{r}$ which satisfies this condition. This fixing is done so that $C_{x}$ (which is determined by $t_{1},\ldots,t_{r}$ , $y_{1},\ldots,y_{r}$ and $x$ ) is fixed to a specific polynomial. We define:

\mathsf{List}_{x}=\left\{{p:\mathbb{F}_{q}\to\mathbb{F}_{q}:p\mbox{ is of % degree $\hat{h}\cdot r$, and}\Pr[D(C_{x}(T),V,\mathsf{SExt}(p(T),V))=1]>\gamma% _{1}}\right\}.

We have seen that $\hat{p}_{x}=\hat{f}\circ C_{x}\in\mathsf{List}_{x}$ . For every polynomial $p\in\mathsf{List}_{x}$ we have that:

\Pr[D(C_{x}(T),V,\mathsf{SExt}(p(T),V))=1]-\Pr[D(C_{x}(T),V,R)=1]

>\gamma_{1}-p_{x,1}>(p_{1}+4\epsilon)-(p_{1}+\epsilon)=3\epsilon.

As $T$ is uniform over $\mathbb{F}_{q}\setminus\left\{{0}\right\}$ and independent of $(V,R)$ , by an averaging argument, it follows that there exist a subset $V_{x,p}\subseteq\mathbb{F}_{q}\setminus\left\{{0}\right\}$ of size $\epsilon(q-1)$ such that for every $t\in V_{x,p}$ , we have that:

\Pr[D(C_{x}(t),V,\mathsf{SExt}(p(t),V))=1]-\Pr[D(C_{x}(t),V,R)=1]>2\epsilon.

For every $t\in\mathbb{F}_{q}\setminus\left\{{0}\right\}$ we define:

\mathsf{List}_{x,t}=\left\{{a\in\mathbb{F}_{q}:\Pr[D(C_{x}(t),V,\mathsf{SExt}(% a,V))=1]-\Pr[D(C_{x}(t),V,R)=1]>\epsilon}\right\},

so that for $t\in V_{x,p}$ , we have that $p(t)\in\mathsf{List}_{x,t}$ . As $\mathsf{SExt}$ is a $(k,\epsilon)$ -strong extractor for $k=m+2\log(1/\epsilon)$ , we have that for every $t\in\mathbb{F}_{q}\setminus\left\{{0}\right\}$ , $|\mathsf{List}_{x,t}|\leq 2^{k}$ (as otherwise the uniform distribution on $\mathsf{List}_{x,t}$ violates the guarantee of strong extractors (see Definition 12) with respect to the distinguisher $D_{t}(i,z)=D(C_{x}(t),i,z)$ ).

We now have the setup of the celebrated Reed-Solomon list-decoding algorithm of Sudan [35] (stated formally in Theorem 11). More precisely, there are $\mathsf{prs}=(q-1)\cdot 2^{k}$ points (namely, all pairs $(t,y)$ for $t\in\mathbb{F}_{q}\setminus\left\{{0}\right\}$ and $y\in\mathsf{List}_{x,t}$ ) such that every degree $\mathsf{deg}=\hat{h}\cdot r$ polynomial $p\in\mathsf{List}_{x}$ , passes through $\mathsf{agr}=\epsilon\cdot(q-1)$ of the points. By Sudan’s theorem, if $\mathsf{agr}>\sqrt{2\cdot\mathsf{prs}\cdot\mathsf{deg}}$ then $|\mathsf{List}_{x}|\leq\frac{2\mathsf{prs}}{\mathsf{agr}}=\frac{2\cdot 2^{k}}{% \epsilon}=\frac{2^{m+1}}{\epsilon^{3}}$ .¹⁷¹⁷17Note that here (similar to [37, 6] and in contrast to [36]) we only use combinatorial list-decoding, and do not rely on the efficiency of Sudan’s algorithm, and we could have used a combinatorial list-decoding result like the Johnson bound. The requirement that $\mathsf{agr}>\sqrt{2\cdot\mathsf{prs}\cdot\mathsf{deg}}$ translates to

q-1>\frac{2\cdot 2^{k}\cdot\hat{h}\cdot r}{\epsilon^{2}}=\frac{2\cdot 2^{m}% \cdot\hat{h}\cdot r}{\epsilon^{4}}.

Recall that $\hat{h}=h\cdot d\leq s^{2}$ , $r\leq s$ , $\epsilon=\frac{\rho}{100\cdot s}$ , and we have that $s\leq\frac{1}{\rho}$ . We can choose the constant $c_{q}$ to be sufficiently large so that $q=\frac{2^{m}}{\rho^{c_{q}}}$ satisfies the requirement.

Using that $(t_{1},\ldots,t_{r})$ and $C_{x}$ are independent to trim the list

For every $x\in\mathbb{F}_{q}^{d}$ , in the probability space of choosing $t_{1},\ldots,t_{r}$ and $y_{1},\ldots,y_{r}$ , the quantities $p_{x,1},p_{x,2}$ , and the set $\mathsf{List}_{x}$ are random variables that depend on the choice of $t_{1},\ldots,t_{r}$ and $y_{1},\ldots,y_{r}$ . A crucial observation is that the random variables $p_{x,1},p_{x,2}$ and $\mathsf{List}_{x}$ , depend only on the “shape” of the curve $C_{x}$ . More formally, $p_{x,1},p_{x,2}$ and $\mathsf{List}_{x}$ are determined by the set $\left\{{(t,C_{x}(t)):t\in\mathbb{F}_{q}}\right\}$ which is determined by the polynomial $C_{x}$ . However, for every specific fixing of the polynomial $C_{x}$ , every choice of distinct values for $t_{1},\ldots,t_{r}\in\mathbb{F}_{q}\setminus\left\{{0}\right\}$ is still possible, and equally likely. This gives that the random variable $C_{x}$ is independent of the random variable $(t_{1},\ldots,t_{r})$ .

Consider conditioning the probability space of choosing $t_{1},\ldots,t_{r}$ and $y_{1},\ldots,y_{r}$ , on a specific fixing of $C_{x}$ , such that $p_{x,1}\leq p_{1}+\epsilon$ and $p_{x,2}\geq p_{2}-\epsilon$ , so that by the previous discussion, $|\mathsf{List}_{x}|\leq\frac{2^{m+1}}{\epsilon^{3}}$ .

By Claim 25 such a fixing occurs with probability $1-\frac{1}{10q^{d}}$ . We’ve seen that having conditioned on a specific choice of $C_{x}$ , the set $\mathsf{List}_{x}$ is fixed, and yet $(t_{1},\ldots,t_{r})$ are distributed like $r$ random distinct values in $\mathbb{F}_{q}\setminus\left\{{0}\right\}$ . We also have that $\hat{p}_{x}\in\mathsf{List}_{x}$ , and that for every $j\in[r]$ , $\hat{p}_{x}(t_{j})=\hat{f}(C_{x}(t_{j}))=\hat{f}(y_{j})$ .

Every $p\in\mathsf{List}_{x}$ that is different from $\hat{p}_{x}$ agrees with $\hat{p}_{x}$ in at most $\hat{h}\cdot r$ elements. Therefore, the probability (in this conditioned probability space) that $p$ and $\hat{p}_{x}$ agree on the (still random) $t_{1},\ldots,t_{r}$ is at most $\left(\frac{\hat{h}\cdot r}{q-1}\right)^{r}$ . We will do a union bound against all $p\in\mathsf{List}_{x}$ such that $p\neq\hat{p}_{x}$ , and there are at most $|\mathsf{List}_{x}|\leq\frac{2^{m+1}}{\epsilon^{3}}$ such polynomials. We obtain that the probability that there exists $p\in\mathsf{List}_{x}$ such that $p\neq\hat{p}_{x}$ , and yet for every $j\in[r]$ , $p(x_{j})=\hat{p}_{x}(t_{j})$ , is at most

\frac{2^{m+1}}{\epsilon^{3}}\cdot\left(\frac{\hat{h}\cdot r}{q-1}\right)^{r}% \leq\frac{2^{m+1}\cdot 100^{3}}{\rho^{6}}\cdot\left(\frac{2}{\rho^{3}\cdot q}% \right)^{c_{r}\cdot d}\leq\frac{2^{m+1}\cdot 100^{3}}{\rho^{6}}\cdot\left(% \frac{\rho}{2^{m}}\right)^{c_{r}\cdot d}\leq\frac{1}{10q^{d}},

where the inequalities above follow because $\epsilon=\frac{\rho}{100s}$ , $\rho\leq\frac{1}{s}$ , $\hat{h}\cdot r=hdr=s\cdot c_{r}\cdot d^{2}\leq s^{3}\leq\frac{1}{\rho^{3}}$ , and then we can take $c_{q}\geq 5$ , so that for $q=\frac{2^{m}}{\rho^{c_{q}}}$ , we have that $\frac{2}{\rho^{3}\cdot q}\leq\frac{\rho}{2^{m}}$ . The final inequality follows for a sufficiently large constant $c_{r}$ .

Overall, we have that except for probability $\frac{1}{10q^{d}}+\frac{1}{10q^{d}}=\frac{1}{5q^{d}}$ over the choice of $t_{1},\ldots,t_{r}$ and $y_{1},\ldots,y_{r}$ , $\Pr[D(C_{x}(T),V,\mathsf{SExt}(\hat{p}_{x}(T),V))=1]\geq\gamma_{2}$ and for every degree $\hat{h}\cdot r$ polynomial $p\neq\hat{p}_{x}$ such that
$\Pr[D(C_{x}(T),V,\mathsf{SExt}(p(T),V))=1]>\gamma_{1}$ , there exist $j\in[r]$ such that $p(t_{j})\neq\hat{p}_{x}(t_{j})=\hat{f}(y_{j})$ , and this completes the proof of Claim 24.

References

[1] B. Applebaum, S. Artemenko, R. Shaltiel, and G. Yang. Incompressible functions, relative-error extractors, and the power of nondeterministic reductions. In 30th Conference on Computational Complexity, pages 582–600, 2015. doi:10.4230/LIPIcs.CCC.2015.582.
[2] S. Artemenko, R. Impagliazzo, V. Kabanets, and R. Shaltiel. Pseudorandomness when the odds are against you. In 31st Conference on Computational Complexity, CCC, volume 50, pages 9:1–9:35, 2016. doi:10.4230/LIPIcs.CCC.2016.9.
[3] S. Artemenko and R. Shaltiel. Pseudorandom generators with optimal seed length for non-boolean poly-size circuits. In Symposium on Theory of Computing, STOC, pages 99–108, 2014. doi:10.1145/2591796.2591846.
[4] V. Arvind and J. Köbler. New lowness results for $\mbox{ZPP}^{NP}$ and other complexity classes. J. Comput. Syst. Sci., 65(2):257–277, 2002. doi:10.1006/jcss.2002.1835.
[5] M. Ball, D. Dachman-Soled, and J. Loss. (nondeterministic) hardness vs. non-malleability. In Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, volume 13507, pages 148–177, 2022. doi:10.1007/978-3-031-15802-5_6.
[6] M. Ball, E. Goldin, D. Dachman-Soled, and S. Mutreja. Extracting randomness from samplable distributions, revisited. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 1505–1514, 2023. doi:10.1109/FOCS57990.2023.00092.
[7] M. Ball, R. Shaltiel, and J. Silbak. Non-malleable codes with optimal rate for poly-size circuits. In Advances in Cryptology - EUROCRYPT, volume 14654 of Lecture Notes in Computer Science, pages 33–54, 2024. doi:10.1007/978-3-031-58737-5_2.
[8] M. Ball, R. Shaltiel, and J. Silbak. Extractor for samplable distributions with low min-entropy. To appear in STOC, 2025.
[9] B. Barak, S. J. Ong, and S. P. Vadhan. Derandomization in cryptography. SIAM J. Comput., 37(2):380–400, 2007. doi:10.1137/050641958.
[10] M. Bellare and J. Rompel. Randomness-efficient oblivious sampling. In 35th Annual Symposium on Foundations of Computer Science, pages 276–287, 1994. doi:10.1109/SFCS.1994.365687.
[11] N. Bitansky and V. Vaikuntanathan. A note on perfect correctness by derandomization. In Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, volume 10211, pages 592–606, 2017. doi:10.1007/978-3-319-56614-6_20.
[12] L. Chen and R. Tell. When arthur has neither random coins nor time to spare: Superfast derandomization of proof systems. Electron. Colloquium Comput. Complex., TR22-057, 2022. URL: https://eccc.weizmann.ac.il/report/2022/057.
[13] Y. Dodis and Y. Yu. Overcoming weak expectations. In Theory of Cryptography – 10th Theory of Cryptography Conference, TCC, volume 7785 of Lecture Notes in Computer Science, pages 1–22, 2013. doi:10.1007/978-3-642-36594-2_1.
[14] D. Doron, D. Moshkovitz, J. Oh, and D. Zuckerman. Nearly optimal pseudorandomness from hardness. J. ACM, 69(6):43:1–43:55, 2022. doi:10.1145/3555307.
[15] Andrew Drucker. Nondeterministic direct product reductions and the success probability of SAT solvers. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 736–745, 2013. doi:10.1109/FOCS.2013.84.
[16] C. Dwork, F. McSherry, K. Nissim, and A. D. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC, volume 3876 of Lecture Notes in Computer Science, pages 265–284. Springer, 2006. doi:10.1007/11681878_14.
[17] U. Feige and C. Lund. On the hardness of computing the permanent of random matrices. Computational Complexity, 6(2):101–132, 1997. doi:10.1007/BF01262928.
[18] O. Goldreich and A. Wigderson. Derandomization that is rarely wrong from short advice that is typically good. In APPROX-RANDOM, pages 209–223, 2002. URL: http://link.springer.de/link/service/series/0558/bibs/2483/24830209.htm.
[19] S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pages 59–68, 1986. doi:10.1145/12130.12137.
[20] V. Guruswami, C. Umans, and S. P. Vadhan. Unbalanced expanders and randomness extractors from parvaresh-vardy codes. In CCC, pages 96–108, 2007.
[21] Dan Gutfreund, Ronen Shaltiel, and Amnon Ta-Shma. Uniform hardness versus randomness tradeoffs for arthur-merlin games. Computational Complexity, 12(3-4):85–130, 2003. doi:10.1007/s00037-003-0178-7.
[22] P. Hubácek, M. Naor, and E. Yogev. The journey from NP to TFNP hardness. In 8th Innovations in Theoretical Computer Science Conference, ITCS, volume 67, pages 60:1–60:21, 2017. doi:10.4230/LIPIcs.ITCS.2017.60.
[23] R. Impagliazzo, L. A. Levin, and M. Luby. Pseudo-random generation from one-way functions (extended abstracts). In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 12–24, 1989. doi:10.1145/73007.73009.
[24] R. Impagliazzo and A. Wigderson. $\mathit{P}=\mathit{BPP}$ if $E$ requires exponential circuits: Derandomizing the XOR lemma. In STOC, pages 220–229, 1997.
[25] J. Kinne, D. van Melkebeek, and R. Shaltiel. Pseudorandom generators and typically-correct derandomization. In APPROX-RANDOM, pages 574–587, 2009. doi:10.1007/978-3-642-03685-9_43.
[26] A. Klivans and D. van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput., 31(5):1501–1526, 2002. doi:10.1137/S0097539700389652.
[27] F. Li and D. Zuckerman. Improved extractors for recognizable and algebraic sources. In Dimitris Achlioptas and László A. Végh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, volume 145 of LIPIcs, pages 72:1–72:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.72.
[28] P. Bro Miltersen and N. V. Vinodchandran. Derandomizing arthur-merlin games using hitting sets. Computational Complexity, 14(3):256–279, 2005. doi:10.1007/s00037-005-0197-7.
[29] R. Shaltiel. Weak derandomization of weak algorithms: explicit versions of yao’s lemma. In CCC, 2009. doi:10.1007/S00037-011-0006-4.
[30] R. Shaltiel and J. Silbak. Explicit codes for poly-size circuits and functions that are hard to sample on low entropy distributions. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC, pages 2028–2038, 2024. doi:10.1145/3618260.3649735.
[31] R. Shaltiel and C. Umans. Simple extractors for all min-entropies and a new pseudorandom generator. J. ACM, 52(2):172–216, 2005. doi:10.1145/1059513.1059516.
[32] R. Shaltiel and C. Umans. Pseudorandomness for approximate counting and sampling. Computational Complexity, 15(4):298–341, 2006. doi:10.1007/s00037-007-0218-9.
[33] R. Shaltiel and C. Umans. Low-end uniform hardness versus randomness tradeoffs for am. SIAM J. Comput., 39(3):1006–1037, 2009. doi:10.1137/070698348.
[34] Ronen Shaltiel. Multiplicative extractors for samplable distributions. Electron. Colloquium Comput. Complex., TR24-168, 2024. URL: https://eccc.weizmann.ac.il/report/2024/168.
[35] M. Sudan. Decoding of Reed Solomon codes beyond the error-correction bound. Journal of Complexity, 13, 1997.
[36] M. Sudan, L. Trevisan, and S. P. Vadhan. Pseudorandom generators without the xor lemma. J. Comput. Syst. Sci., 62(2):236–266, 2001. doi:10.1006/JCSS.2000.1730.
[37] L. Trevisan and S. P. Vadhan. Extracting randomness from samplable distributions. In 41st Annual Symposium on Foundations of Computer Science, pages 32–42, 2000. doi:10.1109/SFCS.2000.892063.

[bib.bib1] [1] B. Applebaum, S. Artemenko, R. Shaltiel, and G. Yang. Incompressible functions, relative-error extractors, and the power of nondeterministic reductions. In 30th Conference on Computational Complexity, pages 582–600, 2015. doi:10.4230/LIPIcs.CCC.2015.582.

[bib.bib2] [2] S. Artemenko, R. Impagliazzo, V. Kabanets, and R. Shaltiel. Pseudorandomness when the odds are against you. In 31st Conference on Computational Complexity, CCC, volume 50, pages 9:1–9:35, 2016. doi:10.4230/LIPIcs.CCC.2016.9.

[bib.bib3] [3] S. Artemenko and R. Shaltiel. Pseudorandom generators with optimal seed length for non-boolean poly-size circuits. In Symposium on Theory of Computing, STOC, pages 99–108, 2014. doi:10.1145/2591796.2591846.

[bib.bib4] [4] V. Arvind and J. Köbler. New lowness results for $\mbox{ZPP}^{NP}$ and other complexity classes. J. Comput. Syst. Sci., 65(2):257–277, 2002. doi:10.1006/jcss.2002.1835.

[bib.bib5] [5] M. Ball, D. Dachman-Soled, and J. Loss. (nondeterministic) hardness vs. non-malleability. In Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, volume 13507, pages 148–177, 2022. doi:10.1007/978-3-031-15802-5_6.

[bib.bib6] [6] M. Ball, E. Goldin, D. Dachman-Soled, and S. Mutreja. Extracting randomness from samplable distributions, revisited. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 1505–1514, 2023. doi:10.1109/FOCS57990.2023.00092.

[bib.bib7] [7] M. Ball, R. Shaltiel, and J. Silbak. Non-malleable codes with optimal rate for poly-size circuits. In Advances in Cryptology - EUROCRYPT, volume 14654 of Lecture Notes in Computer Science, pages 33–54, 2024. doi:10.1007/978-3-031-58737-5_2.

[bib.bib8] [8] M. Ball, R. Shaltiel, and J. Silbak. Extractor for samplable distributions with low min-entropy. To appear in STOC, 2025.

[bib.bib9] [9] B. Barak, S. J. Ong, and S. P. Vadhan. Derandomization in cryptography. SIAM J. Comput., 37(2):380–400, 2007. doi:10.1137/050641958.

[bib.bib10] [10] M. Bellare and J. Rompel. Randomness-efficient oblivious sampling. In 35th Annual Symposium on Foundations of Computer Science, pages 276–287, 1994. doi:10.1109/SFCS.1994.365687.

[bib.bib11] [11] N. Bitansky and V. Vaikuntanathan. A note on perfect correctness by derandomization. In Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, volume 10211, pages 592–606, 2017. doi:10.1007/978-3-319-56614-6_20.

[bib.bib12] [12] L. Chen and R. Tell. When arthur has neither random coins nor time to spare: Superfast derandomization of proof systems. Electron. Colloquium Comput. Complex., TR22-057, 2022. URL: https://eccc.weizmann.ac.il/report/2022/057.

[bib.bib13] [13] Y. Dodis and Y. Yu. Overcoming weak expectations. In Theory of Cryptography – 10th Theory of Cryptography Conference, TCC, volume 7785 of Lecture Notes in Computer Science, pages 1–22, 2013. doi:10.1007/978-3-642-36594-2_1.

[bib.bib14] [14] D. Doron, D. Moshkovitz, J. Oh, and D. Zuckerman. Nearly optimal pseudorandomness from hardness. J. ACM, 69(6):43:1–43:55, 2022. doi:10.1145/3555307.

[bib.bib15] [15] Andrew Drucker. Nondeterministic direct product reductions and the success probability of SAT solvers. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 736–745, 2013. doi:10.1109/FOCS.2013.84.

[bib.bib16] [16] C. Dwork, F. McSherry, K. Nissim, and A. D. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC, volume 3876 of Lecture Notes in Computer Science, pages 265–284. Springer, 2006. doi:10.1007/11681878_14.

[bib.bib17] [17] U. Feige and C. Lund. On the hardness of computing the permanent of random matrices. Computational Complexity, 6(2):101–132, 1997. doi:10.1007/BF01262928.

[bib.bib18] [18] O. Goldreich and A. Wigderson. Derandomization that is rarely wrong from short advice that is typically good. In APPROX-RANDOM, pages 209–223, 2002. URL: http://link.springer.de/link/service/series/0558/bibs/2483/24830209.htm.

[bib.bib19] [19] S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pages 59–68, 1986. doi:10.1145/12130.12137.

[bib.bib20] [20] V. Guruswami, C. Umans, and S. P. Vadhan. Unbalanced expanders and randomness extractors from parvaresh-vardy codes. In CCC, pages 96–108, 2007.

[bib.bib21] [21] Dan Gutfreund, Ronen Shaltiel, and Amnon Ta-Shma. Uniform hardness versus randomness tradeoffs for arthur-merlin games. Computational Complexity, 12(3-4):85–130, 2003. doi:10.1007/s00037-003-0178-7.

[bib.bib22] [22] P. Hubácek, M. Naor, and E. Yogev. The journey from NP to TFNP hardness. In 8th Innovations in Theoretical Computer Science Conference, ITCS, volume 67, pages 60:1–60:21, 2017. doi:10.4230/LIPIcs.ITCS.2017.60.

[bib.bib23] [23] R. Impagliazzo, L. A. Levin, and M. Luby. Pseudo-random generation from one-way functions (extended abstracts). In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 12–24, 1989. doi:10.1145/73007.73009.

[bib.bib24] [24] R. Impagliazzo and A. Wigderson. $\mathit{P}=\mathit{BPP}$ if $E$ requires exponential circuits: Derandomizing the XOR lemma. In STOC, pages 220–229, 1997.

[bib.bib25] [25] J. Kinne, D. van Melkebeek, and R. Shaltiel. Pseudorandom generators and typically-correct derandomization. In APPROX-RANDOM, pages 574–587, 2009. doi:10.1007/978-3-642-03685-9_43.

[bib.bib26] [26] A. Klivans and D. van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput., 31(5):1501–1526, 2002. doi:10.1137/S0097539700389652.

[bib.bib27] [27] F. Li and D. Zuckerman. Improved extractors for recognizable and algebraic sources. In Dimitris Achlioptas and László A. Végh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, volume 145 of LIPIcs, pages 72:1–72:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.72.

[bib.bib28] [28] P. Bro Miltersen and N. V. Vinodchandran. Derandomizing arthur-merlin games using hitting sets. Computational Complexity, 14(3):256–279, 2005. doi:10.1007/s00037-005-0197-7.

[bib.bib29] [29] R. Shaltiel. Weak derandomization of weak algorithms: explicit versions of yao’s lemma. In CCC, 2009. doi:10.1007/S00037-011-0006-4.

[bib.bib30] [30] R. Shaltiel and J. Silbak. Explicit codes for poly-size circuits and functions that are hard to sample on low entropy distributions. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC, pages 2028–2038, 2024. doi:10.1145/3618260.3649735.

[bib.bib31] [31] R. Shaltiel and C. Umans. Simple extractors for all min-entropies and a new pseudorandom generator. J. ACM, 52(2):172–216, 2005. doi:10.1145/1059513.1059516.

[bib.bib32] [32] R. Shaltiel and C. Umans. Pseudorandomness for approximate counting and sampling. Computational Complexity, 15(4):298–341, 2006. doi:10.1007/s00037-007-0218-9.

[bib.bib33] [33] R. Shaltiel and C. Umans. Low-end uniform hardness versus randomness tradeoffs for am. SIAM J. Comput., 39(3):1006–1037, 2009. doi:10.1137/070698348.

[bib.bib34] [34] Ronen Shaltiel. Multiplicative extractors for samplable distributions. Electron. Colloquium Comput. Complex., TR24-168, 2024. URL: https://eccc.weizmann.ac.il/report/2024/168.

[bib.bib35] [35] M. Sudan. Decoding of Reed Solomon codes beyond the error-correction bound. Journal of Complexity, 13, 1997.

[bib.bib36] [36] M. Sudan, L. Trevisan, and S. P. Vadhan. Pseudorandom generators without the xor lemma. J. Comput. Syst. Sci., 62(2):236–266, 2001. doi:10.1006/JCSS.2000.1730.

[bib.bib37] [37] L. Trevisan and S. P. Vadhan. Extracting randomness from samplable distributions. In 41st Annual Symposium on Foundations of Computer Science, pages 32–42, 2000. doi:10.1109/SFCS.2000.892063.

Multiplicative Extractors for Samplable Distributions111In memory of Luca Trevisan.

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Multiplicative Pseudorandomness

Definition 1 (Pseudorandomness with respect to a relation).

Definition 2 (Pseudorandom generators and extractors w.r.t. a relation).

A motivating example: using seedless extractors to select keys for cryptographic protocols

1.2 Extractors for Samplable Distributions

Hardness assumptions against various types of nondeterministic circuits

Previous work on extractors for samplable distributions

Theorem 3 ([37]).

1.3 Our Results

1.3.1 Multiplicative Extractors for Samplable Distributions

Theorem 4 (Multiplicative extractors for samplable distributions).

The role of our extractor in recent extractor for low min-entropy of [8]

Extracting more bits w.r.t. a multiplicative relation with two parameters

Theorem 5 (Multiplicative extractors with larger output length).

1.3.2 Consequences and Necessary Assumptions for Extractors for Samplable Distributions

Hardness assumptions for extractors for samplable distributions

Extractors for samplable distributions and seed-extending PRGs

Paper Organization

2 Preliminaries

Probabilistic notation

Relations from the introduction

Definition 6 (Definitions of relations from Section 1).

2.1 Samplable Distributions and Postselection

Samplable distributions

Definition 7 (Samplable distributions).

Samplable distributions with postselection

Definition 8 (Samplable distributions with postselection).

Distributions samplable by deterministic circuits with postselection by nondeterministic circuits

Recognizable distributions

2.2 Definition of Circuits of Various Types

Definition 9 (randomized circuits, nondeterministic circuits, oracle circuits and Σi-circuits).

2.3 Hardness Assumptions

Definition 10 (𝖤 is hard for exponential size circuits).

2.4 Sudan’s List-Decoding Algorithm

Theorem 11 (Sudan’s list-decoding algorithm [35]).

2.5 Seeded Extractors

Definition 12 (Seeded extractors).

Theorem 13 (Leftover hash lemma [23]).

Theorem 14 ([20]).

2.6 The Low Degree Extension

Lemma 15.

2.7 The Goldwasser-Sipser AM Protocol and Consequences

Definition 16 (The nondeterministic large set promise problem).

Theorem 17 (Goldwasser and Sipser [19]).

2.8 A Tail Inequality

Theorem 18 (r-wise independent tail inequality [10]).

3 Technique

3.1 A Brief Overview of the Approach Used in the Previous Work

Extractors from functions that are very hard functions on average

Lemma 19 (Extractors from very hard on average functions [37]).

Bypassing the barrier of obtaining functions that are very hard on average

3.2 Multiplicative Extractors from Seed-Extending Multiplicative PRGs

Lemma 20 (Multiplicative extractors from Multiplicative PRGs).

Proof sketch for Lemma 20

3.3 A Construction of Seed-Extending Multiplicative PRGs

Theorem 21 (Multiplicative PRG).

3.3.1 Proof of Theorem 21

Definition 22 (Degree r curve passing through given r+1 points).

Lemma 23.

Showing that Theorem 21 follows from Lemma 23

3.3.2 Proof of Lemma 23

Claim 24.

Proof of Claim 24

Claim 25 (Sampling preserves p1 and p2).

Using that (𝒕𝟏,…,𝒕𝒓) and 𝑪𝒙 are independent to trim the list

References

Multiplicative Extractors for Samplable Distributions¹¹1In memory of Luca Trevisan.

Definition 9 (randomized circuits, nondeterministic circuits, oracle circuits and $\Sigma_{i}$ -circuits).

Definition 10 ( ${\mathsf{E}}$ is hard for exponential size circuits).

Theorem 18 ( $r$ -wise independent tail inequality [10]).

Definition 22 (Degree $r$ curve passing through given $r+1$ points).

Claim 25 (Sampling preserves $p_{1}$ and $p_{2}$ ).

Using that $(t_{1},\ldots,t_{r})$ and $C_{x}$ are independent to trim the list