# Is the following a PRG?

Let $$G: \{0, 1\}^n → \{0, 1\}^m$$ be a PRG. We construct a function $$G': \{0, 1\}^{m + n} → \{0, 1\}^{2m}$$ defined as follows

$$G'(x || y) = x || (G(y) ⊕ x)$$

for all $$x ∊ \{0, 1\}^m$$ and $$y ∊ \{0, 1\}^n$$. (The symbol || denotes here the concatenation of binary strings.)

Is $$G'$$ a PRG?

I believe that it is not, but I could easily be wrong.

I know, given a random string s of length $$2m$$ (split into equal length strings $$s_1$$ and $$s_2$$), that $$s_1$$ would be equivalent to $$x$$, and that $$s_2 \oplus x$$ would be equivalent to $$G(y)$$. But since $$G(y)$$ is indistinguishable from $$U_m$$, I'm having trouble reaching the conclusion of my contradiction.

I'm still relatively new to all of this, so any help would be appreciated.

• How about $G''(xy) = xG(y)$? Oct 20 '17 at 2:01
• Suppose that you are given a distinguisher $A'$ for $G'$. Can you use $A'$ to build a distinguisher $A$ for $G$?
– erth
Oct 20 '17 at 5:57

I believe that it is not, but I could easily be wrong.

... I'm having trouble reaching the conclusion of my contradiction

The problem is you can't show that contradiction, because there isn't any. As a rule of thumb for homework questions: If it becomes clear that you can't prove your initial assumption, consider that your intuition was wrong.

Here are some pointers how you can show that $$G'$$ is in fact a PRG, in a proof by contradiction:

• Let's assume $$G'$$ is not a PRG, and that means a distinguisher $$\mathcal{D}$$ exists.
• The input for $$\mathcal{D}$$ is one element either uniform random or of the form $$x||(G(y)\oplus x)$$, and then it has some non-negligible advantage $$\epsilon$$.
• We want to build a distinguisher for $$G$$. So as input we get one element, which is either from a uniform random distribution or from the image of $$G$$.
• In general, if $$a$$ is uniform random, then $$a \oplus b$$ is also uniform random - this is true as long as $$b$$ is independent of $$a$$. This includes fixed $$b$$ as well as $$b$$ drawn independently from any distribution.
• To clarify that last sentence is of course only true if b is independent from a. Oct 20 '17 at 19:59
• @Maeher You're right of course. I've added it to the answer.
– tylo
Oct 23 '17 at 9:52