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.

  • 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$
    – Maeher
    Mar 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$ Mar 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$
    – Mark
    Mar 12, 2020 at 19:19
  • $\begingroup$ Thank you all, I was misinformed, I managed to solve the question and understand the topic. $\endgroup$
    – user574362
    Mar 12, 2020 at 20:43


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.