# PRGs from OW functions

Given a OW function $$f:\{0,1\}^n\to\{0,1\}^n$$ with hardcore predicate $$h(x)$$, you can build a PRG $$G$$ by setting $$G(s):=f(s)\Vert h(s), \quad s\leftarrow\{0,1\}^n.$$ The expansion condition for $$G$$ is trivially satisfied (the seed $$s$$ has length $$n$$, while the string $$f(s)\Vert h(s)$$ has length $$n+1$$). How can I show that $$G$$ is also pseudorandom, that is, for any probabilistic poly-time distinguisher $$\mathcal D$$ $$\mid\Pr[\mathcal D(G(s)=1]-\Pr[\mathcal D(r)=1]\mid\le\epsilon(n), \quad r\leftarrow \{0,1\}^{n+1}$$ where $$\epsilon(n)$$ is a negligible function of $$n$$?

• @kelalaka Sorry, is your comment about my deleted question (the necessity of the one-time requirement for the one-time pad)? If so I have found a satisfactory answer here already. Dec 14, 2021 at 20:17
• Welcome to Cryptography.SE. Usually search first then ask. The usual approach for this type of questions assume that there is a distinguisher for $G$ then there is one for $f$, too. Dec 14, 2021 at 20:24
• @kelalaka Could you elaborate on that? Dec 14, 2021 at 20:26
• It’s not enough for $f$ to be a one-way function, but it does suffice for it to be a one-way permutation (i.e, a bijection). Dec 14, 2021 at 23:18