# Is $G$ a secure PRG?

Is the following function a secure PRG?

Given $F$ is a secure PRG and $k$ is choosen random from key space $K$.

$$G(x) = F(k,x) \oplus F(k,x \oplus 1^s)$$

My solution is $x \oplus 1^s = x'$ so $G(x)$ becomes $f \oplus f'$ with $f = F(k,x)$ and $f' = F(k,x')$. Clearly $f$ and $f'$ are PRG, i.e. generate random strings; and $\oplus$ of these will be random.

Correct me if I am wrong.

-
G(x xor 1^s) = F(k,x xor 1^s) xor F(k,x xor 1^s xor 1^s) = F(k,x xor 1^s) xor F(k,x xor 0^s) = F(k,x xor 1^s) xor F(k,x) = F(k,x) xor F(k,x xor 1^s) = G(x) – Ricky Demer May 6 '14 at 2:40
You should specify what F is (I assume a pseudorandom function) and where k comes from. – Maeher May 6 '14 at 7:19
Ricky is right, but he forgot to say what it meant: G is not a secure PRG. And yeah, using $F$ without specification is bad. And toughts like this are not always as clear. Your only hint was "clearly $f$ and $f'$ are PRG". – tylo May 6 '14 at 8:14
@RickyDemer, care to write it up as an answer? – mikeazo May 7 '14 at 18:11

To give this question its deserved answer, I’ll repeat what Ricky Demer noted in his comment:

$$G(x \oplus 1^s) = F(k,x \oplus 1^s) \oplus F(k,x \oplus 1^s \oplus 1^s) \\ \downarrow \\ F(k,x \oplus 1^s) \oplus F(k,x \oplus 1^s \oplus 1^s) = F(k,x \oplus 1^s) \oplus F(k,x \oplus 0^s) \\ \downarrow \\ F(k,x \oplus 1^s) \oplus F(k,x \oplus 0^s) = F(k,x \oplus 1^s) \oplus F(k,x) \\ \downarrow \\ F(k,x \oplus 1^s) \oplus F(k,x) = F(k,x) \oplus F(k,x \oplus 1^s) \\ \downarrow \\ F(k,x) \oplus F(k,x \oplus 1^s) = G(x)$$

As tylo commented: This shows G is not a secure PRG.

-

If, as can be reasonably inferred from the question, a fresh random $k$ is chosen on each invocation of $G$, then $G$ is not a pseudorandom generator because it is not deterministic. (A pseudorandom generator by definition is a deterministic algorithm.)

If $k$ is fixed, then more information would be needed. For example, is $k$ always the same, or is a different $k$ used depending on the length of $x$ (i.e., is $G$ actually a family of algorithms)?

-