Combiners on PRG

Question

I was asking myself the following question but I'm not really sure if it's in this way:

I have a first $PRG$: $$G_1: \{0,1\}^{\lambda} \rightarrow \{0,1\}^{\lambda+1}$$

Now I want to construct a second $PRG$ that is structured as follows:

$$G: \{0,1\}^{\lambda} \rightarrow \{0,1\}^{2\lambda}$$

Such that ($||$ is the concatenation symbol and for $x_i$ I'm assuming it's the $i^{th}$ bit of $x$:

$$G(x) = x_1||x_2||...||x_{\lambda-1}||G_1(x)$$

I need to prove that $G$ is a $PRG$ if $G_1$ is. But I was thinking that if I can show a third $PRG$ such that: $$G_1 (x)=x_1||x_2||...x_{\lambda/2}||G_2(x_{\lambda/2}||x_{(\lambda/2)+1}||...||x_{\lambda})$$

Right now my question is: since I'm assuming $G1$ is a $PRG$, I can't modify it right? I mean I cannot do the stuff I'm trying to do with $G_2$?

If I continue stepping on $PRGs$($G_2, G_3, ...$)in practice it's still a $PRG$ since it is the $x$ selected as input of the function is indistinguishable from a uniform but string right?

Answer 1

I don't think $G$ is a PRG at all. Consider the following distinguisher $D$, which knows the description of $G$, $G_1$, and given a string $s = x_1||x_2|| ...|| x_{2\lambda}$:

1. The Distinguisher computes $h = G_1(x_1|| ...|| x_{\lambda-1}||0)$ and $h' = G_1(x_1||...|| x_{\lambda-1}||1)$.
2. $D$ outputs 1 if either $s = x_1||...||x_{\lambda-1}||h$ or $s = x_1||...||x_{\lambda-1}||h'$, and 0 otherwise

Now the property of pseudorandomness should be violated by $D$, since a random string $r \in \{0,1\}^{2\lambda}$ should rarely satisfy $D(r)=1$.

A quote from Katz & Lindell's Introduction to Modern Cryptography section on PRGs:

The seed and its length. The seed for a pseudorandom generator is analogous to the key used by an encryption scheme, and—just as in the case of a cryptographic key—the seed $s$ must be chosen uniformly and be kept secret from any adversary if we want $G(s)$ to look random. Another important point, evident from the above discussion of brute-force attacks, is that $s$ must be long enough so that it is not feasible to enumerate all possible seeds. In an asymptotic sense this is taken care of by setting the length of the seed equal to the security parameter, so exhaustive search over all possible seeds requires exponential time. In practice, the seed length n must at least be large enough so that a brute-force attack running in time 2n is infeasible.