# Let $G$ be a PRG. Establish whether the following PRG candidates $G^{'},G^{''}$ are secure or not

Let $$G:\{0,1\}^n \leftarrow \{0,1\}^{2n}$$ be a PRG. Establish whether the following PRG candidates $$G^{'},G^{''}:\{0,1\}^n \leftarrow \{0,1\}^{3n}$$ are secure or not:

• $$G^{'}(s)=(x⊕y,u,v)$$ where $$(x,y)=G(s)$$ and $$(u,v)=G(y)$$;
• $$G^{''}(s)=(x,y ⊕ u,v)$$ where $$(x,y)=G(s)$$ and $$(u,v)=G(y)$$;

This was in my exam today and I thought the following argument: Suppose $$s$$ random in $$\{0,1\}^n$$ then $$(x,y)=G(s)$$ is random in $$\{0,1\}^{2n}$$ since $$G$$ is a PRG. In particular $$y$$ is random in $$\{0,1\}^n$$ so $$(u,v)=G(y)$$ is random in $$\{0,1\}^{2n}$$ since $$G$$ is a PRG. Hence, as XOR preserves randomness, $$x⊕y$$ and $$y ⊕ u$$ are random too.

Finally both $$(x⊕y,u,v)$$ and $$(x⊕y,u,v)$$ are random in $$\{0,1\}^{3n}$$ and this proofs that $$G^{'}$$ and $$G^{''}$$ are both secure PRG.

Now I'm thinking that maybe this argument is wrong because i can't assume that $$(x,y)$$ random in $$\{0,1\}^{2n}$$ implies $$y$$ random in $$\{0,1\}^n$$.

Maybe I’m just confusing myself. Can you help me?

$$\newcommand{\str}{\{0,1\}}$$When trying to tackle such questions, hybrid argument is your friend.
Let $$H_0$$ denote the real experiment where the output $$(w,u,v)$$ is generated according to $$G'$$ -- i.e., for $$s\leftarrow\str^n$$, $$(x,y):=G(s),(u,v):=G(x),w:=x\oplus y;$$ let $$H_2$$ denote the random experiment where $$(w,u,v)\leftarrow\str^{3n}$$. Now, consider a hybrid experiment $$H_1$$ where we choose $$(x,y)\leftarrow\str^{2n}$$ and then set $$(u,v):=G(x),w:=x\oplus y.$$
First, let's prove that $$G'$$ is a PRG using hybrids. Using pseudorandomness of $$G$$, it can be shown that $$H_0\approx H_1$$, where $$\approx$$ denotes computational indistinguishability: given a challenge $$(a^*,b^*)$$ from the PRG experiment of $$G$$, the reduction simply sets $$(x,y):=(a^*,b^*)$$. In case $$(a^*,b^*)$$ is real, then the reduction is simulating $$H_0$$; otherwise, the reduction is simulating $$H_1$$. Similarly, it can be shown that $$H_1\approx H_2$$: the reduction now sets $$(u,v):=(a^*,b^*)$$ (here you need your observation that $$\oplus$$ preserves uniform randomness). Because indistinguishability is transitive, we get that $$H_0\approx H_2$$.
Now, when you try something similar with $$G''$$, you'll see that it doesn't quite go through. Specifically, the reduction for $$H_0\approx H_1$$ still works, but it is not clear how to show $$H_1\approx H_2$$ since it requires a "weird-looking" requirement that, for $$y\leftarrow\str^n$$, $$(G_L(y)\oplus y, G_R(y))$$ is pseudorandom, where by $$G_L$$ and $$G_R$$, I denote the left and right halves of $$G$$'s output. This should already set your alarm bells ringing and you should start thinking about counter-examples to $$G''$$ being a PRG. That is, is it possible to design a $$G$$ such that this property fails? I'll leave that to you (hint: design $$G$$ such that it leaks the seed).