Timeline for Let F be a PRF, how to prove F3 is PRF?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 5, 2018 at 10:12 | comment | added | fgrieu♦ | @Maeher and Yehuda Lindell: perfectly clear, I had overlooked that fact. Thanks. | |
| Nov 5, 2018 at 9:41 | comment | added | Yehuda Lindell | @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. :-)) | |
| Nov 5, 2018 at 9:34 | comment | added | Maeher | @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. | |
| Nov 5, 2018 at 8:16 | comment | added | fgrieu♦ | @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? | |
| Nov 5, 2018 at 6:00 | comment | added | Yehuda Lindell | This is wrong. In such cases, we always consider random keys and so K1=K2 with only negligible probability. | |
| Nov 5, 2018 at 3:06 | history | answered | WDS | CC BY-SA 4.0 |