The Randomized Iterate Revisited - Almost Linear Seed Length PRGs from A Broader Class of One-way Functions.

摘要: We revisit “the randomized iterate” technique that was originally used by Goldreich, Krawczyk, and Luby (SICOMP 1993) refined Haitner, Harnik Reingold (CRYPTO 2006) in constructing pseudorandom generators (PRGs) from regular one-way functions (OWFs). abstract out a technical lemma (which is folklore leakage resilient cryptography), use it to provide simpler more modular proof for the Haitner-Harnik-Reingold PRGs OWFs. introduce general class of OWFs called “weakly-regular functions” which we construct PRG with seed length O(n·logn). More specifically, consider an arbitrary function f range divided into sets Y1, Y2, . ., Yn where each Yi def = {y : 2i−1 ≤ |f−1(y)| < 2}. say weakly-regular if there exists (not necessarily efficient computable) cut-off point max such Ymax some noticeable portion (say n−c constant c), Ymax+1, only sum negligible fraction. making O(n) calls achieve O(n · logn) using bounded space generators. This generalizes approach Haitner et al., fall special case c 0. similar extended method hardness amplification weakly-one-way functions. Our work further explores feasibility limits “randomized type black-box constructions. In particular, underlying can have structure as long set images maximal preimage size has addition, our construction much seed-length security-preserving (albeit less general) than HILL-style best known Vadhan Zheng (STOC 2012) requires O(n).