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$
5
  • 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, 2015 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, 2015 at 10:56
  • $\begingroup$ Yes, I refer you to "introduction to modern cryptography" , 1st edition, page 213-214. $\endgroup$
    – user13676
    Jul 30, 2015 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, 2015 at 11:14
  • $\begingroup$ @user13676 The seed is $s$, and it is uniformly chosen. $\endgroup$
    – fkraiem
    Jul 30, 2015 at 11:44

2 Answers 2

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$
13
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 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 and acknowledge you have read our privacy policy.

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