Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-119 | 19th July 2018 18:30

A Tight Lower Bound for Entropy Flattening

RSS-Feed




Revision #1
Authors: YiHsiu Chen, Mika G\"o{\"o}s, Salil Vadhan, Jiapeng Zhang
Accepted on: 19th July 2018 18:30
Downloads: 8
Keywords: 


Abstract:

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.



Changes to previous version:

Fixed minor typo


Paper:

TR18-119 | 21st June 2018 18:21

A Tight Lower Bound for Entropy Flattening





TR18-119
Authors: YiHsiu Chen, Mika G\"o{\"o}s, Salil Vadhan, Jiapeng Zhang
Publication: 24th June 2018 17:14
Downloads: 118
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint