A Dichotomy for Local Small-Bias Generators

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

G

and a small predicate

P

that is applied at each output. Following the works of Cryan and Miltersen (MFCS ’01) and by Mossel et al (FOCS ’03), we ask: which graphs and predicates yield “small-bias” generators (that fool linear distinguishers)?

We identify an explicit class of degenerate predicates and prove the following. For most graphs, all

non-degenerate

predicates yield small-bias generators,

$f\colon \{0,1\}^n \rightarrow \{0,1\}^m$

, with output length

m

 = 

n

1 + 

ε

for some constant

ε

 > 0. Conversely, we show that for most graphs,

degenerate

predicates are not secure against linear distinguishers, even when the output length is linear

m

 = 

n

 + Ω(

n

). 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 give evidence in support of 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 for such functions.