Paper 2016/395

Efficient Beyond-Birthday-Bound-Secure Deterministic Authenticated Encryption with Minimal Stretch

Christian Forler, Eik List, Stefan Lucks, and Jakob Wenzel


Block-cipher-based authenticated encryption has obtained considerable attention from the ongoing CAESAR competition. While the focus of CAESAR resides primarily on nonce-based authenticated encryption, Deterministic Authenticated Encryption (DAE) is used in domains such as key wrap, where the available message entropy motivates to omit the overhead for nonces. Since the highest possible security is desirable when protecting keys, beyond-birthday-bound (BBB) security is a valuable goal for DAE. In the past, significant efforts had to be invested into designing BBB-secure AE schemes from conventional block ciphers, with the consequences of losing efficiency and sophisticating security proofs. This work proposes Deterministic Counter in Tweak (DCT), a BBB-secure DAE scheme inspired by the Counter-in-Tweak encryption scheme by Peyrin and Seurin. Our design combines a fast $\epsilon$-almost-XOR-universal family of hash functions, for $\epsilon$ close to $2^{-2n}$, with a single call to a $2n$-bit SPRP, and a BBB-secure encryption scheme. First, we describe our construction generically with three independent keys, one for each component. Next, we present an efficient instantiation which (1) requires only a single key, (2) provides software efficiency by encrypting at less than two cycles per byte on current x64 processors, and (3) produces only the minimal $\tau$-bit stretch for $\tau$ bit authenticity. We leave open two minor aspects for future work: our current generic construction is defined for messages of at least $2n-\tau$ bits, and the verification algorithm requires the inverse of the used $2n$-bit SPRP and the encryption scheme.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Major revision. ACISP 2016
deterministic authenticated encryptionsymmetric cryptographycryptographic schemesprovable securitytweakable block cipheruniversal hash function
Contact author(s)
eik list @ uni-weimar de
2016-06-30: last of 3 revisions
2016-04-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Christian Forler and Eik List and Stefan Lucks and Jakob Wenzel},
      title = {Efficient Beyond-Birthday-Bound-Secure Deterministic Authenticated Encryption with Minimal Stretch},
      howpublished = {Cryptology ePrint Archive, Paper 2016/395},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.