# If $G$ is a PRG, is $F(s)=G(S)||G(\bar{s})$ necessarily a PRG?

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!

• @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$? Oct 2, 2018 at 18:30
• @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? Oct 3, 2018 at 0:02
• My previous counterexample (now deleted) was both flawed by the lacks of a bar, and unnecessarily complex. Here is another.
– fgrieu
Oct 3, 2018 at 6:30

$$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.

• 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)$ Oct 3, 2018 at 10:44
• @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.
– fgrieu
Oct 3, 2018 at 12:04
• 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. Oct 3, 2018 at 12:10
• @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? Oct 3, 2018 at 12:54
• @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
– fgrieu
Oct 3, 2018 at 13:46