2026-07-23T17:14:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8866 2024-03-06T10:42:53Z ddc:004 open_access

A Tight Lower Bound for Entropy Flattening Chen, Yi-Hsiu Göös, Mika Vadhan, Salil P. Zhang, Jiapeng Entropy One-way function 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 [Johan Håstad et al., 1999; John Rompel, 1990; Thomas Holenstein, 2006; Iftach Haitner et al., 2006; Iftach Haitner et al., 2009; Iftach Haitner et al., 2013; Iftach Haitner et al., 2010; Salil P. Vadhan and Colin Jia Zheng, 2012]. It is also used in reductions between problems complete for statistical zero-knowledge [Tatsuaki Okamoto, 2000; Amit Sahai and Salil P. Vadhan, 1997; Oded Goldreich et al., 1999; Vadhan, 1999]. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yi-Hsiu Chen and Mika Göös and Salil P. Vadhan and Jiapeng Zhang 2018 Is Part Of LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2018.23 urn:nbn:de:0030-drops-88669 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.23 eng https://creativecommons.org/licenses/by/3.0/legalcode