# 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= <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?

-
If a function $G$ has $G(k) = G(k+1)$ (and if $+$ is addition of natural numbers), then $G$ is a constant function, and I don't think this qualifies as a PRG. –  Paŭlo Ebermann Feb 1 at 11:33
@PaŭloEbermann - note that it holds for even inputs $k$. so if it's true - it means that each to consecutive inputs to $G$ yield the same output. (If $k$ is odd the it's not mandatory that $G(k)=G(k+1)$ , only that $G(k)=G(k-1)$. –  Bush Feb 1 at 11:36
And since the attacker doesn't control the input to a PRG he cannot distinguish between its output and a random string. This is my intuition, I just don't know how to prove. –  Bush Feb 1 at 11:38
I'm confused, the PRG has to meet some criteria? You can take any PRNG and just clone each block of the required size twice. –  daniel Feb 1 at 13:04
Well, that's my question.. why does the cloned is considered as a PRG? How can you prove that the cloned is a PRG as well? –  Bush Feb 1 at 13:20

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

-

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

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.

-
Next time you edit any of your questions or answers, do us a favour and login first. I gave an OK this time, but generally… edits are bound to be rejected if you post them as "anonymous user". Just stating "I am Diagon" doesn't really help verifying it's actually you who is proposing an edit. As said: next time, login to Crypto.SE! –  e-sushi Feb 1 at 22:43
@e-sushi - perhaps you would like to take a look here: meta.stackexchange.com/questions/218477/… If you are a moderator, perhaps you could have a bit more patience. Thanks. –  Diagon Feb 4 at 7:54
No, I'm not a moderator. Depending on gained reputation, community members can vote to confirm or ignore edits. Your edit showed up as anonymous, which can lead to edits being non-trusted and therefore voted to be ignored. Didn't want to step on your toes or anything... it's just that some new members forget to login. That's why I wrote "do us a favor and login". Maybe it might have sounded a bit harsh or cynical, but it wasn't - logging in really makes life easier for us all, so it is a favor. Anyway, just read your meta post and now understand. Hope things work for you soon. Btw: Welcome. ;) –  e-sushi Feb 4 at 13:46
@e-sushi; @Diagon: I was the other reviewer on this, and was very close to rejecting it. Since it was submitted as anon there was no way of knowing if it was a legitimate edit or not. In the end i decided to let it through since you could always rollback once logged in and it wouldn't loose you your writing if legitimate. –  figlesquidge Feb 4 at 14:02
The Wikipedia page on cryptographically secure pseudo-random generators isn't a good reference, because it requires "backtracking resistance", which is non-standard. Also, the best definition of pseudo-random generator uses indistinguishability, not next-bit-unpredictability. The two notions are equivalent, of course, but the indistinguishability definition is best. –  K.G. Feb 5 at 8:49