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}$?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
-
2$\begingroup$ This is wrong. In such cases, we always consider random keys and so K1=K2 with only negligible probability. $\endgroup$ Commented Nov 5, 2018 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 ♦Commented Nov 5, 2018 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$– MaeherCommented Nov 5, 2018 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$ Commented Nov 5, 2018 at 9:41
-
$\begingroup$ @Maeher and Yehuda Lindell: perfectly clear, I had overlooked that fact. Thanks. $\endgroup$– fgrieu ♦Commented Nov 5, 2018 at 10:12