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

I argue it is because there should be no more correlation between the outputs $G(s0^{|s|})$ than between the outputs $G(s)$. Thus we can say the $G'(s)$ is a PRNG that satisfies $|G'(s)| \geq 4|s|$. If we let $s' = s0^{|s|}$ and denote the set of all $s'$ by $S'$, then $s'$ should be chosen uniformly at random from $S'$. Since, as I stated there should be no correlation between $G'(s')$ for any $s'$, then effectively we are only increasing the expansion factor $l$.

Disagree? Please tell me why.

share|improve this question

closed as unclear what you're asking by D.W., figlesquidge, e-sushi, rath, archie Mar 15 '14 at 0:23

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

I attempted the same editing, but wondered if $s0$ is meant to be $s_0$, or something else; and in either case those come from nowhere and I fail to parse the question. – fgrieu Mar 2 '14 at 18:10

Suppose g is a PRNG. $\:$ Define G by the following pseudocode:

def G(w):
 m = length(w)
 n = ceiling(m/2)
 set x equal to the n leftmost bits of w
 set y equal to the m-n rightmost bits of w
 z = concatenate(g(x),y)
 output z

In this case, G is a PRNG and G' is not a PRNG.

share|improve this answer
The way you wrote this was not clear. If I understand you correctly you mean to say: "Let G(s) be a PRNG. Then where $s = s_1, \dots ,s_n$ define $G'(s) = G(s_1, \dots ,s_{n/2})||(s_{(n/2)+1, \dots, s_n)$, where $||$ denotes the concatenation. In this case G'(s) is not a PRNG." – fowlslegs Mar 2 '14 at 17:36

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