# $G_f(x) = x \|f(x)$ is not a PRG with $\operatorname{DPT}$-computable function $f$

Let $$f:\{0,1\}^* \rightarrow \{0,1\}$$ be any $$\operatorname{DPT}$$-computable function.

• Show that $$G_f(x) = x \|f(x)$$ is not a PRG.

Can anyone help me on understand how to prove this?

• Hint: assume $x$ is $n$-bit bitstring, and construct a distinguisher with advantage $\frac14$ whatever $n$. It will need to use $f$ as a subprogram. For what a distinguisher is, see my updated answer to your previous question. Note: "DPT-computable" stands for computable in Deterministic Polynomial Time, so that the PRG and the distinguisher are. – fgrieu Dec 2 '18 at 18:35
• @ fgrieu I had the idea that given input $x = x_1 ...x_n$ then $G(x) = (x_1...x_n)||f(x) = y$ where $y$ would have $n+1$ bits. Then a distinguisher $D$ on input $y$ could distinguish input by just checking if $y_{n+1} =f(x_1...x_n)$ So I would guess that the $Pr[D(G(x))=1]=1$ Because just checking the above would tell you $G$ was used. And for $Pr_{r\in\{0,1\}^{n+1}}[D(r)=1]$ im not so sure about. – nachofest Dec 2 '18 at 22:10
• Kudos, you have selected a good distinguisher. Hint: in the experiment computing $\displaystyle\Pr_{r\in\{0,1\}^{n+1}}[D(r)=1]$, the bit $r_{n+1}$ is random and independent of the other ones, which determine against what $r_{n+1}$ is compared. Note: my former $\frac14$ is lower than it could have been. – fgrieu Dec 3 '18 at 6:20