Return to Answer

This basically says that a PRG produces a "scatter" of points on the image set that approximates the uniform distribution. More precisely, if we consider a set E in the image set of the PRG, then the measure of the set of points that the PRG maps into E is very close to the measure of E.

(Since we are essentially always dealing with finite sets and uniform distributions, then we are saying that the fraction of the domain that is mapped into E is very close to the fraction of the image that is represented by E. In technicalese, "the pushforward of the uniform measure on the domain via the PRG is uniform".)

So, let's suppose we have a PRG F: DF -> I.

Define a new function G: DG -> I, st. G(2n)=F(n) and G(2n+1) = F(n).

1. g(k) = F([|k/2|]), where [|x|] is the greatest integer <= x.
2. |DG| = 2|DF|, where |S| is the number of points in the set S.

For a set E on the image space, the number of points that map into it via G is just 2x the number of points that map into it by F. On the other hand, the domain of G is twice as big as the domain of F. So the measure of the preimages via F and G are the same. So, if F approximates the uniform distribution on I, then so does G. Therefore, if F is a PRG, then so is G.

The reason we would want the next bit test in our definition is clear. The whole point is that the CSPRG should give us a (one time) semantically secure stream cypher. If the first few bits could give us some information about the next bit that the PRG generates, then this would give us some information to distinguish the PRG output from uniformly random. So, given messages m1, m2 and a ciphertext c, we could distinguish which of m1 (+) c or m2 (+) c is more likely to be the output of the PRG. That would allow us to break semantic security.

I think the restriction on state compromise, may be just an extension of this. If we generate a key by concatenating shorter keys: F(n)||F(n+1)||F(n+2)||..., we don't want exposure of one part of the key, F(k), to give us information about previous or later parts of the key, eg F(k-1) or F(k+1).

At first glance it appears to me that if F satisfies the next bit test, then so will G. On the other hand, If some of G's state is revealed (eg, G(k) != G(k+1)), then we can predict a part of it's past (G(k-1) = G(k)) and future (G(k+1) = G(k+2)).

This basically says that a PRG produces a "scatter" of points on the image set that approximates the uniform distribution. More precisely, if we consider a set $E$ in the image set of the PRG, then the measure of the set of points that the PRG maps into $E$ is very close to the measure of $E$.

(Since we are essentially always dealing with finite sets and uniform distributions, then we are saying that the fraction of the domain that is mapped into $E$ is very close to the fraction of the image that is represented by $E$. In technicalese, "the pushforward of the uniform measure on the domain via the PRG is uniform".)

So, let's suppose we have a PRG $F: DF \rightarrow I$.

Define a new function $G: DG \rightarrow I$, st. $G(2n)=F(n)$ and $G(2n+1) = F(n)$.

1. $ g(k) = F([|k/2|])$, where $[|x|]$ is the greatest integer $<= x$.
2. $|DG| = 2|DF|$, where $|S|$ is the number of points in the set $S$.

For a set $E$ on the image space, the number of points that map into it via $G$ is just $2x$ the number of points that map into it by $F$. On the other hand, the domain of $G$ is twice as big as the domain of $F$. So the measure of the preimages via $F$ and $G$ are the same. So, if $F$ approximates the uniform distribution on $I$, then so does $G$. Therefore, if $F$ is a PRG, then so is $G$.

The reason we would want the next bit test in our definition is clear. The whole point is that the CSPRG should give us a (one time) semantically secure stream cypher. If the first few bits could give us some information about the next bit that the PRG generates, then this would give us some information to distinguish the PRG output from uniformly random. So, given messages $m_1, m_2$ and a ciphertext $c$, we could distinguish which of $m_1 \oplus c$ or $m_2 \oplus c$ is more likely to be the output of the PRG. That would allow us to break semantic security.

I think the restriction on state compromise, may be just an extension of this. If we generate a key by concatenating shorter keys: $F(n)||F(n+1)||F(n+2)|| \ldots$, we don't want exposure of one part of the key, $F(k)$, to give us information about previous or later parts of the key, eg $F(k-1)$ or $F(k+1)$.

At first glance it appears to me that if $F$ satisfies the next bit test, then so will $G$. On the other hand, If some of $G$'s state is revealed (eg, $G(k) != G(k+1))$, then we can predict a part of it's past ($G(k-1) = G(k)$) and future ($G(k+1) = G(k+2)$).

Look at this definition of a PRG.

Notice that:

... On second inspection ... While the above is correct for a PRG, I don't think it's correct for a CSPRG ("Cryptographically Secure PRG"), which is a more restricted notion that includes the "next bit test", along with the ability to withstand state compromise. See here: http://en.m.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator

I'd like to think more on this, but at first glance it appears to me that if F satisfies the next bit test, then so will G. On the other hand, If some of G's state is revealed (eg, the input is odd), then we can predict a part of it's past (the previous pseudo-random number).

If I have more thoughts I'll add more later, but I'd like to hear from others if they know more.

@Bush - What you really mean to ask is whether there is a "Cryptographically Secure" PRG (CSPRG) that has the property you describe. The nature of PRG's and CSPRG's remain to me a bit deep and obscure - and to some extent I think this might be intrinsic, the whole field of crypto may be embedded in this one question on the nature of pseudo-randomness; but I'll give it a go.

Let's start with the PRG. You can find a definition here.

We have:

While I belive the above is correct for a PRG, a CSPRG is a more restricted notion that includes the "next bit test", along with the ability to withstand state compromise. See here.

The reason we would want the next bit test in our definition is clear. The whole point is that the CSPRG should give us a (one time) semantically secure stream cypher. If the first few bits could give us some information about the next bit that the PRG generates, then this would give us some information to distinguish the PRG output from uniformly random. So, given messages m1, m2 and a ciphertext c, we could distinguish which of m1 (+) c or m2 (+) c is more likely to be the output of the PRG. That would allow us to break semantic security.

I think the restriction on state compromise, may be just an extension of this. If we generate a key by concatenating shorter keys: F(n)||F(n+1)||F(n+2)||..., we don't want exposure of one part of the key, F(k), to give us information about previous or later parts of the key, eg F(k-1) or F(k+1).

At first glance it appears to me that if F satisfies the next bit test, then so will G. On the other hand, If some of G's state is revealed (eg, G(k) != G(k+1)), then we can predict a part of it's past (G(k-1) = G(k)) and future (G(k+1) = G(k+2)).

I hope that helps. I'll be watching eagerly if someone has something to add.

Look at this definition of a PRG.

This basically says that a PRG produces a "scatter" of points on the image set that approximates the uniform distribution. More precisely, if we consider a set E in the image set of the PRG, then the measure of the set of points that the PRG maps into E is very close to the measure of E.

(Since we are essentially always dealing with finite sets and uniform distributions, then we are saying that the fraction of the domain that is mapped into E is very close to the fraction of the image that is represented by E. In technicalese, "the pushforward of the uniform measure on the domain via the PRG is uniform".)

So, let's suppose we have a PRG F: DF -> I.

Define a new function G: DG -> I, st. G(2n)=F(n) and G(2n+1) = F(n).

Notice that:

1. g(k) = F([|k/2|]), where [|x|] is the greatest integer <= x.
2. |DG| = 2|DF|, where |S| is the number of points in the set S.

For a set E on the image space, the number of points that map into it via G is just 2x the number of points that map into it by F. On the other hand, the domain of G is twice as big as the domain of F. So the measure of the preimages via F and G are the same. So, if F approximates the uniform distribution on I, then so does G. Therefore, if F is a PRG, then so is G.

Look at this definition of a PRG.

This basically says that a PRG produces a "scatter" of points on the image set that approximates the uniform distribution. More precisely, if we consider a set E in the image set of the PRG, then the measure of the set of points that the PRG maps into E is very close to the measure of E.

(Since we are essentially always dealing with finite sets and uniform distributions, then we are saying that the fraction of the domain that is mapped into E is very close to the fraction of the image that is represented by E. In technicalese, "the pushforward of the uniform measure on the domain via the PRG is uniform".)

So, let's suppose we have a PRG F: DF -> I.

Define a new function G: DG -> I, st. G(2n)=F(n) and G(2n+1) = F(n).

Notice that:

1. g(k) = F([|k/2|]), where [|x|] is the greatest integer <= x.
2. |DG| = 2|DF|, where |S| is the number of points in the set S.

For a set E on the image space, the number of points that map into it via G is just 2x the number of points that map into it by F. On the other hand, the domain of G is twice as big as the domain of F. So the measure of the preimages via F and G are the same. So, if F approximates the uniform distribution on I, then so does G. Therefore, if F is a PRG, then so is G.

... On second inspection ... While the above is correct for a PRG, I don't think it's correct for a CSPRG ("Cryptographically Secure PRG"), which is a more restricted notion that includes the "next bit test", along with the ability to withstand state compromise. See here: http://en.m.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator

I'd like to think more on this, but at first glance it appears to me that if F satisfies the next bit test, then so will G. On the other hand, If some of G's state is revealed (eg, the input is odd), then we can predict a part of it's past (the previous pseudo-random number).

If I have more thoughts I'll add more later, but I'd like to hear from others if they know more.