Concatenated pseudorandom generators

Question

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?

Answer 1

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.

Answer 2

This is the Goldreich-Goldwasser-Micali construction, and its security is proved in good textbooks on the foundations of cryptography (e.g., Oded Goldreich's book).