Is a PRG concatenation using the same input still a PRG?

Question

Suppose we have a secure PRG $G: \{0,1\}^s→ \{0,1\}^n$ and we define a $G'(k)$ as:

$$ G'(k) = G(k) \| G(k) $$

So if $G(k)=\mathbf{i}$, $G'(k) = \mathbf{i} \| \mathbf{i}$

Is $G'$ still a secure PRG?

Based on my own understanding it should be, because the statistical distinguishers will produce the same analogy of zeros and ones, therefore $G'$ should be a secure PRG too.

Is there any other principle about PRGs that $G'$ does not satisfy?

Answer 1

Refering to THIS post

If we call $U_k$ the random variable uniformly distributed over bit strings of length $k$, then a function $g: \{0,1\}^k \to \{0,1\}^m$ is called pseudo-random generator if no feasible(poly-time if you want) algorithm can distinguish $g(U_k)$ and $U_m$ with non-negligible probability.

More formally let $U'_m = g(U_k)$ then the distinguishing advantage of any distinguisher efficient $D$ that we denote as $\Delta^D(U'_m, U_m) = \Pr^{DU_m}[Z = 1] - \Pr^{DU'_m}[Z = 1]$ is negligible.

Here $Z$ is the output of the distinguisher, and negligible is any suitable notion of "really small"; same for efficient.

Now my ability to distinguish between $U_k$ from your PRNG $g: \{0,1\}^k \to \{0,1\}^m \mathbin\| \{0,1\}^m$ is obviously more than negligible. Because any OUTPUT from your generator has symmetry and if I see this symmetry the generator being used is most probably your generator.

Answer 2

Note that for $G : \{0,1\}^s \to \{0,1\}^{n}$ to be a PRG, $n$ must be some polynomial of $s$, so let's rewrite this as $G : \{0,1\}^s \to \{0,1\}^{\ell(s)}$, where $\ell(s)$ is a polynomial.

To disprove the proposition that your $G' : \{0,1\}^s \to \{0,1\}^{2\cdot\ell(s)}$ is a PRG, it suffices to exhibit a probabilistic polynomial time algorithm (over $s$) that, for random $k$, distinguishes $G'(k)$ from a random bitstring drawn from $\{0,1\}^{2\cdot\ell(s)}$ with non-negligible probability. Given a string $x \in \{0,1\}^{2\cdot\ell(s)}$, here's one such algorithm, which runs in time proportional to $2\cdot\ell(s)$:

1. Split $x$ in length-$n$ halves $x_1$, $x_2$ such that $x_1 \| x_2 = x$;
2. If $x_1 = x_2$, then output True; otherwise, output False.

If $x$ was produced by $G'$, then this algorithm is guaranteed to output True. If $x$ is random, the probability that it outputs True is $2^{-\ell(s)}$. The distinguishing advantage is therefore

$$ 1 - 2^{-\ell(s)} $$

which is not a negligible function of $s$. Therefore $G'$ is not a PRG.

---

In simpler English, the statistical test that checks whether the first half of the input is identical to the second half always succeeds on the output of $G'$.

Answer 3

This is in complement to the other answers. We can look at a concrete example with $G: \{0, 1\} \to \{0, 1\}^2 = \{00, 01, 10, 11\}$ and $G(k) = k|k$

A natural game to play is to just try to guess the output of a PRG and see how well we can do. So Let $U_2$ an uniform random generator, so it outputs a 2-bits strings with probability $\frac{1}{4}$. It is clear that no matter the strategy that an adversary $A$ chooses, $A$ only guess correctly with probability $\frac{1}{4}$ when interacting with $U_2$.

Now when interacting with $G$, $A$ can be a bit smarter and only chooses guesses in $\{00, 11\}$. So here $A$ guesses correctly with probability $\frac{1}{2}$.

In other words $A$ has 2 times more chance of guessing the output of $G$ that it would guess the output of $U_2$. This does not sound too good, even if we are building a pseudo random generator. We can generalize this reasoning to any bit length as was done in @Luis Casillas's answer.

Another example, if $G$ was used to generate pads for encryption like in additive stream ciphers, i.e we use $G$ to generate $k$ and encrypt the message $m$ as $c = m \oplus k$.

Then if $m = header|secret$ and somehow(maybe not really realistic) the adversary knows $header$, the $secret$ is no longer secret!