ECCC-Report TR18-119https://eccc.weizmann.ac.il/report/2018/119Comments and Revisions published for TR18-119en-usThu, 19 Jul 2018 18:30:20 +0300
Revision 1
| A Tight Lower Bound for Entropy Flattening |
YiHsiu Chen,
Mika G\"o{\"o}s,
Salil Vadhan,
Jiapeng Zhang
https://eccc.weizmann.ac.il/report/2018/119#revision1We 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.Thu, 19 Jul 2018 18:30:20 +0300https://eccc.weizmann.ac.il/report/2018/119#revision1
Paper TR18-119
| A Tight Lower Bound for Entropy Flattening |
YiHsiu Chen,
Mika G\"o{\"o}s,
Salil Vadhan,
Jiapeng Zhang
https://eccc.weizmann.ac.il/report/2018/119We 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.Sun, 24 Jun 2018 17:14:35 +0300https://eccc.weizmann.ac.il/report/2018/119