Can you prove the existance of a PRG $G$ s.t. for each even $k$: $G(k)=G(k+1)$? In one of the exercises in [KL] Book I need to tell whether an encryption scheme is secure under an eavesdropper of only one message.

Given a PRG $G: \{0,1\}^n \rightarrow \{0,1\}^{n+1}$. The encryption scheme encrypt $m \in \{0,1\}^{2n+2}$ by $c= &lt;G(k) \oplus m_1, G(k+1) \oplus m_2&gt;$

where $m_1$ and $m_2$ are the first and second halves of $m$.

Clearly, this is not CPA-secure. But if I could say that there exist PRGs such that for each even $k$: $G(k)=G(k+1)$ I would say that it's even not secure against an eavesdropper of only one message since the adversary can check if $m_1 \oplus m_2= c_1 \oplus c_2$ which will be true whenever $k$ is even which happens with probability of $1/2$.

So: how can I prove that such PRG exists?
@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.

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)$.  

We have:


$ g(k) = F([|k/2|])$, where $[|x|]$ is the greatest integer $&lt;= x$.
$|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$.

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 $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)$).

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