3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How about $G''(xy) = xG(y)$? $\endgroup$ – fkraiem Oct 20 '17 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 '17 at 5:57
4
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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