0
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 5:20

1 Answer 1

Reset to default
1
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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