0
$\begingroup$

Let $G$ be a pseudorandom generator, and $F(s)=G(s)||G(\bar{s})$ (where $\bar{s}$ denotes the bitwise complement of $s$), is $F$ necessarily a PRG?

My intuition says that it is a PRG, as clearly $G(s)$ and $G(\bar{s})$ are PRGs on their own, and concatenating them shouldn't affect the randomness, but rather it will simply increase the expansion factor (length of output). However, I feel like there exists a counterexample where $G(s)$ and $G(\bar{s})$ are secure on their own but concatenating them will lose some randomness, i.e. make them predictable (because $F(s)$ and $F(\bar{s})$ should look pretty similar). I've thought about some examples where $G(s)=H(s) \oplus H(\bar{s})$, where $H(s)$ is a PRG (and $G(s)$ would also still be a PRG here), but I'm not sure if this leads to $F(s)$ not being a PRG. Any thoughts would be appreciated!

$\endgroup$
  • $\begingroup$ @fgrieu I'm struggling to think of a scenario where knowing $G(s)$ and $G(\overline{s})$ would allow you to deduce $s$, since by definition $G(s)$ and $G(\overline{s})$ are completely unrelated to each other and by seeing their outputs, you shouldn't be able to tell that the inputs are related (or $G$ wouldn't be a PRG). Proceeding with $H(t)$ where $|t|=|s|-1$, I guess you can build $G(s)=H(s)||b$, where $b$ is a random bit, but I'm unsure where to go from here as this would only leak two bits in $F(s)$, and certainly wouldn't leak all of $s$? $\endgroup$ – user3043904 Oct 2 '18 at 18:30
  • $\begingroup$ @fgrieu so working out $F(s)$ with $G(s)=H(s_{0}...s_{n-1})$ if $s_{n}=0$, and $G(s)=H'(s_{0}...s_{n-1})$ if $s_{n}=1$, I get that $F(s)=G(s)||G(\overline{s})=H(s_{0}...s_{n-1})||H(s_{0}...s_{n-1})$ if $s_{n}=0$, and $F(s)=H'(s_{0}...s_{n-1})||H'(s_{0}...s_{n-1})$ if $s_{n}=1$. If this sufficient to show that $F(s)$ is not a PRG, because it's output is the same thing concatenated with itself? Because this doesn't leak anything about the input $s$, since $H(s_{0}...s_{n-1})$ is still a PRG, but I'm not sure if concatenating it with itself violates PRG properties? $\endgroup$ – user3043904 Oct 3 '18 at 0:02
  • $\begingroup$ My previous counterexample (now deleted) was both flawed by the lacks of a bar, and unnecessarily complex. Here is another. $\endgroup$ – fgrieu Oct 3 '18 at 6:30
2
$\begingroup$

$F(s)=G(s)\mathbin\|G(\bar{s})$ is not necessarily a PRG. We'll construct a counterexample.

Assume $H(t)$ is a PRG.

Now define $G(t\mathbin\|0)=H(t)$ and $G(t\mathbin\|1)=H(\bar t)$. The $G(s)$ thus defined is a PRG with input width $|t|+1$. Yet $F(s)=G(s)\mathbin\|G(\bar s)$ is not a PRG, because its two halves are always equal.

$\endgroup$
  • $\begingroup$ Do we really need $G(t\mathbin\|1)=H(\bar t)$? I think it can be any PRF, as $G(t\mathbin\|1)=K(t)$ $\endgroup$ – kelalaka Oct 3 '18 at 10:44
  • 1
    $\begingroup$ @kelalaka: I do not see how the distinction of $G(s)\mathbin\|G(\bar{s})$ from a PRG would work for $G(t\mathbin\|0)=H(t)$ and $G(t\mathbin\|1)=K(t)$ with $H$, $K$ two unrelated PRGs. I do see many other possible counterexamples. $\endgroup$ – fgrieu Oct 3 '18 at 12:04
  • $\begingroup$ I saw that the $G(t||1)$ only need to be defined to be a PRG. In the proof, you use the complement of it , so I can put any PRG there? the $H( \bar t)$ confused me at the beginning. $\endgroup$ – kelalaka Oct 3 '18 at 12:10
  • $\begingroup$ @fgrieu why does a function whose output is the same thing concatenated with itself (i.e. two halves are always equal) necessarily not a PRG? These two halves are uniformly distributed and don't reveal anything about the input, what property of PRG does this violate? My understanding of a PRG is that it must have some stretch factor $\ell(s)>s$ so that $|\ell(s)|>|s|$, and that it's output must be indistinguishable from a uniform, $U_{\ell(s)}$ bit string. Is the problem with the function you've constructed that a distinguisher can easily tell it apart from a uniform string? $\endgroup$ – user3043904 Oct 3 '18 at 12:54
  • 1
    $\begingroup$ @user3043904: the property violated is "output must be indistinguishable from a uniform"(ly random output). Illustration: one of the following two hex strings is drawn uniformly at random, the other is the same thing concatenated with itself. Can you distinguish which is uniformly random? E299608B1105BAA4D534E37A860CFE69 616A3400F498345A616A3400F498345A $\endgroup$ – fgrieu Oct 3 '18 at 13:46

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.