# Concatenated pseudorandom generators

I have two pseudorandom generators $$G_1$$ and $$G_2$$ from $$k$$ bit to $$2k$$ bit. I have another PRG $$G_3$$ from $$k$$ to $$2k$$ bits. Now I buildup a new function from $$k$$ to $$4k$$ as follows:

Let $$x$$ be $$k$$ bit then apply $$G_3$$ on it on $$x$$. Then let output by $$y$$. Apply $$G_1$$ on first $$k$$ bits and $$G_2$$ on last $$k$$ and join the resulting output. Then resulting function is a PRG. How do you prove this?

• What exactly is a PRNG “from k bit to 2k bit”? – gnasher729 Apr 5 at 8:43

The idea is to use a hybrid argument. Let us first write a formula for the new PRG: $$G(x) = G_1(G_{3,1}(x)) G_2(G_{3,2}(x)),$$ where $$G_3(x) = G_{3,1}(x) G_{3,2}(x)$$.
Suppose that we could distinguish between $$G(U_k)$$ and $$U_{4k}$$, where $$U_n$$ denotes $$n$$ random bits. Consider the following sequence: $$G(U_k); G_1(U_k) G_2(U_k); U_{2k} G_2(U_k); U_{4k}.$$ By assumption, we can distinguish between the first distribution and the last distribution. Hence we can distinguish an adjacent pair of distributions.
• If we can distinguish $$G(U_k)$$ and $$G_1(U_k) G_2(U_k)$$, then this gives a distinguisher for $$G_3$$.
• If we can distinguish $$G_1(U_k) G_2(U_k)$$ and $$U_{2k} G_2(U_k)$$, then this gives a distinguisher for $$G_1$$.
• If we can distinguish $$U_{2k} G_2(U_k)$$ and $$U_{4k}$$, then this gives a distinguisher for $$G_2$$.
By assumption, $$G_1,G_2,G_3$$ are all secure, so we obtain a contradiction.