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.

  • 1
    $\begingroup$ 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\}^*$.) $\endgroup$ – Ilmari Karonen Oct 27 '13 at 18:09
  • $\begingroup$ @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$. $\;\;\;\;$ $\endgroup$ – user991 Oct 27 '13 at 21:57
  • 1
    $\begingroup$ Much bigger hint: $\:$ What happens if the last bit of G's output is always equal to the last bit of G's input? $\;$ $\endgroup$ – user991 Oct 27 '13 at 22:08
  • $\begingroup$ @RickyDemer No that didn't do it as it was written as a comment instead of an answer :P $\endgroup$ – Maarten Bodewes Oct 30 '13 at 16:34
  • $\begingroup$ @RickyDemer Could somebody either please answer or delete this question? $\endgroup$ – Maarten Bodewes Nov 3 '13 at 21:22

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.