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.

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

1 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.
  • 1
    $\begingroup$ To clarify that last sentence is of course only true if b is independent from a. $\endgroup$
    – Maeher
    Oct 20, 2017 at 19:59
  • $\begingroup$ @Maeher You're right of course. I've added it to the answer. $\endgroup$
    – tylo
    Oct 23, 2017 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.