Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

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

share|improve this answer

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)?

share|improve this answer

Your Answer


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.