As per the title, say we have $\text{MAC}(k,m) = (m,f_k(m))$ where $f$ is a PRF family and every function $f_k$ is PRP, where $f_k(m)$ and $f_k^{-1}(m)$ are efficiently computable. I proved that this scheme is secure, but I do not understand why do we need $f_k^{-1}(m)$ to be efficiently computable, my first thought was to use it to validate the tag by running the inverse on the tag and getting $m$ back, but since we also send $m$ with the tag, computing $f_k$ on $m$ could easily be done to verify the message, any hint would be appreciated.
4
-
3$\begingroup$ We don't. Every PRF family is also a secure MAC. Where did you read the claim that we do need efficient invertability? $\endgroup$– MaeherMar 12, 2020 at 9:59
-
$\begingroup$ I think you are likely misinterpreting something. A non-invertible PRF qualifies as a MAC. Possibly the point of the assumption in the exercise is to demonstrate that a PRP also does? $\endgroup$– Luis CasillasMar 12, 2020 at 18:20
-
$\begingroup$ Note that we don't even need the notion of a PRF to build a MAC. An "Unpredictable Function" suffices, which is a weaker notion (in the sense that every PRF is a UF, but the reverse is not true). See for example this question. Another point not mentioned here is that the output distribution of a UF can depend on the particular key chosen (so $f_k$ and $f_{k+1}$ can have computationally distinguishable output distributions), provided their outputs are still "hard to guess". This is false for PRFs $\endgroup$– MarkMar 12, 2020 at 19:19
-
$\begingroup$ Thank you all, I was misinformed, I managed to solve the question and understand the topic. $\endgroup$– user574362Mar 12, 2020 at 20:43
Add a comment
|