Realize a MAC using a Pseudo-random function?

Question

Given a pseudo-random function and assuming that we do not have any other tools, How can we construct a MAC?

I believe this can be done. Would like to know if there is more than one way of doing this.

Answer 1

I am not sure if $\mathsf{PRF}$ alone can be used to construct; however there is a natural way to construct $\mathsf{MAC}$ using $\mathsf{PRF}$ and $\mathsf{UHF}$. You can see the following papers for more detail:

1. LFSR-based hashing and authentication. In CRYPTO 1994.
2. Bucket hashing and its application to fast message authentication. In CRYPTO 1995.
3. On fast and provably secure message authentication based on universal hashing. In CRYPTO 1996.

I just found a very easy way to construct $\mathsf{MAC}$ from $\mathsf{PRF}$ in the lecture notes of Barak. More concisely, it says that if $\{ f_k \}_{k \in \mathcal{K}}$ is a family of $\mathsf{PRF}$, then the following is a $\mathsf{MAC}$:

$$ \mathsf{SIGN}_k(x) = f_k(x) \qquad \mathsf{VERIFY}_k(x,s)=1 \text{ iff } f_k(x)=s. $$

I think this is pretty neat.

Answer 2

If you have a keyed PRF, where the key is sufficient to turn the function into an independent PRF, you can turn it into a keyed PRP using a Luby Rackoff construct. If you got a keyed PRP, you can use it in CBC-MAC mode.

Answer 3

If you have a PRF (with larger input than output), you can use it as compression function in a Merkle-Damgård structure, yielding a hash function which you can subsequently turn into a MAC with HMAC. Indeed, the security proof of HMAC relies on indistinguishability of the compression function from a PRF.

There are still an awful lot of details, though. And the PRF assumption is quite strong.