# Knowing that $G(s)$ is a PRG, is the following construction $G'(s) = G(s||0)$ a PRG?

I know there already is a very similar question. However, I can't understand why $G'(s)$ is not a PRG. If $G(s)$ is a PRG, then why $G(s||0)$ can't also be a PRG? How can the distribution over $G(s||0)$ be distinguished from a truly uniform distribution of the same output range?

• Please note that the input $s$ must be defined as: $s\leftarrow \{0,1\}^n$. In other words, $s$ must be chosen uniformly at random, whereas in your case $s||0$ is not a uniformly random value. – user13676 Jul 30 '15 at 10:51
• Oh, so based on the non-true randomness of the seed, is legitimate to conclude that the corresponding construction can't possibly be pseudorandom? – pa5h1nh0 Jul 30 '15 at 10:56
• Yes, I refer you to "introduction to modern cryptography" , 1st edition, page 213-214. – user13676 Jul 30 '15 at 11:03
• Ok. Could you please add an answer as your first comment above, so that the question can be completed? Thank you very much. – pa5h1nh0 Jul 30 '15 at 11:14
• @user13676 The seed is $s$, and it is uniformly chosen. – fkraiem Jul 30 '15 at 11:44

Knowing that $G(s)$ is a PRG, is the following construction $G'(s) = G(s||0)$ a PRG?

Maybe.

If $G(s)$ is a PRG, then why $G(s||0)$ can't also be a PRG?

$G'$ can "also be a PRG". (It's just not necessarily also a PRG.)

How can the distribution over $G(s||0)$ be distinguished from a truly uniform distribution of the same output range?"

$G$ can be such that the last bit of its output is always equal to the last bit of its input.

• "The last bit of $G$'s output can always equal the last bit of $G$'s input" - now this is what I don't understand, because you're assuming to know that in advance (how? why?). The only thing I see here is that the input to $G$ has an extra bit at index '0' fixed to $0$, but this doesn't say you nothing about the possible output, this doesn't mean that the output's bit at index '0' will also be 0 (it can also be 1, as $G$ is pseudorandom). – pa5h1nh0 Jul 30 '15 at 11:32
• It is possible that the last bit of $G$'s output equals the last bit of the seed, in this case $G'$ is not a pseudorandom generator. – fkraiem Jul 30 '15 at 11:39
• One can "know that in advance" by choosing $G$. $\:$ "this doesn't say you nothing about the possible output," which is why the answer to your title is "Maybe". $\;\;\;\;$ – user991 Jul 30 '15 at 11:57
• @pa5h1nh0 Also, I notice that answers to your questions tend to have a comment thread which degenerates into a discussion, which is not allowed here. You must ask precise questions so that it is possible to know what you are asking without a discussion. – fkraiem Jul 30 '15 at 12:41
• First, what's a "99% PRG"? Either $G$ is a PRG or it is not. Second, that's not how your original question is worded: your question was "why $G'$ can't be a PRG?" There is no general answer as to whether or not $G'$ is a PRG, as both cases are possible. It is possible that $G$ is a PRG and that $G'$ is, and it is also possible that $G$ is a PRG and $G'$ is not. – fkraiem Jul 30 '15 at 13:20

no , assuming the existence of a PRG G , then you can construct another PRG H , H defined as follow : $H(s_1,,,,s_n)=G(s_1||s_2||...||s_{n-1})||s_n$ , you can prove that H is indeed a PRG , so if you use H instead of G in your construction above , you will get that the last bit is always 0 which is obviously not a PRG.