# Given PRNG $G(s)$, why is $G(s) || G(s+1)$ not a PRNG?

I have given a pseudorandom Generator $G(s)$, $|s|=n$ whose expansion $l(n)$ is $>2n$. I also know that $G^\prime(s) := G(s_1,\ldots,s_{\lfloor\frac{n}{2}\rfloor})$ is a pseudorandom generator. Now the function

$$$L(s) := G(s) ~||~ G(s+1)$$$

with $||$ being concatenation is supposed to be no pseudorandom generator and I struggle to prove it. Intuitively, I would think that since $L$ passes two different seeds to $G$ and $G$ is pseudorandom, $L$ must be pseudorandom too. $G(s+1)$ should be unpredictably different from $G(s+1)$ for a PRNG, should it not? Could someone point me into the right direction?

• I missed the fact that you mix the terms PRG, PRF and PRNG. They are all different. Which does the problem actually concern? – otus Nov 20 '15 at 12:13
• I am not sure what the difference is, but I would label it PRNG. – oarfish Nov 20 '15 at 12:26
• The tag wikis (click tag, then learn more) have some info and Wikipedia has decent articles about them too. – otus Nov 20 '15 at 12:31

$L$ is not necessarily a pseudorandom generator, but it may be. Hence, there is no hope of proving that $L$ is not a pseudorandom generator from what you are given. Rather, you must exhibit a pseudorandom generator $G$ such that $L$ is not a pseudorandom generator. Here is the canonical example with expansion factor $n+1$.

Let $f$ be a one-way permutation (i.e., an injective, length-preserving one-way function). Then it is known that the following is a pseudorandom generator with expansion factor $n+1$:

• Choose uniformly a seed $s$ of even length $s_1s_2\dots s_{2n}$.
• Compute $b = \sum_{i=1}^n s_is_{n+i}$ (with arithmetic in $\mathbf{F}_2$).
• Output $f(s_1s_2\dots s_n)s_{n+1}s_{n+2}\dots s_{2n}b$.

Now, if $s$ is uniformly chosen, with probability $1/2$ its last bit will be $0$, meaning that $s+1$ will be just $s$ with the last bit ($s_{2n}$) flipped, and in turn it means that $G(s+1)$ will equal $G(s)$ except possibly in the last two bits. Hence, a distinguisher can check whether the second half of its input string equals the first one disregarding the last two bits of each. If the string is $G(s)G(s+1)$, this happens with probability at least $1/2$, whereas if the string is truly random this happens with probability $1/2^{n-2}$.

• Can you give a source for why it is known? – oarfish Nov 20 '15 at 13:13
• Any good cryptography textbook (e.g., Goldreich or Katz-Lindell). – fkraiem Nov 20 '15 at 13:14
• @fkraiem I don't think this construction is a pseudorandom generator. Since a distinguisher can always compute the last bit $b$ as described. For a uniform string the probability for last bit to be $\sum_{i=1}^n{s_is_{n+i}}$ is only $1\over2$. And as you mentioned, in Katz's book a similar construction is presented as a counterexample. – wangkaibule Jan 6 '18 at 2:33
• @wangkaibule No, a distinguisher cannot compute $b$, since it does not know the seed (by virtue of $f$'s one-wayness). – fkraiem Jan 6 '18 at 2:58
• @wangkaibule The generator does not output $s_1\dots s_n$; it outputs $f(s_1\dots s_n)$. – fkraiem Jan 6 '18 at 3:06

I would like to improve upon @fkraiem answer (i.e. give a simpler construction):

you must exhibit a pseudorandom generator G such that L is not a pseudorandom generator.


Take any pseudorandom number generator $$PRG : \{0,1\}^{n-1} \rightarrow \{0,1\}^{l(n)}$$. Now define $$G : \{0,1\}^n \rightarrow \{0,1\}^{l(n)}$$ to be $$G(x_1 | x_2 ... | x_n) = PRG(x_1 | x_2 ... | x_{n-1})$$.

I.e. $$G$$ ignores the last input bit and passes the truncated key to $$PRG$$.

$$G$$ is a pseudorandom number generator but $$L = G(s)|G(s+1)$$ is not:

Let's construct a distinguisher $$D$$ that given a number $$x = x_1 | x_2 | ... | x_{2l(n)}$$ tells whether it was sampled uniformly at random, or whether it was generated from $$L$$:

# our distinguisher
fun D(x):
if the first half of x equals to the second half of x:
return 1
else
return 0


If $$x = r$$ is a truly random number, then $$\Pr[D(r) = 1] = 2^{-l(n)}$$

If $$x = L(s)$$ was generated using $$L$$ from a random key $$s = s_1|s_2|...|s_n$$, then at least half of the time G(s) is identical to G(s+1) (because half of the time the last bit $$s_n = 0$$) and so at least half of the time the distinguisher $$D$$ outputs 1, thus the difference

$$|\Pr[D(G(s)) = 1] - \Pr[D(r) = 1]| \geq \frac{1}{2} - 2^{-l(n)}$$ is not negligible.

• You might add a note about the endianness you're assuming for this to work. – Maeher Mar 20 at 14:11

I eventually came up with an answer myself.

Since $|G^\prime| > 2n$, we assume \begin{align*} L(s) & = G^\prime(s) ~||~ G^\prime(s+1) \\ & = G(s_1,\ldots,s_{\lfloor\frac{n}{2}\rfloor}) ~||~ G^\prime(s+1) \\ & = G(s_1,\ldots,s_{\lfloor\frac{n}{2}\rfloor}) ~||~ G(s^\prime) \\ & = G(s_1,\ldots,s_{\lfloor\frac{n}{2}\rfloor}) ~||~ G(s^\prime_1,\ldots,s^\prime_{\lfloor\frac{n}{2}\rfloor}) \\ \end{align*}

Let $D(K)$ be a Distinguisher with $$\begin{equation*} D(K) = \begin{cases} 1 & \text{if k_1,\ldots,k_{\frac{n}{2}} = k_{\frac{n}{2} + 1},\ldots,k_n} \\ 0 & \text{else} \end{cases} \end{equation*}$$

$|K|$ must be even for strings generated by $L$, being the concatenation of two equally long strings. Strings with odd length can thus be immediately identified as random and thus uninteresting.

Adding $1$ to $s$, the probability that a bit in the first half changes is equal to the probability that all bits in the second half are $1$. For $D$ to output $0$ on a string generated by $L$, exactly that case must occur as the second half is cut off and ignored. $$\begin{equation*} P(\text{bit i flipped with i>\frac{n}{2}}) = \frac{1}{2^{\frac{n}{2}}}, \end{equation*}$$ because the lower $\frac{n}{2}$ bits must be $1$.

Hence $$\begin{equation*} P(D(G(s)) = 1) = 1 - P(D(G(s)) = 0) = 1 - \frac{1}{2^\frac{n}{2}} \end{equation*}$$

The probability that in a uniformly random bistring $r$ the upper and lower half are identical (which leads to an erroneous output $D(r)$) is the ratio between the number of possible bitrings with equal halves and all possible bistrings. For half a string, there are $2^{\frac{n}{2}}$ possibilities wo this is also the number of possibilities for strings with equal halves, with $2^n$ total strings.

$$\begin{equation*} P(D(r) = 1) = \frac{2^{\frac{n}{2}}}{2^n} = 2^{-\frac{n}{2}} = \frac{1}{2^\frac{n}{2}} \end{equation*}$$

Furthermore $$\begin{equation*} \left\lvert P(D(G(s)) = 1) - P(D(r) = 1) \right\rvert = \left\lvert1 - \frac{1}{2^\frac{n}{2}} - \frac{1}{2^\frac{n}{2}}\right\rvert = 1 - \frac{2}{2^{\frac{n}{2}}} = 1 - \frac{1}{2^{\frac{n}{2} - 1}} \end{equation*}$$

This is non-negligible and increases with increasing $n$. $L$ is therefore not necessarily pseudorandom.

• A beautiful proof! – user1767774 Nov 16 '17 at 22:37
• @oarfish I don't really understand... Isn't the output of function $L$ behaves just like a pad generated in a CTR cipher (except for $IV$ does not participate in pad directly, but this is another question)? And I also believe that when $s+1$, the probability of "the first half does not change" is equal to the probability of "all bits in the second half are $1$". Or the probability "a bit in the first half changes" is equal to ${}_{\frac{n}{2}}C_1/2^{\frac{n}{2}}$. – wangkaibule Jan 5 '18 at 14:34