Construction:MAC from PRF

From CRYPTUTOR

A message authentication code (MAC) for fixed-length messages can be constructed from any pseudorandom function family.

Construction

Let $F:\{0,1\}^k \times \{0,1\}^{m(k)} \to \{0,1\}^{n(k)}$ be a pseudorandom function. Then the following algorithms define a MAC on $m (k)$ -bit messages, with security parameter $k$ :

KeyGen: pick a random $s \gets \{0,1\}^k$
$\mathsf{MAC}_s(x) = F_s(x)$
$\mathsf{Ver}_s(x,\tau) = \begin{cases} 1 & \mbox{ if } \tau = F_s(x) \\ 0 & \mbox{ otherwise}\end{cases}$

[edit]

Security proof

Consider the MAC security experiment against an adversary. The experiment can be implemented by querying an oracle who (secretly) chooses $s$ and answers queries to the $F_s(\cdot)$ function. Now consider replacing that oracle with a random oracle $R(\cdot)$ of the appropriate input/output lengths. By the security property of the PRF, the outcome of the experiment does not change by more than a negligible amount when making this change. In the modified experiment, the adversary succeeds if he can output a pair $(x,τ)$ such that $τ = R (x)$ , and $R$ has never been queried on input $x$ . But since $R$ is a random oracle, the value of $R (x)$ is uniformly distributed over $n (k)$ -bit strings. The probability that the adversary has given the correct value $τ$ is $2 - n (k)$ , which is negligible.