License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2018.23
URN: urn:nbn:de:0030-drops-88669
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8866/
Chen, Yi-Hsiu ;
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 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.
BibTeX - Entry
@InProceedings{chen_et_al:LIPIcs:2018:8866,
author = {Yi-Hsiu 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:1--23:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-069-9},
ISSN = {1868-8969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8866},
URN = {urn:nbn:de:0030-drops-88669},
doi = {10.4230/LIPIcs.CCC.2018.23},
annote = {Keywords: Entropy, One-way function}
}
Keywords: |
|
Entropy, One-way function |
Collection: |
|
33rd Computational Complexity Conference (CCC 2018) |
Issue Date: |
|
2018 |
Date of publication: |
|
04.06.2018 |