Given a secure PRG $G :\text{{0,1}}^n \rightarrow \text{{0,1}}^{2n}$, I've constructed the following PRG:
$$
G'(x) =
\begin{cases}
0^{2n} & \text{if x is palindrome;}\\
G(x) & \text{otherwise;}\\
\end{cases}
$$
My intuition is that $G'$ is secure because it's "predictable" only for negligible portion of the inputs, so I tried to write a formal reduction.
I tried showing that given an efficient distinguisher $D'$ for $G'$, I can construct an efficient distinguisher $D$ for $G$. The immediate issue I faced is that $D$ receives as input either a random string $r$ of length $2n$, or $G(s)$ for a random $s$ of length $n$, and In the later case I'm having trouble rearranging $G(s)$ to be "suitable" for $D'$. (which I'm using as a black box)
Is my intuition about $G'$ security correct? If so, what's the way of proving its' security?
-
$\begingroup$ Be careful about your notion of "rearranging $G(s)$ to be suitable for $D'$". Although one clearly sees what you mean by that, strictly speaking it does not make sense because $D'$ is an algorithm, and any input is of course "suitable" for it, in the sense that the algorithm will run and produce an output. $\endgroup$– fkraiemCommented Apr 21, 2017 at 19:14
-
2$\begingroup$ By the way, Shoup's "sequences of games" methodology (or the very similar "code-based games" of Bellare and Rogaway) are more elegant ways to deal with such arguments than raw probabilites. Just Google them, and maybe see also this. $\endgroup$– fkraiemCommented Apr 21, 2017 at 19:16
2 Answers
Indeed, your intuition is perfectly correct and the distinguisher $D$ you're trying to build is basically $D'$ itself. To see that this is the case, simply divide the experiment for $G'$ into two cases: either the chosen input is palindrome or it is not. The first case occurs with negligible probability, so we can focus in the second case, but now it's easy since this case corresponds to the original experiment for $G$.
If you want to be formal, just keep in mind that \begin{multline*} \mathbb{P}\left[D'(G'(x)) = 1\right] = \mathbb{P}\left[D'(G'(x)) = 1|x\text{ is palindrome}\right]\cdot\overbrace{\mathbb{P}\left[x\text{ is palindrome}\right]}^{\delta} \\ + \mathbb{P}\left[D'(G'(x)) = 1|x\text{ is not palindrome}\right]\cdot\underbrace{\mathbb{P}\left[x\text{ is not palindrome}\right]}_{1-\delta} \end{multline*} and $$\mathbb{P}\left[D'(r) = 1\right] = \delta\cdot\mathbb{P}\left[D'(r) = 1\right] + (1-\delta)\cdot\mathbb{P}\left[D'(r) = 1\right].$$ Now, when you take the difference $$\begin{align*} \left|\mathbb{P}\left[D'(G'(x)) = 1\right] - \mathbb{P}\left[D'(r) = 1\right]\right| \end{align*}$$ try to associate terms appropriately and apply some straightforward inequalities to show this is negligible.
A palindrome is a bit string that is equal to itself when reversed, $x=\sigma({x})$ for some permutation of the bits $\sigma$. For every $x\in\lbrace{0,1\rbrace}^n$ sequence we can append $n$ additional bits to create a palindrome by $x||\sigma(x)$. To verify that this process produces a palindrome, note that $\sigma$ is an involution; $x = \sigma(\sigma(x))$ (self inverse) and that it distributes over string concatenation; $\sigma(a||b) = \sigma(b)||\sigma(a)$, so that $\sigma(x||\sigma(x)) = \sigma(\sigma(x))||\sigma(x) = x||\sigma(x)$, as claimed.
Of the $2^n$ possible ways to extend $x$ by $x||y$ with $y\in\lbrace{0,1\rbrace}^n$, only one choice of $y$ will produce a palindrome; $y=\sigma(x)$. This means that the total number of palindromes in $x||z$ with $z\in\lbrace{0,1\rbrace}^n$ is equal to the number of possible choices of $x$ which is $2^n$.
Thus the probability that G is a palindrome is $2^{n}/2^{2n} = 2^{-n}$.
