We introduce a more general class of OWFs called "weakly-regular one-way functions" from which we construct a PRG of seed length O(n*logn). More specifically, consider an arbitrary one-way function f with range divided into sets Y1, Y2, ..., Yn where each Y_i={ y:2^{i-1}<=|f^{-1}(y)|<2^{i} }. We say that f is weakly-regular if there exists a (not necessarily efficient computable) cut-off point max such that Y_max is of some noticeable portion (say n^{-c} for constant c), and Y_max+1, ..., Y_n only sum to a negligible fraction. We construct a PRG by making O(n^{2c+1}) calls to f and achieve seed length O(n*logn) using bounded space generators. This generalizes the approach of Haitner et al., where regular OWFs fall into a special case for c=0. We use a proof technique that is similar to and extended from the method by Haitner, Harnik and Reingold for hardness amplification of regular weakly-one-way functions.
Our work further explores the feasibility and limits of the "randomized iterate" type of black-box constructions. In particular, the underlying f can have an arbitrary structure as long as the set of images with maximal preimage size has a noticeable fraction. In addition, our construction is much more seed-length efficient and security-preserving (albeit less general) than the HILL-style generators where the best known construction by Vadhan and Zheng (STOC 2012) requires seed length O(n^3).
Category / Keywords: foundations / Foundations, Pseudorandom Generators, One-way Functions, the Randomized Iterate. Original Publication (with minor differences): IACR-TCC-2015 Date: received 29 May 2014, last revised 10 Jan 2015 Contact author: yuyuathk at gmail com Available format(s): PDF | BibTeX Citation Version: 20150110:100425 (All versions of this report) Discussion forum: Show discussion | Start new discussion