Realize a MAC using a Pseudo-random function?

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.

-

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.

-
Just to quibble over minor points, I think NMAC makes more sense than HMAC here (since you're starting with a compression function, rather than a hash function), and I believe the requirement is that the output has to be at least as long as the PRF key (since you'd be chaining through the key input). –  Seth Feb 19 '12 at 10:03

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.

-

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.

-
I think the exact details depend from the used definition of pseudo-random function. If you have one that allows input of any size (like a hash function and the $f_k$ used here), it is a lot easier than if you have one with fixed input size. –  Paŭlo Ebermann Feb 20 '12 at 20:17