Efficient Beyond Birthday Bound Secure Deterministic Authenticated Encryption with Minimal Stretch
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.
ACISP