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?
Asked
Viewed
137 times
1
$\begingroup$
$\endgroup$
-
1$\begingroup$ 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. $\endgroup$ – fgrieu Dec 2 '18 at 18:35
-
$\begingroup$ @ 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. $\endgroup$ – nachofest Dec 2 '18 at 22:10
-
$\begingroup$ 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. $\endgroup$ – fgrieu Dec 3 '18 at 6:20
