# Existence of MAC implies existence of OWF

I'm having trouble understanding how the existence of a MAC implies the existence of an OWF.

If the MAC protocol is $$(\operatorname{Gen}, \operatorname{MAC}, \operatorname{Ver})$$ such that for any adversary $$\mathcal{A}$$,

$$\begin{gather*} \underset{k \sim \operatorname{Gen}(1^n)}\Pr[\operatorname{Ver}(k, \operatorname{MAC}(k, m)) = m] = 1, \qquad\text{and} \\ \underset{k \sim \operatorname{Gen}(1^n)}\Pr[\mathcal{A}(1^n) = (m,t) \mathrel{\text{such that}} \operatorname{MAC}(k, m) = t] < \text{negligible}. \end{gather*}$$

I am imagining the OWF I would construct to look something like $$f(x) = \operatorname{MAC}(x, 0)$$. If an adversary can invert $$f$$, then given the 'tag' $$t$$ of the zero string they are likely to be able to find some key $$k$$ such that $$\operatorname{MAC}(k, 0) = t$$. They could then break the security property of the MAC by using $$k$$ to forge new messages.

The problem I am running into is: just because inverting $$f$$ gives some key $$k$$ where $$\operatorname{MAC}(k,0) = t$$, it isn't necessarily the same with the challenger used, and may just happen to have the same tag at 0. How can I get around this?

It is not hard to construct a secure MAC where $$f(k) = \textsf{MAC}(k,0)$$ is not one-way. Take any secure $$\textsf{MAC}$$ and define a new one as
$$\textsf{MAC}^*\Bigl( (k_1,k_2), m \Bigr) = \textsf{MAC}(k_1,m) \oplus k_2.$$
It should be relatively clear that $$\textsf{MAC}^*$$ is also a secure MAC. Now given arbitrary $$m$$ and $$t$$, it is easy to find a key under which $$\textsf{MAC}^*((k_1,k_2,m)=t$$. Just choose arbitrary $$k_1$$ and then solve for $$k_2 = t \oplus \textsf{MAC}(k_1,m)$$. This leads to a natural way to invert the $$f$$ function you propose.
Another way to look at things: The function $$f(k) = \textsf{MAC}(k,0)$$ can only rely on the fact that the MAC is secure against an attacker who sees just one output. But there are information-theoretic MACs with this property, and you can't expect them to imply a OWF.
To get around this, you should use $$f(k) =\textsf{MAC}(k,0) \| \textsf{MAC}(k,1) \| \cdots \| \textsf{MAC}(k,\ell)$$ as your OWF candidate, where $$\ell$$ depends on the key size of this MAC. But even then the argument of one-wayness is not trivial.