# Combining multiple PRGs together

Got some theoretical questions about PRGs to solve (given by lecturer for self-learning, no score involved).

Tried to find on the internet but couldn't figure out how to solve them, so I will mention my own intuition but I would appreciate a formal answer to the questions to fully understand.

$G_1$ , $G_2$ are safe PRGs in range $\{0,1\}^n \rightarrow \{0,1\}^{2n}$, s.t. $G_1 \not = G_2$. Is $G$ necessarily a PRG? Prove your answer.

1. $G(s) = G_1(s) \oplus G_2(s)$
2. $G(s) = \overline{G_1(s)} \oplus G_2(s)$
3. $G(s) = G_1(s) \oplus G_2(s \oplus 1^{|s|})$
4. $G(s) = \overline{G_1(s)} \oplus G_2(s \oplus 1^{|s|})$
5. $G(s) = G_1(s) \oplus G_2(0^{|s|})$
6. $G(s) = \overline{G_1(s)} \oplus G_2(0^{|s|})$
7. $G(s) = \overline{G_1(s) \oplus G_2(0^{|s|})}$

Now $G$ is in range $\{0,1\}^n \rightarrow \{0,1\}^{n+1}$. Is $G'$ necessarily a PRG? Prove your answer.

1. $G'(s) = G(s \oplus s^R)$ ($R$ is reverse)
2. $G'(s) = G(s \oplus G(s)^{1,...,n})$ ($G(s)^{1,..,n}$ stands for $G(s)$ first $n$-bits).

Intuition:

I belive XOR maintains the PRG attribute, so a. (and therefore b.) is true.

In 3. we essentialy flipping the bits of $G_2$ input, can't see any harm at this, same goes for d. but we flip bits of result.

Well, I think I should stop the guessing now and get a true answer for the questions, since I really have no clue.

No, A is not true.

Suppose that $G_1$ is a secure PRG and $G_2(s) = G_1(s) \oplus 1$, obviously $G_2 \neq G_1$ and $G_2$ is a secure PRG.

You can see that $G(s) = G_1(s) \oplus G_2(s) = G_1(s) \oplus G_1(s) \oplus 1 = 1$ which is obviously not a secure PRG.

Now you have a hint. You should think the rest of the problems.

• Thanks alot for the direction. I'd like to verify my answer with you. So b can be easily solved using the above method. in c-d we use the same idea but we pick G2(s XOR 1) = G1(s XOR 1) XOR 1, so we get G = 1. In e we choose G1 = 𝐺2(0^|𝑠|) XOR 1 so G = 1. f is the same, we pass the above G1 but with NOT upperline (so it cancels each other). In g, the solution is like e. Am I right? P.S. no clue regarding h and i. – Jjang Apr 7 '16 at 19:42
• Regarding i, I got a little idea that might show that it IS a PRG. Since G is PRG, then the first n bits of G are also random, XOR with s must also be random, so we got random seed as an input to the outer G which is PRG, so G1 is PRG. – Jjang Apr 7 '16 at 19:49
• I thought, for c, it should be $G_2(s) = G_1(s \oplus 1^{|s|}) \oplus 1$. For d, it should be $G_2(s) = \overline{G_1(s \oplus 1^{|s|})} \oplus 1$. For e,f,g, they are secure PRGs, since $G_2(0^{|s|})$ is just a constant. Finally, you should be careful with this sentence "XOR with s must also be random". – Suphanat Chunhapanya Apr 7 '16 at 22:50
• Why does G2(0^|s|) imply that e,f,g are secure PRGs? Constant or not, I showed G1 such that G is always 1... how can G be safe? And also, got any idea about h,i? – Jjang Apr 9 '16 at 17:11
• Please? 2 weeks have passed and I have no clue. – Jjang Apr 29 '16 at 18:09