New Constructions of MACs from (Tweakable) Block Ciphers

We propose new constructions of Message Authentication Codes (MACs)
from tweakable or conventional block ciphers. Our new schemes are either stateless
and deterministic, nonce-based, or randomized, and provably secure either in the
standard model for tweakable block cipher-based ones, or in the ideal cipher model
for block cipher-based ones. All our constructions are very efficient, requiring only
one call to the underlying (tweakable) block cipher in addition to universally hashing
the message. Moreover, the security bounds we obtain are quite strong: they are
beyond the birthday bound, and nonce-based/randomized variants provide graceful
security degradation in case of misuse, i.e., the security bound degrades linearly with
the maximal number of repetitions of nonces/random values.