Is the first bit preserving version of a PRG also a PRG?

Question

Given that $G$ is a pseudorandom generator from $\{0,1\}^n$ to $\{0,1\}^{l(n)}$, $G'$ defined as follows: $G'(s) = \begin{cases} G(s) \space \text{if the first bit of s and G(s) are the same} \\ G(s)\oplus 100\cdots0 \space \text{if the first bits of s and G(s) don't match} \end{cases}$

That is, $G'$ is the first-bit preserving version of $G$. Is $G'$ a PRG?

The reason I am interested in this question is that I wish to construct a first-bit preserving PRG since that would imply that for any PRG $G$, $s\oplus G(s)$ is not always a PRG (checking for the first bit being $0$ or not is a distinguisher).

I have tried doing a contrapositive argument by assuming $D$ is some PPT distinguisher for telling apart $G(s)$ and $G'(s)$, and using $D$ to construct a PPT algorithm that distinguishes $U_{l(n)}$ from $G(s)$ but I am unable to create one which wins with noticeable probability. I considered the algorithm which on input $w$, flips a coin $b$ and then passes $b||w$ to $D$ and outputs the same output as $D$ but this does not guarantee me a noticeable win probability

Answer 1

(Assuming PRGs exist) it is possible to construct $G$ such that $G'$ is provably a PRG and it is possible to construct $G$ such that $G'$ is provably not a PRG.

As a fun way to disprove the conjecture that $G'$ must be secure whenever $G$ is, let's start by assuming we are given $G$ and $G'$ which are both secure. Now let $F[G']$ denote the function for which $F[G'](x)$ equals $G'(x)$ written in reverse. If $G'$ is secure, then $F[G']$ must be secure. However, applying your transform again gives a $F[G']'$ which is definitely insecure (because its first and last bits always match).

As a hint towards your higher-level motivation, I recommend constructing a "first-bit preserving PRG" by transforming a given PRF $G:\{0,1\}^n\to \{0,1\}^{\ell(n)}$ into a first-bit preserving PRG with domain $\{0,1\}^{n+1}$.