Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
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
up vote 0 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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