Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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
1  
This feels like a homework question to me. Is it? –  pg1989 Jan 11 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 at 0:19
1  
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 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 at 0:29
add comment

1 Answer 1

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 at 0:24
add comment

Your Answer

 
discard

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.