# Implementing MAC with PRF family $f$, why do we need $f_k$ to be invertible?

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.

• We don't. Every PRF family is also a secure MAC. Where did you read the claim that we do need efficient invertability? – Maeher Mar 12 '20 at 9:59
• 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? – Luis Casillas Mar 12 '20 at 18:20
• 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 – Mark Mar 12 '20 at 19:19
• Thank you all, I was misinformed, I managed to solve the question and understand the topic. – user574362 Mar 12 '20 at 20:43