I'm a novice reader of Introduction to Modern Cryptography, where it states:

Let $G$ be a pseudorandom generator with expansion factor $\ell(n) > 2n$.
In each of the following cases, say whether $G′$ is necessarily a pseudorandom generator. If yes, give a proof; if not, show a counterexample.
(a) Define $G'(s) = G(s_1, \ldots, s_{\lfloor n/2\rfloor})$, where $s = s_1, \ldots, s_n$.

I thought that it's not a PRG, by the counterexample that, if $G$ is a PRG such that $G:\{0,1\}^{\lfloor n/2\rfloor} \to \{0,1\}^n$ and if we have $s$ and $s'$ of length $n$ such that $s(1, \ldots,{\lfloor n/2\rfloor}) = s'({1,\ldots,\lfloor n/2\rfloor})$ then $G(s) = G(s')$

What am I missing?

  • $\begingroup$ Hi Eshkod. Please check that we got the formula translation to $\LaTeX$ right, you can of course adjust by hitting edit. $\endgroup$
    – Maarten Bodewes
    Mar 14, 2023 at 7:37
  • 2
    $\begingroup$ HINT: The definition of a PRG does not require that $G$ is collision-free. BTW to which question are you referring? I cannot see this question in my copy of Katz and Lindell. $\endgroup$
    – Daniel S
    Mar 14, 2023 at 8:11
  • 1
    $\begingroup$ @Daniel S: this is exercise 3.6 (a) in the second edition of Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography, correctly transcribed. In the third edition, exercise 3.6 is significantly different. $\endgroup$
    – fgrieu
    Mar 14, 2023 at 9:15
  • 1
    $\begingroup$ In the question, $G$ has input length $n$ and output length $\ell(n)$, and $G'$ mechanically obtained form $G$ has input length $\lfloor n/2\rfloor$ and output length $\ell(n)$. A counterexample must be some $G$ that's a PRG such that $G'$ is not a PRG. Among issues with the PRG proposed as counterexample (beside what's noted in comment by Daniel S): it's noted $G$ but when we look at it's input it's more like $G'$; and it's output has the wrong length. Hint: assume there exists a PRG with output 5 times as wide as it's input. $\endgroup$
    – fgrieu
    Mar 14, 2023 at 10:19
  • $\begingroup$ @DanielS, so if I understand your hint, a test of a distinguisher that runs and outputs 1 for D(G(s)) if it encounters a collision is not a valid test for PRG, right? $\endgroup$
    – Eshkod
    Mar 14, 2023 at 12:55


Your Answer

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

Browse other questions tagged or ask your own question.