1
$\begingroup$

Let $\operatorname{F}$ be a $\operatorname{PRF}$, how to prove $\operatorname{F^3_{k_1,k_2}}(x) = \operatorname{F_{k_1}}(x) \oplus \operatorname{F_{k_2}}(x) $ is aslo a $\operatorname{PRF}$?

$\endgroup$
-2
$\begingroup$

This cannot be a PRF in all cases, because in the edge case where K1 = K2, the output of F3 will be 0 for all x.

$\endgroup$
  • 2
    $\begingroup$ This is wrong. In such cases, we always consider random keys and so K1=K2 with only negligible probability. $\endgroup$ – Yehuda Lindell Nov 5 '18 at 6:00
  • $\begingroup$ @Yehuda Lindell: I understand the point you make, and how it invalidates the answer's argument. But: what if $F_k$ is a PRF that ignores all of its input $k$, except its bit size (e.g. SHA-3 without considering initial state of round constants to be $k$, extended to variable-size output determined by the bit width of $k$)? Then $\operatorname{F^3_{k_1\mathbin\|k_2}}(x) = \operatorname{F_{k_1}}(x) \oplus \operatorname{F_{k_2}}(x)$ is always zero (for $k_1$ and $k_2$ of equal size), thus not a PRF. Is the definition of a PRF violated by my hypothetical PRF? $\endgroup$ – fgrieu Nov 5 '18 at 8:16
  • 1
    $\begingroup$ @fgrieu The length of the key is a function of the security parameter. Therefore it's known to the adversary in the PRF definition. Thus in your construction the adversary can simply query a few points and compare the values to the ones it can compute itself. Therefore it's trivially distinguishable from a random function. $\endgroup$ – Maeher Nov 5 '18 at 9:34
  • 1
    $\begingroup$ @fgrieu Yes, your construction is not a PRF since the adversary can run the function itself. (I know that your counterexample can't work since I know easily how to prove that the construction is a PRF. :-)) $\endgroup$ – Yehuda Lindell Nov 5 '18 at 9:41
  • $\begingroup$ @Maeher and Yehuda Lindell: perfectly clear, I had overlooked that fact. Thanks. $\endgroup$ – fgrieu Nov 5 '18 at 10:12

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.