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.

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 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 at 18:10
add comment

1 Answer 1

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 at 17:36
add comment

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