1
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jjang Apr 7 '16 at 19:42
  • $\begingroup$ 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. $\endgroup$ – Jjang Apr 7 '16 at 19:49
  • $\begingroup$ 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". $\endgroup$ – Suphanat Chunhapanya Apr 7 '16 at 22:50
  • $\begingroup$ 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? $\endgroup$ – Jjang Apr 9 '16 at 17:11
  • $\begingroup$ Please? 2 weeks have passed and I have no clue. $\endgroup$ – Jjang Apr 29 '16 at 18:09

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.