4
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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) $\endgroup$ – user991 May 6 '14 at 2:40
  • 1
    $\begingroup$ You should specify what F is (I assume a pseudorandom function) and where k comes from. $\endgroup$ – Maeher May 6 '14 at 7:19
  • $\begingroup$ 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". $\endgroup$ – tylo May 6 '14 at 8:14
  • 1
    $\begingroup$ @RickyDemer, care to write it up as an answer? $\endgroup$ – mikeazo May 7 '14 at 18:11
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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