Is this a prg: G'(x) = G(x) ⊕ (x || 0^(l(|x|)-|x|)) This is not homework, but a question from an exam.

Let $G(x)$ be a PRG with expansion parameter $\ell(n)$.

$$G'(x) = G(x) \oplus (x \mathbin\| 0^{\ell(|x|)-|x|})$$ where $\ell(|x|) = |G(x)|$

My intuition is that it is a PRG, first, $n$ bits are just XOR between $x$ which is random, with $G(x)$ which is a PRG, and the rest of the bits are untouched.

I tried to formally prove this to no avail, so I tried a simpler exercise:

$$G'(x) = G(x) \oplus (x_1 \mathbin\| 0^{\ell(|x|)-1})$$ where $x_1$ is the first bit of $x$.

If I can show this is a PRG, it will be easy with induction on the number of bits we take from x to show the original $G'$ is a PRG.
$G'(x)$ is not a PRG.

I am posting a formalized version of @fgrieu 's example.

Given $H(x)$ PRG we build $G(x)$:

$$G(x) = x_1\mathbin\|H(x_2\mathbin\|\ldots\mathbin\|x_n)$$

$G(x)$ is a PRG:

The expansion requirement is easily shown.

We show that for all $D$ there exists a negligible function $neg$ such that:
$$|\Pr(D(r)=1) - \Pr(D(G(x))=1)| &lt; neg(n)$$

Let $D'$ be an identifier for $G(x)$, we shall build an identifier $D$ for $H(x)$:

$D(w):$


Generate a random bit $b$
Run $D'$ on $b\mathbin\|w$
Return 1 if and only if $D'$ returned 1.


Analysis:

Let $r$ be a uniformly drawn binary string:

$$\Pr(D(r)=1)=\Pr(D'(b\mathbin\|r)=1) = \Pr(D'(r')=1)$$
Where r' is also a uniformly drawn binary string.

$$\Pr(D(H(x))=1)=\Pr(D'(b\mathbin\| H(x))=1)=\Pr(D'(G(b\mathbin\| x))=1)=\Pr(D'(G(x'))=1)$$

Since we assume $H(x)$ is a PRG, there exists a negligible function such that:

$$|\Pr(D(r)=1) - \Pr(D(H(x))=1)| &lt; neg(n)$$
Subtitute the above:
$$|\Pr(D'(r')=1) - \Pr(D'(G(x'))=1)| &lt; neg(n)$$

This proves that $G(x)$ is a PRG.

Now we show $G'(x)$ as defined below is not a PRG:
$$G'(x) = G(x) \oplus (x \mathbin\| 0^{\ell(|x|)-|x|})$$ where $\ell(|x|) = |G(x)|$

Substitute our $G(x)$:
$$G'(x) = (x_1 \mathbin\| H(x)) \oplus (x \mathbin\| 0^{\ell(|x|)-|x|})$$ 
$$G'(x)=0||(H(x)\oplus(x_2\mathbin\| x_3\mathbin\| \ldots\mathbin\|x_n\mathbin\| 0^{\ell(|x|)-|x|})$$

As shown $G'(x)$ will always start with a 0, so we can build an identifier $T$ that will output 1 if the first bit is 0.

$$|\Pr(T(r)=1) - \Pr(T(G'(x))=1)| = |1/2 - 1| = 1/2$$ which is not negligible, hence $G'(x)$ is not a PRG.