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

Question

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?

Answer 1

$\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).