We revisit ``the randomized iterate'' technique that was originally used by Goldreich, Krawczyk, and Luby (SICOMP 1993) and refined by Haitner, Harnik and Reingold (CRYPTO 2006) in constructing pseudorandom generators (PRGs) from regular one-way functions (OWFs). We abstract out a technical lemma with connections to several recent work on cryptography with imperfect randomness, which provides an arguably simpler and more modular proof for the Haitner-Harnik-Reingold PRGs from regular OWFs.

We extend the approach to a more general construction of PRGs with seed length $O(n{\log}n)$ from a broader class of OWFs. More specifically, consider an arbitrary one-way function $f$ whose range is divided into sets $Y_1$, $Y_2$, $\ldots$, ${Y}_n$ where each ${Y}_i=\{y:2^{i-1}\le|f^{-1}(y)|<2^{i}\}$. We say that the maximal preimage size of $f$ is $2^{max}$ if $Y_{max}$ has some noticeable portion (say $n^{-c}$ for constant $c$), and ${Y}_{max+1}$, $\ldots$, ${Y}_{n}$ only sum to a negligible fraction $\epsilon$. We construct a PRG by making $O(n^{2c+1})$ calls to the underlying OWF and achieve seed length $O(n{\log}n)$ using bounded space generators, where the only parameter required to know is $c$ (which is constant for a specific $f$ but may vary for different functions) and no knowledge is required for $\max$ and $\epsilon$. 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 construction achieves almost linear seed length for a broader class of one-way functions than previously known, where the case of regular OWFs follows as a simple corollary for $c=0$. We show that although an arbitrary one-way function may not fall into the class of OWFs as we defined, the counterexamples must satisfy a very strong condition and thus should be somewhat artificial. Our approach takes a different route from the generic HILL-style generators (which is characterized by flattening Shannon entropy sources) where the best known construction by Vadhan and Zheng (STOC 2012) requires seed length $O(n^3)$.

We revisit ``the randomized iterate'' technique that was originally used by Goldreich, Krawczyk, and Luby (SICOMP 1993) and refined by Haitner, Harnik and Reingold (CRYPTO 2006) in constructing pseudorandom generators (PRGs) from regular one-way functions (OWFs). We abstract out a technical lemma (which is folklore in leakage resilient cryptography), and use it to provide a simpler and more modular proof for the Haitner-Harnik-Reingold PRGs from regular OWFs.

We introduce a more general class of OWFs called ``weakly-regular one-way functions'', and construct a PRG with seed length $O(n\cdot\log{n})$. More specifically, consider an arbitrary one-way function $f$ with range divided into sets $Y_1$, $Y_2$, $\ldots$, $Y_n$ where each $Y_i=\{y:2^{i-1}\le|f^{-1}(y)|<2^{i}\}$. We say that $f$ is weakly-regular if there is a cutoff point $max$ such that $\Y_{max}$ has some noticeable portion (say $n^{-c}$ for constant $c$), and $Y_{max+1}$, $\ldots$, $Y_n$ only sum to a negligible fraction $\epsilon$.

We construct a PRG by making $O(n^{2c+1})$ calls to $f$ and achieve seed length $O(n\cdot\log{n})$ using bounded space generators, where the only parameter required to know is $c$ (which is constant for a specific $f$ but may vary for different OWFs) and no knowledge is required for $max$ and $\epsilon$. This generalizes the approach of Haitner et al., where arbitrary 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 (but less general) than the HILL-style generators where the best known construction by Vadhan and Zheng (STOC 2012) requires seed length $\tilde{O}(n^3)$.

We revisit ``the randomized iterate'' technique that was originally used by Goldreich, Krawczyk, and Luby (SICOMP 1993) and refined by Haitner, Harnik and Reingold (CRYPTO 2006) in constructing pseudorandom generators (PRGs) from regular one-way functions (OWFs). We abstract out a technical lemma with connections to several recent work on cryptography with imperfect randomness, which provides an arguably simpler and more modular proof for the Haitner-Harnik-Reingold PRGs from regular OWFs.

We extend the approach to a more general construction of PRGs with seed length $O(n{\log}n)$ from a broader class of OWFs. More specifically, consider an arbitrary one-way function $f$ whose range is divided into sets $Y_1$, $Y_2$, $\ldots$, ${Y}_n$ where each ${Y}_i=\{y:2^{i-1}\le|f^{-1}(y)|<2^{i}\}$. We say that the maximal preimage size of $f$ is $2^{max}$ if $Y_{max}$ has some noticeable portion (say $n^{-c}$ for constant $c$), and ${Y}_{max+1}$, $\ldots$, ${Y}_{n}$ only sum to a negligible fraction $\epsilon$. We construct a PRG by making $O(n^{2c+1})$ calls to the underlying OWF and achieve seed length $O(n{\log}n)$ using bounded space generators, where the only parameter required to know is $c$ (which is constant for a specific $f$ but may vary for different functions) and no knowledge is required for $\max$ and $\epsilon$. 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 construction achieves almost linear seed length for a broader class of one-way functions than previously known, where the case of regular OWFs follows as a simple corollary for $c=0$. We show that although an arbitrary one-way function may not fall into the class of OWFs as we defined, the counterexamples must satisfy a very strong condition and thus should be somewhat artificial. Our approach takes a different route from the generic HILL-style generators (which is characterized by flattening Shannon entropy sources) where the best known construction by Vadhan and Zheng (STOC 2012) requires seed length $O(n^3)$.

We revisit ``the randomized iterate'' technique that was originally used by Goldreich, Krawczyk, and Luby (SICOMP 1993) and refined by Haitner, Harnik and Reingold (CRYPTO 2006) in constructing pseudorandom generators (PRGs) from regular one-way functions (OWFs). We abstract out a technical lemma with connections to several recent work on cryptography with imperfect randomness, which provides an arguably simpler and more modular proof for the Haitner-Harnik-Reingold PRGs from regular OWFs.

We extend the approach to a more general construction of PRGs with seed length $O(n{\log}n)$ from a broader class of OWFs. More specifically, consider an arbitrary one-way function $f$ whose range is divided into sets $Y_1$, $Y_2$, $\ldots$, ${Y}_n$ where each ${Y}_i=\{y:2^{i-1}\le|f^{-1}(y)|<2^{i}\}$. We say that the maximal preimage size of $f$ is $2^{max}$ if $Y_{max}$ has some noticeable portion (say $n^{-c}$ for constant $c$), and ${Y}_{max+1}$, $\ldots$, ${Y}_{n}$ only sum to a negligible fraction $\epsilon$. We construct a PRG by making $O(n^{2c+1})$ calls to the underlying OWF and achieve seed length $O(n{\log}n)$ using bounded space generators, where the only parameter required to know is $c$ (which is constant for a specific $f$ but may vary for different functions) and no knowledge is required for $\max$ and $\epsilon$. 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 construction achieves almost linear seed length for a broader class of one-way functions than previously known, where the case of regular OWFs follows as a simple corollary for $c=0$. We show that although an arbitrary one-way function may not fall into the class of OWFs as we defined, the counterexamples must satisfy a very strong condition and thus should be somewhat artificial. Our approach takes a different route from the generic HILL-style generators (which is characterized by flattening Shannon entropy sources) where the best known construction by Vadhan and Zheng (STOC 2012) requires seed length $O(n^3)$.