Construct a specific length-doubling pseudorandom generator from a length-doubling pseudorandom

Question

Let $G$ be a length-doubling pseudorandom generator (i.e., for any $n\in \mathbb{N}$ and for any $s\in\{0, 1\}^n$ it holds that $G(s)\in\{0, 1\}^{2n}$). Can you construct a length-doubling pseudorandom generator $H$ such that $H(0^n)= 0^{2n}$ for any $n\in \mathbb{N}$?

Answer 1

Define $\forall s\in \{0,1\}^{n} \ : H(s)=G(s)\oplus G(0^n)\implies H(0^n)=G(0^n)\oplus G(0^n)=0^{2n}$

now, we'll prove by contradiction that $H$ is indeed a pseudo-random generator.

assuming that it's not we get that there exist an adversary D (PPT algo) such that for every polynomial p(n):

$|Pr_{s\leftarrow\{0,1\}^n}[D(H(s))=1]-Pr_{r\leftarrow\{0,1\}^n}[D(r)=1]|>1/p(n)$

Now, define the adversary $D'(v):=v\oplus G(0^n)$ for the PRG "$G$", and we're almost done: $|Pr_{s\leftarrow\{0,1\}^n}[D'(G(s))=1]-Pr_{r\leftarrow\{0,1\}^n}[D'(r)=1]|=$ $|Pr_{s\leftarrow\{0,1\}^n}[D(G(s)\oplus G(0^n))=1]-Pr_{r\leftarrow\{0,1\}^n}[D((r)\oplus G(0^n)=1]|=$ $|Pr_{s\leftarrow\{0,1\}^n}[D(H(s))=1]-Pr_{r\leftarrow\{0,1\}^n}[D(r)=1]|>1/p(n)$

$\blacksquare$