# 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.

1. $$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?

A proper construction is one similar to your second one.

Once fixed $$l(n)=p(n)\cdot n$$ you can construct a PRF $$G$$ with expansion factor $$l(n)$$ from a PRF $$F:\{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}^n$$ in the following way:

$$G(k) = F_k(1) || F_k(2) || ... || F_k(p(n))$$.

You can prove that $$G$$ is a PRG since if you replace the PRF $$F$$ with a true random function $$f$$ and define $$G'(k) = f(1) || f(2) || ... || f(p(n))$$ an adversary $$\mathcal{A}$$ that distinguish $$G'$$ from $$G$$ can be used to distinguish $$F$$ from $$f$$ contradicting the fact that $$F$$ is a PRF.

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.