3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This feels like a homework question to me. Is it? $\endgroup$ – pg1989 Jan 11 '14 at 0:16
  • $\begingroup$ My question is not the HW problem, it is something I am gathering after doing it and wondering if it is true. $\endgroup$ – arynhard Jan 11 '14 at 0:19
  • 2
    $\begingroup$ 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? $\endgroup$ – DrLecter Jan 11 '14 at 0:24
  • $\begingroup$ Oh man, it is distinguishable. Thank you. So is it the advantage in the case of my example that would make G' insecure? $\endgroup$ – arynhard Jan 11 '14 at 0:29
3
$\begingroup$

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?

| improve this answer | |
$\endgroup$
3
$\begingroup$

Of course not. We can define a simple statistical test A as:

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – tylo Oct 20 '16 at 11:46

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.