This is closely related to a challenge from the early 1990s, which calls for more efficient and hopefully also simpler constructions of pseudorandom generator based on one-way functions. Let me reproduce here my opening comment on a related work (2011).
After two decades of research, the barrier envisioned by Johan Hastad (in a private discussion with me) has been reached, and now the goal is to break it. The barrier that I refer to is a seed length of $O(n^3)$ for a PRG (pseudorandom generator) constructed based on a OWF (one-way function) that operates on $n$-bit long strings. The barrier arises from the paradigm of ``smoothing'' the random variables that arise from applying the OWF to a uniformly distributed $n$-bit long string, where smoothing means manipulating them into a random variable with min-entropy sufficiently close to its entropy (so that randomness extraction can be safely applied).So the current work shows that this barrier is actually a real one in the sense that one cannot do better when seeking a black-box procedure for performing such ``smoothing''; that is, the feeling that smoothing cannot perform any better than the straighforward way is turned into a theorem that relates to black-box constructions.
We study \emph{entropy flattening}: Given a circuit $\mathcal{C}_X$ implicitly describing an $n$-bit source $X$ (namely, $X$ is the output of $\mathcal{C}_X$ on a uniform random input), construct another circuit $\mathcal{C}_Y$ describing a source $Y$ such that (1) source $Y$ is nearly \emph{flat} (uniform on its support), and (2) the Shannon entropy of $Y$ is monotonically related to that of $X$. The standard solution is to have $\mathcal{C}_Y$ evaluate $\mathcal{C}_X$ altogether $\Theta(n^2)$ times on independent inputs and concatenate the results (correctness follows from the asymptotic equipartition property). In this paper, we show that this is optimal among \emph{black-box} constructions: Any circuit $\mathcal{C}_Y$ for entropy flattening that repeatedly queries $\mathcal{C}_X$ as an oracle requires $\Omega(n^2)$ queries.
Entropy flattening is a component used in the constructions of pseudorandom generators and other cryptographic primitives from one-way functions. It is also used in reductions between problems complete for statistical zero-knowledge. The $\Theta(n^2)$ query complexity is often the main efficiency bottleneck. Our lower bound can be viewed as a step towards proving that the current best construction of pseudorandom generator from arbitrary one-way functions by Vadhan and Zheng (STOC 2012) has optimal efficiency.
See ECCC TR18-119.