# 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.

• Ah. So $G'(x)$ is $G(x)$ with the first $|x|$ bits of output XORed with the seed $x$, and the rest unchanged, including any dependence of output length from input length thru the function $l$. Hint: what if $G$ was defined (for non-enpty input) from a PRG $H$ by $G(0\mathbin\|x)=0\mathbin\|H(x)$ and $G(1\mathbin\|x)=1\mathbin\|H(x)$? Would $G$ be a PRG? Would $G'$ be a PRG? – fgrieu Feb 13 at 17:45
• "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." Sure! I would add also that if you can find a counter example for this simple example, it would also be pretty easy from there to find the answer to you initial question :) Did you try? – Geoffroy Couteau Feb 13 at 17:51
• @fgrieu I see why G'(x) is not a PRG, but having trouble showing G is a PRG, I can see the intuition why G could be a PRG since revealing one bit of the seed might not be enough to identify G. I've tried building an Identifier D for H given an Identifier D' for G - given w run D' on 0||w. I'm guessing that x1 was 0 and giving that to D'. The analysis doesn't work out. – David Peled Feb 16 at 16:19
• I see where I was confused!! the first bit is not fed into H. I will continue working on it and hopefully post a full answer soon. Thanks for the help. – David Peled Feb 16 at 16:29

$$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)| < neg(n)$$

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

$$D(w):$$

1. Generate a random bit $$b$$
2. Run $$D'$$ on $$b\mathbin\|w$$
3. 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)| < neg(n)$$ Subtitute the above: $$|\Pr(D'(r')=1) - \Pr(D'(G(x'))=1)| < 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.