# How to prove that the concatenation of two secure PRG is secure?

Given $G:\{0,1\}^s \rightarrow \{0, 1\}^n$ a secure PRG, how can one prove that $G'(k_1, k_2) = G(k_1) \cdot G(k_2)$ is secure ($\cdot$ means concatenation)?

In other words, I'd like to show that if there is a distinguisher for $G'$ then this implies that there exists a distinguisher for $G$.

For example, could this distinguisher be as follows?

$A(x) = \text{round}(\frac{1}{2^n} \sum_{y \in \{0,1\}^n} A(y \cdot x))$

-
I fixed some errors in your question. My question for you is: is this homework? If so, you should solve it yourself. The entire point of homework is to force you to struggle with these problems yourself; that's the only way you will learn it. You won't learn the material by looking at how other people have solved the problem. – D.W. Nov 14 '12 at 3:39

• You're on a good direction. If you want to prove that $G'$ is a secure PRG, then your general approach (trying to show that a distinguisher for $G'$ implies a distinguisher for $G$) is a good strategy. Keep at it.
• Your particular distinguisher $A$ is not an effective distinguisher against $G$. Hint: What is the running time to compute $A(x)$?