Proving correctness of pseudorandom generator construction given existing pseudorandom generator Say if I have a given pseudorandom generator G which takes a k-bit input and outputs a 3k-bit number.

How should I show that a specific construction using this pseudorandom generator is valid?

For example, if I want a generator which takes a 2k-bit input and output a 3k-bit number. Is the following scheme valid?

1. split the 2k-bit input into two half
2. passes the two half through the given generator G to get two 3k-bit numbers
3. XOR the two numbers to output the final 3k-bit number.
Call your original ($k$-to-$3k$ bit) PRG $G$ and your construction $G'$.

Let $\mathcal{U}_t$ denote the uniform distribution on $\{0,1\}^t$. Then $G'$ is a PRG as long as the distributions $\mathcal{U}_{3k}$ and $G'(\mathcal{U}_{2k})$ are indistinguishable with effort polynomial in $k$; see this reference.

Distribution $G'(\mathcal{U}_{2k})$ is just $G(\mathcal{U}_k) \oplus G(\mathcal{U}_k)$, where the two occurrences of $\mathcal{U}_k$ in the latter expression are independent. By the PRG property of $G$ applied to the first term, the distribution is indistinguishable from $\mathcal{U}_{3k} \oplus G(\mathcal{U}_k)$.

Since $\mathcal{U}_t \oplus \mathcal{D}$ is distributed identically to $\mathcal{U}_t$, for any independent distribution $\mathcal{D}$, we get the desired result.



I find this question a bit odd though. If all you want is a $2k$-to-$3k$ PRG constructed from a $k$-to-$3k$ PRG, then what about the following simpler construction: given $2k$ bits, throw away the first half and run the second half through the $k$-to-$3k$ PRG?