# If G is a secure PRG and G' is a function of G, is G' secure?

For example: for secure PRG G if I have a G' s.t. G'(k) = G(k)||0, is G' necessarily secure? This question is not for the above example only but for any other possibilities as well. My thinking is that since G is secure (ADV is negligible and PRG is unpredictable), then no matter what I do with G to make G', G' is secure.

• This feels like a homework question to me. Is it? – pg1989 Jan 11 '14 at 0:16
• My question is not the HW problem, it is something I am gathering after doing it and wondering if it is true. – arynhard Jan 11 '14 at 0:19
• Your example is already sufficient to contradict your intuition. If the last bit is always zero can the output of $G'$ be indistinguishable from uniformly random strings? – DrLecter Jan 11 '14 at 0:24
• Oh man, it is distinguishable. Thank you. So is it the advantage in the case of my example that would make G' insecure? – arynhard Jan 11 '14 at 0:29

Hint: Consider the function $G'(k) = f(G(k))$, where $f(x) = 0$ for all $x$. Clearly, $G'$ is a function of $G$. Is $G'$ a secure PRG?
A(x): If the last bits of x is 0 output 1. Otherwise output 0. Then $$Pr[A(G(k)) = 1]= 0$$ for random $k \in K$, where $K$ is the key space, and $$Pr[A(r)=1 ]=1/2$$ for random $r \in \{0,1\}^n$. So $$ADV(A,G) = |0-1/2| = 1/2$$ Which is clearly non-negligible.
• This question is almost 3 years old, and this is just a repetition of what DrLecter wrote in the comments. Even for a full answer, it is lacking the main statement that the example in the question isn't a PRF in the first place. Since the question was explicitly about general constructions for $G'$, this answer doesn't adress the question. – tylo Oct 20 '16 at 11:46