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.


2 Answers 2


$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 :


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


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


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


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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.