Welcome to the resource topic for 2011/512
Title:
A Dichotomy for Local Small-Bias Generators
Authors: Benny Applebaum, Andrej Bogdanov, Alon Rosen
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 \bit^n \rightarrow \bit^m, with output length m = n^{1 + \eps} for some constant \eps > 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.
ePrint: https://eprint.iacr.org/2011/512
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .