Chen, YiHsiu ;
Göös, Mika ;
Vadhan, Salil P. ;
Zhang, Jiapeng
A Tight Lower Bound for Entropy Flattening
Abstract
We study entropy flattening: Given a circuit C_X implicitly describing an nbit 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 blackbox 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 oneway 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 zeroknowledge [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 oneway functions by Vadhan and Zheng (STOC 2012) has optimal efficiency.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs:2018:8866,
author = {YiHsiu Chen and Mika G{\"o}{\"o}s and Salil P. Vadhan and Jiapeng Zhang},
title = {{A Tight Lower Bound for Entropy Flattening}},
booktitle = {33rd Computational Complexity Conference (CCC 2018)},
pages = {23:123:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770699},
ISSN = {18688969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8866},
URN = {urn:nbn:de:0030drops88669},
doi = {10.4230/LIPIcs.CCC.2018.23},
annote = {Keywords: Entropy, Oneway function}
}
2018
Keywords: 

Entropy, Oneway function 
Seminar: 

33rd Computational Complexity Conference (CCC 2018)

Issue date: 

2018 
Date of publication: 

2018 