Message Authentication, Revisited

Message Authentication Codes (MACs) are one of the most fundamental primitives in cryptography. Historically, a vast majority of MAC constructions are based on Pseudo-Random Functions (PRFs). In particular, since a PRF with large output domain is also a MAC, most research on symmetric-key authentication concentrated on designing and improving various PRF constructions. This is done either using very fast heuristic constructions, such as block-cipher based PRFs, or using elegant, but slower number-theoretic constructions, such as the Naor-Reingold (NR) PRF.