This paper gives the first TBC construction that simultaneously allows for arbitrarily “wide” tweaks, does not rekey, and delivers provable security beyond the birthday bound. Our construction is built from a blockcipher and an $\eAXU$ hash function.
As an application of the TBC primitive, LRW suggest the TBC-MAC construction (similar to CBC-MAC but chaining through the tweak), but leave open the question of its security. We close this question, both for TBC-MAC as a PRF and a MAC. Along the way, we find a nonce-based variant of TBC-MAC that has a tight reduction to the security of the underlying TBC, and also displays graceful security degradation when nonces are misused. This result is interesting on its own, but it also serves as an application of our new TBC construction, ultimately giving a variable input-length PRF with beyond birthday-bound security.Category / Keywords: secret-key cryptography / tweakable blockcipher, beyond birthday bound, pseudorandom function, message authentication code, unforgeability Publication Info: The conference version of this paper will appear in CRYPTO 2012. This is the full version. Date: received 6 Aug 2012, last revised 8 Aug 2012 Contact author: seth at cs pdx edu Available formats: PDF | BibTeX Citation Version: 20120808:065419 (All versions of this report) Discussion forum: Show discussion | Start new discussion