Can you prove the existance of a PRG $G$ s.t. for each even $k$: $G(k)=G(k+1)$?

Question

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= <G(k) \oplus m_1, G(k+1) \oplus m_2>$

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?

Answer 1

One point of the exercise is to show that you may run into trouble if you use related keys, because the ordinary security notions do not provide any guarantees in that case.

Recall the security definition of a pseudo-random generator: sample x uniformly at random from $\{0,1\}^n$, compute $y_0 = G(x)$, sample $y_1$ uniformly at random from $\{0,1\}^{n+1}$, flip a coin $b$, give the adversary $y_b$. The adversary must now determine the coin flip $b$.

Consider first the "obvious" construction. Let $F: \{0,1\}^n \rightarrow \{0,1\}^{n+1}$ be a pseudo-random generator. Define $G$ to be $$G(x_1x_2\dots x_n) = F(x_1x_2\dots x_{n-1}0),$$ that is, clear the final bit before evaluating $F$.

Intuitively, this should work. If I can distinguish $G$'s output, I can distinguish "half" of $F$'s outputs, which should be sufficient.

Unfortunately, there are counterexamples. Given any pseudo-random generator $H: \{0,1\}^{n-1} \rightarrow \{0,1\}^n$, we can construct a pseudo-random generator $F: \{0,1\}^n \rightarrow \{0,1\}^{n+1}$ using $$F(x_1x_2\dots x_{n-1}x_n) = H(x_1x_2\dots x_{n-1}) || x_n .$$ If $H$ is secure, then $F$ is also secure. But if you insert this generator into the above construction, you get a $G$ that is easy to distinguish (final bit is always $0$). Which is bad.

Instead, you should start with a generator $F: \{0,1\}^{n-1} \rightarrow \{0,1\}^{n+1}$ and use $$G(x_1x_2\dots x_{n-1}x_n) = F(x_1x_2\dots x_{n-1}).$$ If $F$ is secure, then $G$ is secure, and $G$ has the desired property.

(Note that you can go from a one-bit expander $H: \{0,1\}^{n-1} \rightarrow \{0,1\}^n$ to a two-bit expander $F: \{0,1\}^{n-1} \rightarrow \{0,1\}^{n+1}$ using standard constructions.)

(Note II: For any given pseudo-random generator $\{0,1\}^n \rightarrow \{0,1\}^{n+1}$, I expect to be able to construct a good pseudo-random generator $\{0,1\}^{n-1} \rightarrow \{0,1\}^n$. However, I suspect that there's no generic construction.)

Answer 2

@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:

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

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.