# 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.

• Well, what properties do you want to prove? One problem I see with your proposal is that, say $A$ and $B$ are k-bit inputs. If I put $A|B$ (where $|$ is concatenation) into your proposed system, the output will be the same as if I put $B|A$ in. I.e., $f(A|B)=f(B|A)$. This may or may not be an issue though depending on the properties you want (and the properties of the original generator $G$). Oct 4 '12 at 13:09
• What's the definition of valid? Also, how is G given? As an explicit algorithm as implementable on a Turing Machine? As an explicit combination of ideal primitives/random oracles? Or is it just named and assumed valid?
– fgrieu
Oct 4 '12 at 13:17

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?

• But a distinguisher for G' is trivial when the input is malleable! If the two input halves are equal, the output is all zero. I stand by my opinion the problem is ill-defined for lack of definition of valid and given.
– fgrieu
Oct 5 '12 at 6:03
• The definition of "pseudorandom generator" is very standard (e.g., here). There is no requirement for non-malleability of PRGs, whatever that would mean. In the PRG distinguishing game, input to the PRG is chosen randomly and the output is given to the distinguisher. The case you are worried about (two halves being equal) happens with negligible probability ($2^{-k}$) and hence does not compromise the pseudorandomness of $G'$. Oct 7 '12 at 2:46
• @Mikero: Yes, under a distinguishing game where input is random, G' is secure when G is, for some suitable asymptotic definition of secure, like "with effort polynomial in $k$ for an arbitrary small odd of success"; and your proof is sound. I was unaware this was implied by "pseudorandom generator". Change the answer (preferably clarifying that or linking to a reference, perhaps adding an explicit "with effort polynomial" before "in $k$" to prevent me reading "with effort in 2 to the $k$") and the answer's score will raise by 2.
– fgrieu
Oct 8 '12 at 11:19
• @Mikero: I took the liberty to do what I suggested; feel free to revert.
– fgrieu
Oct 8 '12 at 14:18