Is the following a PRG?

Question

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.

Answer 1

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.