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?


1 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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.