7
$\begingroup$

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?

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

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

\begin{multline} \operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1] \\ = \operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}]\operatorname{Pr}[\text{eq}] + \operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}^c]\operatorname{Pr}[\text{eq}^c] \\ = (\operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}] - \operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}^c])\operatorname{Pr}[\text{eq}]\\ + \operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}^c] \end{multline}

So

\begin{multline} |\operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1] - \operatorname{Pr}[\mathcal{D}\left(r\right) = 1]| \\ \leq \operatorname{Pr}[\text{eq}] + |\operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}^c] - \operatorname{Pr}[\mathcal{D}\left(r\right) = 1]| \end{multline}

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

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.