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.

Fixed minor typo

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.