# [Resource Topic] 2017/466: Tweakable Blockciphers for Efficient Authenticated Encryptions with Beyond the Birthday-Bound Security

Welcome to the resource topic for 2017/466

Title:
Tweakable Blockciphers for Efficient Authenticated Encryptions with Beyond the Birthday-Bound Security

Authors: Yusuke Naito

Abstract:

Modular design via a tweakable blockcipher (TBC) offers efficient authenticated encryption (AE) schemes (with associated data) that call a blockcipher once for each data block (of associated data or a plaintext). However, the existing efficient blockcipher-based TBCs are secure up to the birthday bound, where the underlying keyed blockcipher is a secure strong pseudorandom permutation. Existing blockcipher-based AE schemes with beyond-birthday-bound (BBB) security are not efficient, that is, a blockcipher is called twice or more for each data block. In this paper, we present a TBC, XKX, that offers efficient blockcipher-based AE schemes with BBB security, by combining with efficient TBC-based AE schemes such as $\Theta$CB and \mathbb{OTR}. XKX is a combination of two TBCs, Minematsu’s TBC and Liskov et al.'s TBC. In the XKX-based AE schemes, a nonce and a counter are taken as tweak; a nonce-dependent blockcipher’s key is generated by using a pseudo-random function F (from Minematsu); a counter is inputted to an almost xor universal hash function, and the hash value is xor-ed with the input and output blocks of a blockcipher with the nonce-dependent key (from Liskov et al.). For each query to the AE scheme, after the nonce-dependent key is generated, it can be reused, thereby a blockcipher is called once for each data block. We prove that the security bounds of the XKX-based AE schemes become roughly \ell^2 q/2^n, where q is the number of queries to the AE scheme, n is the blockcipher size, and \ell is the number of blockcipher calls in one AE evaluation. Regarding the function F, we present two blockcipher-based instantiations, the concatenation of blockcipher calls, F^{(1)}, and the xor of blockcipher calls, F^{(2)}, where F^{(i)} calls a blockcipher i+1 times. By the PRF/PRP switch, the security bounds of the XKX-based AE schemes with F^{(1)} become roughly \ell^2 q/2^n + q^2/2^n, thus if \ell \ll 2^{n/2} and q \ll 2^{n/2}, these achieve BBB security. By the xor construction, the security bounds of the XKX-based AE schemes with F^{(2)} become roughly \ell^2 q/2^n + q/2^n, thus if \ell \ll 2^{n/2}, these achieve BBB security.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.