# Showing the non-pseudorandomness of a generator

I'm sorry if this question is too novice. It comes from a practice midterm in a cryptography course which I'm taking, and my confusion here is really that I don't know the "tools" that one uses in practice for this sort of question. The notation (and class) is Katz's.

I've been given a PRG $$G(s)$$; I'm trying to show explicitly that $$s\mathbin\|G(s)$$ is not a PRG. Intuitively, I'd expect both components to be random-seeming, so there's nothing obvious that sticks out to me to XOR or manipulate.

• What's the probability that a uniform random string $s \mathbin\| x$ satisfies $G(s) = x$, assuming the lengths all work out? – Squeamish Ossifrage Mar 10 '19 at 5:10
• @SqueamishOssifrage So, my distinguisher $D$ has "access" to the PRG $G$? (I'm sorry, that just wasn't very clear from the start to me.) – Chris Mar 10 '19 at 5:14
• Yep! The only thing it doesn't have a priori is the original input to the putative generator $G'\colon s \mapsto s \mathbin\| G(s)$. Of course, $G'$ just happens to cough it up in the output, so, a posteriori – Squeamish Ossifrage Mar 10 '19 at 5:18
• In particular, your goal is to write a decision algorithm $A$ such that $A(G'(s)) = A(s \mathbin\| G(s))$ and $A(u)$ have substantially different probability of returning 1, where $u$ and $s$ are uniform random strings of the appropriate lengths. – Squeamish Ossifrage Mar 10 '19 at 5:19
• Incidentally, I know that the answer to your question is $\frac{2^n}{2^{2n}}$, since the subset of strings $r \in \{0,1\}^{2n}$ in this format is constrained by $G$ having a range of size $2^n$. – Chris Mar 10 '19 at 5:20

Let $$D(s) = \mathbb{I}\{s = x||G(x), x \in \{0,1\}^n\}$$. Then, if our putative PRG is $$G'$$, $$\Pr[D(G'(s)) = 1] = 1$$ - that is, $$G'(s)$$ is always in the format that $$D$$ looks for. However, $$\Pr[D(r) = 1]$$ (where $$r$$ is uniform from $$\{0,1\}^{2n}$$) is $$\frac{2^n}{2^{2n}}$$, to reflect that $$s||G(s)$$ has a range of only $$2^n$$ - being completely determined by $$s$$ - while there are $$2^{2n}$$ possible values $$r$$.
Thus $$|\Pr[D(G'(s)) = 1] - \Pr[D(r) = 1]| = 1 - \frac{2^n}{2^{2n}}$$, a non-negligible function.