Is a secure deterministic MAC always a PRF? Given a secure MAC scheme $ \Pi=(Gen, Mac, Vrfy) $, wheres $ Gen $ produces uniformly distributed keys, and the algorithm $ Mac $ is deterministic, is $ Mac $ necessarily a pseudorandom function?


I think that it is a PRF: since there is no forger A that can somehow obtain information from the given tags, and thus deduce something about how the $Mac$ function is built (i.e. how a tag is created), I conclude that there's no distinguisher D that can distinguish between a tag and a random string emitted by a random function.

Is my intuition right? If not, I'd like to have some intuition as to why a deterministic MAC can't be a PRF. (An example of such a MAC would be great.) If yes, further intuition would be great as well.
Your intuition is not right. The fact that no forger can obtain new valid message/tag pairs doesn't say anything about the "shape" of the MAC. For instance, if $\Pi$ is a secure MAC, then the MAC obtained by appending a bunch of zeros at the end of the tag is secure as well:


  If a forger $\mathcal{A}$ is able to create a new and valid message/tag pair $(m,t)$ for our modified MAC (the one obtained by appending the zeros to a secure MAC), then $(m,t')$ would be a new and valid message/pair for $\Pi$, where $t = t'||0^n$ (you would need to be more precise with the games being played here, but the idea is that any msg/tag pair for one MAC corresponds to one msg/tag pair for the other)


But of course this is not a pseudorandom function.

I think your intuition is that a secure MAC can not reveal anything about the underlying message, but this is not right. The security of a MAC relies on the hardness of generating new messages/tag pairs, not in the difficulty of learning anything about the underlying message. In fact, a MAC can reveal the whole message! can you imagine how?