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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Apr 7, 2016 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
    Commented Apr 7, 2016 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
    Commented Apr 7, 2016 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
    Commented Apr 9, 2016 at 17:11
  • $\begingroup$ Please? 2 weeks have passed and I have no clue. $\endgroup$
    – Jjang
    Commented Apr 29, 2016 at 18:09

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.