I'm sorry if this question is too novice. It comes from a practice midterm in a cryptography course which I'm taking, and my confusion here is really that I don't know the "tools" that one uses in practice for this sort of question. The notation (and class) is Katz's.

I've been given a PRG $G(s)$; I'm trying to show explicitly that $s\mathbin\|G(s)$ is not a PRG. Intuitively, I'd expect both components to be random-seeming, so there's nothing obvious that sticks out to me to XOR or manipulate.

  • 1
    $\begingroup$ What's the probability that a uniform random string $s \mathbin\| x$ satisfies $G(s) = x$, assuming the lengths all work out? $\endgroup$ – Squeamish Ossifrage Mar 10 '19 at 5:10
  • $\begingroup$ @SqueamishOssifrage So, my distinguisher $D$ has "access" to the PRG $G$? (I'm sorry, that just wasn't very clear from the start to me.) $\endgroup$ – Chris Mar 10 '19 at 5:14
  • $\begingroup$ Yep! The only thing it doesn't have a priori is the original input to the putative generator $G'\colon s \mapsto s \mathbin\| G(s)$. Of course, $G'$ just happens to cough it up in the output, so, a posteriori $\endgroup$ – Squeamish Ossifrage Mar 10 '19 at 5:18
  • $\begingroup$ In particular, your goal is to write a decision algorithm $A$ such that $A(G'(s)) = A(s \mathbin\| G(s))$ and $A(u)$ have substantially different probability of returning 1, where $u$ and $s$ are uniform random strings of the appropriate lengths. $\endgroup$ – Squeamish Ossifrage Mar 10 '19 at 5:19
  • $\begingroup$ Incidentally, I know that the answer to your question is $\frac{2^n}{2^{2n}}$, since the subset of strings $r \in \{0,1\}^{2n}$ in this format is constrained by $G$ having a range of size $2^n$. $\endgroup$ – Chris Mar 10 '19 at 5:20

This is an attempt to answer my own question based on Squeamish's helpful comments. If terminology is unclear or misleading, please tell me!

Let $D(s) = \mathbb{I}\{s = x||G(x), x \in \{0,1\}^n\}$. Then, if our putative PRG is $G'$, $\Pr[D(G'(s)) = 1] = 1$ - that is, $G'(s)$ is always in the format that $D$ looks for. However, $\Pr[D(r) = 1]$ (where $r$ is uniform from $\{0,1\}^{2n}$) is $\frac{2^n}{2^{2n}}$, to reflect that $s||G(s)$ has a range of only $2^n$ - being completely determined by $s$ - while there are $2^{2n}$ possible values $r$.

Thus $|\Pr[D(G'(s)) = 1] - \Pr[D(r) = 1]| = 1 - \frac{2^n}{2^{2n}}$, a non-negligible function.

| improve this answer | |

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.