Existence of MAC implies existence of OWF

Question

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?

Answer 1

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.