On Liner-Size Pseudorandom Generators and Hardcore Functions
Joshua Baron, Yuval Ishai, Rafail Ostrovsky
Abstract:
We consider the question of constructing psedudorandom generators that simultaneously have liner circuit complexity ( in the output length), exponetial security(in the seed length), and a large stretch (liner 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 ƒ:{0,1}n →{0,1}n which satisfies the following requirements:
1.ƒ → can be computed by liner-size circuits;
2. ƒ→is 2βn -hard to invert for some constant β>0 and the min-entropy of → (x) on a random input x is at least γn for constant γ >0 such that β/3+γ>1.
Alternatively, building on the work of Haitner, Harnik and Reingold (SICOMP 2011) one can replace the second requirement by:
2.ƒ →is 2βn-hard to invert for some constant β>0 and it is regular in the sense that the preimage size of every output of → is fixed (but possibly unknown).
Previous constructions of PRGs from one-way functions can do without the entropy or regularity requirements, but even the best such constructions achieve slightly sub-exponetial security (vadhan and Zheng, STOC 2012).
Our Construction relies oon a technical result about hardcore functions that may be of independent intrest. We obtain a family of hardcore functions Η={h : {0 ,1 }n → {0,1}an that can be computed by linear-sized circuits for any 2βn-hard one -way function ƒ:{0,1}n →{0,1}n where β>3a. Our construction of asymptotically optimal PRGs uses such hardcore functions, which can be obtained via linear-size computable affine hash functions (ishai, Kushihlevitz, Ostrovsky and Sahai, STOC2008).
comment: Preliminary version appeared in COCOON 2013 pp: 169-181. Full version appeared in Theor. Comput. Sci. 554: 50-63 (2014)
Fetch PDF file of the paper
| Back to Publications List |