Paper 2012/450

Tweakable Blockciphers with Beyond Birthday-Bound Security

Will Landecker, Thomas Shrimpton, and R. Seth Terashima


Liskov, Rivest and Wagner formalized the tweakable blockcipher (TBC) primitive at CRYPTO'02. The typical recipe for instantiating a TBC is to start with a blockcipher, and then build up a construction that admits a tweak. Almost all such constructions enjoy provable security only to the birthday bound, and the one that does achieve security beyond the birthday bound (due to Minematsu) severely restricts the tweak size and requires per-invocation blockcipher rekeying. 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.

Note: This is a revised full version of a paper that appeared in CRYPTO ’12. Both the original full version (6 Aug. 2012) and the CRYPTO paper contain an error in the proof of Theorem 1. Briefly, the error occurs in the transition from Game 4 to Game 5 when we tacitly assume the former is more likely than an ideal tweakable blockcipher to return certain values (specifically, values in the set S_1 ). We would like to thank Gordon Procter for bringing the error to our attention. Procter also provided a suggested patch to the problem; while we believe the patch is sound, we opted for a solution that simplifies the proof by using a coupling argument to abstract away the details of certain game transitions.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. The conference version of this paper will appear in CRYPTO 2012. This is the full version.
tweakable blockcipherbeyond birthday boundpseudorandom functionmessage authentication codeunforgeability
Contact author(s)
seth @ cs pdx edu
2014-02-20: last of 3 revisions
2012-08-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Will Landecker and Thomas Shrimpton and R.  Seth Terashima},
      title = {Tweakable Blockciphers with Beyond Birthday-Bound Security},
      howpublished = {Cryptology ePrint Archive, Paper 2012/450},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.