# Is this PRG secure? Different on halves of input

So yes, this is a homework question, but no I have not just copy pasted the question without giving it any thought.

The question goes:

$H$ on input $x$ outputs $G(x)$ except for $x$ when $x_\text{Left} = x_\text{Right}$, then $H$ outputs $0^{2n}$ for $n = |x|$. Is $H$ a secure PRG for all secure PRG $G$? On even length binary inputs.

So I am going with no it is not secure, BUT in a size $n$ input, $1/(2^{n/2})$ of the input, the outcome will be $0^{2n}$ for $n = |x|$. So, as $n$ grows, the amount of input that is distinguishable (where the input is symmetric).

$1/(2^{n/2})$ is a negligible function, so does this fall under negligible, so H is secure?

• This would be a good opportunity to get familiar with Shoup's "sequences of games" methodology. eprint.iacr.org/2004/332 – fkraiem Feb 12 '17 at 5:05

The PRG $H$ is still secure, and your intuition is right: $x_\text{Left} = x_\text{Right}$ happens with a very small probability, so this shouldn't be a problem.
The way to formally prove this would be as follows. Consider a distinguisher $\mathcal{D}$ and the experiment in which a random $x\in\{0,1\}^n$ is chosen and $G(x)$ is given to $\mathcal{D}$, we want to see that the probability that $\mathcal{D}$ outputs 1 in this case is very close to the possibility that $\mathcal{D}$ outputs 1 when we feed it with a truly random string $r\in \{0,1\}^{2n}$. Let $\text{eq}$ denote the event in which $x_\text{Left} = x_\text{Right}$ (where $x$ is the uniform seed of the experiment), then we know that
The first term is negligible as you mentioned, and the second is because of the assumption that $G$ is a PRG, since whenever $\text{eq}$ does not occur, the experiment is the same as the experiment for $G$.