Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 2 down vote favorite

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.
share|improve this question
3  
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$). – mikeazo♦ Oct 4 '12 at 13:09
2  
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

1 Answer

up vote 4 down vote

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?

share|improve this answer
2  
+1 for the last paragraph. $\:$ – Ricky Demer Oct 5 '12 at 4:37
1  
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
2  
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'$. – Mikero 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
1  
@Mikero: I took the liberty to do what I suggested; feel free to revert. – fgrieu Oct 8 '12 at 14:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.