Let $G:(0,1)^n \rightarrow (0,1)^{n+1}$ be a secure PRG.
Define $G'(s):=s_1 ||G(s)_{2,...,n+1} $.
($||$ is concatenation, and the subscript $ _{2,...,n+1}$ means the last $n$ bits of $G$)
I claim that $G'$ is a secure PRG, and my intuition is that if a distinguisher, say $D'$, could distinguish its output on a random seed from a truly random string of length $n+1$, I could break $G$. My reduction is:

1) Choose $b \in(0,1)$ randomly.
2) Return whatever $D'(b||x_{2,...,n+1})$ returns.

Clearly, if $x=r$ is truly random, then $b||x_{1,...,n+1}=r'$ is truly random and:
The other case is where I have problem.

I've divided the probability into two events:
$Pr[D(G(s))=1|b=s_1]\cdot Pr[b=s_1] + Pr[D(G(s))=1|b\neq s_1]\cdot Pr[b\neq s_1]=$
${1 \over 2}(Pr[D(G(s))=1|b=s_1] + Pr[D(G(s))=1|b\neq s_1])=$
${1 \over 2}(Pr[D'(G'(s))=1] + Pr[D(G(s))=1|b\neq s_1])$
Where the final transition is true because when $b=s_1$, we have exactly the definition of $G'$.
However, I don't know how to handle the later addend. I noticed that when $b \neq s_1$, we give $D'$ an input of the form $G'(s) \oplus 10^n $.

1) Is my intuition correct?
2) If so, is my reduction/proof correct? I feel like I'm missing something obvious.

  • $\begingroup$ Suppose input $s = 0^n$ is submitted and $\mathcal{D}$ observes a response of $1 || \{0, 1\}^n$, what can $\mathcal{D}$ immediately infer with $Pr = 1$? $\endgroup$ – puzzlepalace May 9 '17 at 0:48
  • $\begingroup$ @puzzlepalace Nothing because D does not know s. $\endgroup$ – fkraiem May 9 '17 at 11:49
  • $\begingroup$ Remember that you don't need to compute $\mathrm{Pr}[D(G(s)) = 1]$ exactly, only to show that it it sufficiently far from $\mathrm{Pr}[D(r) = 1]$. $\endgroup$ – fkraiem May 9 '17 at 12:22

Your Answer

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

Browse other questions tagged or ask your own question.