# 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\}^*$.) – Ilmari Karonen Oct 27 '13 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$. $\;\;\;\;$ – Ricky Demer Oct 27 '13 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? $\;$ – Ricky Demer Oct 27 '13 at 22:08
@RickyDemer thanks, that dit it. – user1658887 Oct 29 '13 at 17:35
@RickyDemer No that didn't do it as it was written as a comment instead of an answer :P – Maarten Bodewes Oct 30 '13 at 16:34

## 1 Answer

If there exists a secure PRG, then there is a secure PRG
whose last bit of output is always equal the last bit of its input.
If the last bit of G's output is always equal to the last bit of G's input, then the
function G' constructed as described in the question will not be a secure PRG.

-