3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user13676 Jul 30 '15 at 10:51
  • $\begingroup$ Oh, so based on the non-true randomness of the seed, is legitimate to conclude that the corresponding construction can't possibly be pseudorandom? $\endgroup$ – pa5h1nh0 Jul 30 '15 at 10:56
  • $\begingroup$ Yes, I refer you to "introduction to modern cryptography" , 1st edition, page 213-214. $\endgroup$ – user13676 Jul 30 '15 at 11:03
  • $\begingroup$ Ok. Could you please add an answer as your first comment above, so that the question can be completed? Thank you very much. $\endgroup$ – pa5h1nh0 Jul 30 '15 at 11:14
  • $\begingroup$ @user13676 The seed is $s$, and it is uniformly chosen. $\endgroup$ – fkraiem Jul 30 '15 at 11:44
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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). $\endgroup$ – pa5h1nh0 Jul 30 '15 at 11:32
  • $\begingroup$ 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. $\endgroup$ – fkraiem Jul 30 '15 at 11:39
  • $\begingroup$ 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". $\;\;\;\;$ $\endgroup$ – user991 Jul 30 '15 at 11:57
  • 1
    $\begingroup$ @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. $\endgroup$ – fkraiem Jul 30 '15 at 12:41
  • 1
    $\begingroup$ 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. $\endgroup$ – fkraiem Jul 30 '15 at 13:20
0
$\begingroup$

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.

$\endgroup$

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.