Construct PRG from PRF with polynomial expansion factor

I want to prove that for every pseudorandom function $F: \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}^n$ and for every polynomial $p$ such that $p(n) > 1$ for every $n$ it is possible to construct, starting from $F$, a pseudorandom generator $G$ having expansion factor equal to $l(n) = p(n) \cdot n$.

I fixed a PRF $F$ and came up with two constructions for $G$ (where || denotes the concatenation of binary strings), but I am not sure of either:

1. $G(k) = F_k(0^n) || F_k(F_k(0^n))|| \cdots || F_k(...(F_k(0^n))$.

The idea is to apply $F_k$ to the previous output $p(n)$ times. I'm not sure if this is indeed a PRG, though. I fear that in some cases it could lead to "cyclic" strings, but I am not sure.

2. $G(k) = F_k(000...000) || F_k(000...001)|| \cdots || F_k(111...111)$

In the second construction all the inputs have length $n$ and the final output has length $n \cdot 2^n$, but for some combination of $n$ and $p$ the output cannot have a length of $p(n)\cdot n$. For instance, if $n = 2$ and $p(n) = n^{100}+1$, then $|G(k)|= 8$ which is less than $2^{100} + 1$.

Could anyone give me a hint to push me in the right direction?

Both of your PRG constructions are secure.

• Your first construction is essentially output feedback mode (OFB). It is the OFB encryption of the all-zeroes plaintext.

• Similarly, your second construction is essentially a counter mode (CTR) encryption of the all-zeroes plaintext.

Both OFB and CTR modes are CPA-secure. This doesn't exactly guarantee that the PRGs are secure (because the PRGs use these modes with all-zeroes IV), but the proofs of CPA security can be easily adapted to show that both of your PRGs are secure.