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

Since this looks like homework, I'm not going to answer the question directly (and I hope others won't either), but I'll just give some hints:

• 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)$?

• You can probably fix up your distinguisher (to get the runtime down to something reasonable), but that's working harder than you need to. Instead, you might want to read on....

• Have you heard of the notion of a "hybrid argument"? If yes, can you see any way that it might be relevant? If no, go read up on "hybrid arguments"; they are a fundamental and important proof techniques for proving indistinguishability/distinguishability.

-