# Why: $G'(s) = G(s_1, \ldots, s_{\lfloor{n/2}\rfloor})$, where $s = s_1, \ldots, s_n$ is PRG?

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?

• Hi Eshkod. Please check that we got the formula translation to $\LaTeX$ right, you can of course adjust by hitting edit. Commented Mar 14, 2023 at 7:37
• 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. Commented Mar 14, 2023 at 8:11
• @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.
– fgrieu
Commented Mar 14, 2023 at 9:15
• 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.
– fgrieu
Commented Mar 14, 2023 at 10:19
• @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? Commented Mar 14, 2023 at 12:55