# How can I prove/disprove that a construction yields a secure PRG?

Let $G:\{0,1\}^{*} \mapsto \{0,1\}^{*}$ be a secure PRG. Prove or disprove that the following construction also yields a secure PRG. $$G'(k) = G(k||0),$$ where $||$ denotes the concatenation of two strings.

I understand that proving/disproving such constructions usually involves a proof by reduction or a counterexample. Intuitively, I would say that $G'$ is a secure PRG, since we only fix a bit of the input, which should not make the output distinguishable (in polynomial time). However, for some reason I can't finde the right reduction, since I don't see how a $w \in \{0,1\}^{*}$ and a distinguisher $D'$ for $G'$ can be used to construct a distinguisher for $D$ for $G$.

So is $G'$ a secure PRG? If yes, how can I construct a valid reduction and if no, how does a distinguisher for $G'$ work?

I don't know if it is appropriate, but I would prefer hints, which point me in the right direction instead of complete solutions.

• Is the input space of your PRG really $\{0,1\}^*$? If so, what's the distribution of the inputs? (It can't be uniform, since there is no uniform distribution over $\{0,1\}^*$.) Commented Oct 27, 2013 at 18:09
• @Ilmari : $\:$ The distribution of the inputs is uniform on $\{\hspace{-0.01 in}0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^n$, and security is that the amount a $\hspace{.4 in}$ feasible adversary can distinguish by is a negligible function of $n$. $\;\;\;\;$
– user991
Commented Oct 27, 2013 at 21:57
• Much bigger hint: $\:$ What happens if the last bit of G's output is always equal to the last bit of G's input? $\;$
– user991
Commented Oct 27, 2013 at 22:08
• @RickyDemer No that didn't do it as it was written as a comment instead of an answer :P Commented Oct 30, 2013 at 16:34
• @RickyDemer Could somebody either please answer or delete this question? Commented Nov 3, 2013 at 21:22