4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – fgrieu Feb 13 at 17:45
  • $\begingroup$ "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? $\endgroup$ – Geoffroy Couteau Feb 13 at 17:51
  • $\begingroup$ @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. $\endgroup$ – David Peled Feb 16 at 16:19
  • $\begingroup$ 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. $\endgroup$ – David Peled Feb 16 at 16:29
5
$\begingroup$

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

| improve this answer | |
$\endgroup$

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.