# Identifying Opportunities in Pseudorandomness (NSF CCF-1749750)

2018
Chen, Yi-Hsiu, Mika Goos, Salil P. Vadhan, and Jiapeng Zhang. “A tight lower bound for entropy flattening.” In 33rd Computational Complexity Conference (CCC 2018), 102:23:21-23:28. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik: Leibniz International Proceedings in Informatics (LIPIcs), 2018. Publisher's VersionAbstract

Version History: Preliminary version posted as ECCC TR18-119.

We study entropy flattening: Given a circuit $$C_X$$ implicitly describing an n-bit source $$X$$ (namely, $$X$$ is the output of $$C_X$$  on a uniform random input), construct another circuit $$C_Y$$ describing a source $$Y$$ such that (1) source $$Y$$ is nearly 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 $$C_Y$$ evaluate $$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 black-box constructions: Any circuit $$C_Y$$ for entropy flattening that repeatedly queries $$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 [12, 22, 13, 6, 11, 10, 7, 24]. It is also used in reductions between problems complete for statistical zero-knowledge [19, 23, 4, 25]. 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.