Take the 2-minute tour ×
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.

Is the following function is 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 - $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. generates random strings and $\oplus$ of these will be random.

Correct me if I am wrong.

share|improve this question
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 at 2:40
You should specify what F is (I assume a pseudorandom function) and where k comes from. –  Maeher May 6 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 at 8:14
@RickyDemer, care to write it up as an answer? –  mikeazo May 7 at 18:11

Your Answer


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

Browse other questions tagged or ask your own question.