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

Eshkod

3/13/24, 9:52 PM

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?

0 + 6

pseudo-random-generator

Maarten Bodewes

3/14/24, 7:37 AM

Hi Eshkod. Please check that we got the formula translation to $\LaTeX$ right, you can of course adjust by hitting [edit].

Daniel S

3/14/24, 8:11 AM

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.

fgrieu

3/14/24, 9:15 AM

@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

3/14/24, 10:19 AM

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](https://crypto.stackexchange.com/posts/comments/226189)): 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.

Eshkod

3/14/24, 12:55 PM

@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?

fgrieu

3/14/24, 1:36 PM

The distinguisher $D$ of definition 3.14 in the K&L reference has input _one_ bitstring of size $\ell(n)$, and must output $0$ or $1$ based on that only. It thus can not directly detect collisions among the outputs of $G(s)$.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.