On pseudorandom generators with linear stretch in NC0

We consider the question of constructing cryptographic pseudorandom generators (PRGs) in NC0, namely ones in which each bit of the output depends on just a constant number of input bits. Previous constructions of such PRGs were limited to stretching a seed of n bits to n + o(n) bits. This leaves open the existence of a PRG with a linear (let alone superlinear) stretch in NC0. In this work we study this question and obtain the following main results: We show that the existence of a linear-stretch PRG in NC0 implies non-trivial hardness of approximation results without relying on PCP machinery. In particular, it implies that Max3SAT is hard to approximate to within some multiplicative constant. We construct a linear-stretch PRG in NC0 under a specific intractability assumption related to the hardness of decoding "sparsely generated" linear codes. Such an assumption was previously conjectured by Aleklmovich (FOCS 2003).