PRF ⇒ MAC

Fully-black-box reduction · standard model · GGM84 · security loss: ${\mathbf{Adv}}_{\mathsf{MAC},\mathcal{A}}^{\mathrm{uf}\text{-}\mathrm{cma}}(\lambda )\le {\mathbf{Adv}}_{\mathsf{PRF},\mathcal{B}}^{\mathrm{prf}}(\lambda )+1/|\mathcal{R}|$

Statement

For a PRF $\mathsf{PRF}=(\mathsf{KeyGen},\mathsf{Eval})$ with domain $\mathcal{D}$ and range $\mathcal{R}$ of superpolynomial size, $\mathsf{Tag}(k,m):=\mathsf{Eval}(k,m)$ with canonical verification $\mathsf{Vrfy}(k,m,t):=[t=\mathsf{Eval}(k,m)]$ is a UF-CMA-secure MAC with message space $\mathcal{M}=\mathcal{D}$ — GGM84.

Sketch

Verification recomputes the tag, so correctness is perfect. The distinguisher $\mathcal{B}$ runs the forger $\mathcal{A}$, answers each $\mathsf{Tag}$ query with one query to its own oracle, and outputs $1$ iff one further query confirms the forgery. With a truly random function the tag of an unqueried message is uniform in $\mathcal{R}$, so $\mathcal{B}$ outputs $1$ with probability at most $1/|\mathcal{R}|$, and the bound follows.

Notes

• Domain extension, such as CBC-MAC, enlarges the message space beyond $\mathcal{D}$ — standard.