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
  • 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, 2014 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, 2014 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, 2014 at 8:14
  • 1
    $\begingroup$ @RickyDemer, care to write it up as an answer? $\endgroup$
    – mikeazo
    May 7, 2014 at 18:11

2 Answers 2

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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