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

-

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