**
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 |