# identify if the functions are pseudorandom generator?

Given a pseudorandom generator (PRG) with $G(x) = y_{1} || y_{2}$, where $y_{1}$ and $y_{2}$ are n-bit strings. $G'(x) := G(y_{1}) || G(y_{2})$. Is $G'(.)$ still a PRG? I am guessing it's a No because $G'(x) := G(y_{1}) || G(y_{2})$ always outputs the concatenation of $G(x)$ with previously generated outputs as inputs. But I am not sure what's the formal way of explaining this.

In addition. $G''(x) = G(y_{1}) ||G(y_{1})\oplus G(y_{2})|| G(y_{2})$, is $G''(x)$ still a PRG? I would say No again in this case because the pattern is again the concatenation of $G'(x)$ with the $\oplus$ in the middle?

I think I might be entirely wrong on this. A pointer or two would be appreciated.

$G'$ is a PRG. Proof sketch: by assumption, $G(x)$ for a uniform $x$ is indistinguishable from a uniform string. This means that $y_1$ and $y_2$ (the halves of $G(x)$) are also indistinguishable from uniform strings, and finally that so are $G(y_1)$ and $G(y_2)$.

$G’(x)=G(y_1)||G(y_2)$ is a PRG , to prove this i suggest you to prove that both $H_1(x) = y_1$ and $H_2(x) = y_2$ are PRG, then you get that $G’(x)=G(H_1(x))||G(H_2(x))$ then to prove that $G’$ is indeed a PRG you use the hybrid argument :

$G(H_1(x))||G(H_2(x))$

--distinguishing between $H_1(x)$ and $r_1$ , $r_1$ is a random string.

$G(r_1)||G(H_2(x))$

--distinguishing between $H_2(x)$ and $r_2$ , $r_2$ is a random string.

$G(r_1)||G(r_2)$

--distinguishing between $G(r_1)$ and $r_1$ , $r_1$ is a random string.

$r_1||G(r_2)$

--distinguishing between $G(r_2)$ and $r_2$ , $r_2$ is a random string.

$r_1||r_2$

about $G’'$ i think its not a PRG since a Distinguisher can check if the first part is equal to the second part.