To print higher-resolution math symbols, click the
Hi-Res Fonts for Printing button on the jsMath control panel.

jsMath
Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-126 | 17th September 2011 15:52

A Dichotomy for Local Small-Bias Generators

RSS-Feed




TR11-126
Authors: Benny Applebaum, Andrej Bogdanov, Alon Rosen
Publication: 17th September 2011 17:14
Downloads: 4312
Keywords: 


Abstract:

We 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.



ISSN 1433-8092 | Imprint