Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions as a possible solution to the problem of extracting 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 \ge 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$ that has $H_{\infty}(X) \ge (1-\alpha) \cdot n$, $\mathsf{Ext}(X)$ is $\epsilon$-close to uniform for $\epsilon=\frac{1}{n^c}$, and furthermore, $\mathsf{Ext}$ is computable in time $\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 $\E=\DTIME(2^{O(n)})$ that requires size $2^{\beta n}$ nondeterministic circuits.
\smallskip \noindent
In this paper we give an alternative proof of this result with the following advantages:
\begin{itemize}
\item Our extractors have ``multiplicative error''. More specifically, it is guaranteed that for every event $A \subseteq \{0,1\}^m$, $\Pr[\mathsf{Ext}(X) \in A] \le (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] \le \epsilon +\Pr[U_m \in A]$).
Consequently, unlike the 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.
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.
\item 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.)
\end{itemize}
Trevisan and Vadhan also asked whether lower bounds against nondeterministic circuits are \emph{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.
