Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
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
up vote 1 down vote accepted

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?

share|improve this answer
No it is not. Thank you for the example. – arynhard Jan 11 '14 at 0:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.