On linear-size pseudorandom generators and hardcore functions
We consider the question of constructing pseudorandom generators that simultaneously have linear circuit complexity (in the output length), exponential security (in the seed length), and a large stretch (linear or polynomial in the seed length). We refer to such a pseudorandom generator as an asymptotically optimal PRG . We present a simple construction of an asymptotically optimal PRG from any one-way function f:{0,1}n?{0,1}n f : { 0 , 1 } n ? { 0 , 1 } n which satisfies the following requirements: f can be computed by linear-size circuits; f  is 2?n 2 ? n -hard to invert, for some constant ?>0 ? > 0 ; f either has high entropy , in the sense that the min-entropy of f(x) f ( x ) on a random input x is at least ?n  where ?/3+?>1 ? / 3 + ? > 1 , or alternatively it is regular in the sense that the preimage size of every output of f is fixed. Our construction relies on a technical result about hardcore functions that may be of independent interest. We obtain a family of hardcore functions H={h:{0,1}n?{0,1}?n} H = { h : { 0 , 1 } n ? { 0 , 1 } ? n } that can be computed by linear-size circuits for any 2?n 2 ? n -hard one-way function f:{0,1}n?{0,1}n f : { 0 , 1 } n ? { 0 , 1 } n where ?>3? ? > 3 ? . Our construction of asymptotically optimal PRGs uses such hardcore functions, which are obtained via linear-size computable affine hash functions (Ishai et al. (2008) [24]).
pseudorandom generators circuit complexity one-way functions cryptography