ECCC-Report TR11-126https://eccc.weizmann.ac.il/report/2011/126Comments and Revisions published for TR11-126en-usSat, 17 Sep 2011 17:14:15 +0300
Paper TR11-126
| A Dichotomy for Local Small-Bias Generators |
Benny Applebaum,
Andrej Bogdanov,
Alon Rosen
https://eccc.weizmann.ac.il/report/2011/126We consider pseudorandom generators in which each output bit depends on a constant number of input bits. Such generators have appealingly simple structure: they can be described by a sparse input-output dependency graph and a small predicate that is applied at each output. Following the works of Cryan and Miltersen (MFCS'01) and by Mossel et al (STOC'03), we focus on the study of ``small-bias" generators (that fool linear distinguishers).
We prove that for most graphs, all but a handful of ``degenerate'' predicates yield small-bias generators, $f\colon \{0,1\}^n \rightarrow \{0,1\}^m$, with output length $m = n^{1 + \epsilon}$ for some constant $\epsilon > 0$. Conversely, we show that for most graphs, ``degenerate'' predicates are not secure against linear distinguishers. Taken together, these results expose a dichotomy: every predicate is either very hard or very easy, in the sense that it either yields a small-bias generator for almost all graphs or fails to do so for almost all graphs.
As a secondary contribution, we attempt to support the view that small-bias is a good measure of pseudorandomness for local functions with large stretch. We do so by demonstrating that resilience to linear distinguishers implies resilience to a larger class of attacks.Sat, 17 Sep 2011 17:14:15 +0300https://eccc.weizmann.ac.il/report/2011/126