Paper 2017/466

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

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 $$CB and $$. 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 $$ (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 $$, where $$ is the number of queries to the AE scheme, $$ is the blockcipher size, and $$ is the number of blockcipher calls in one AE evaluation. Regarding the function $$, we present two blockcipher-based instantiations, the concatenation of blockcipher calls, $$, and the xor of blockcipher calls, $$, where $$ calls a blockcipher $$ times. By the PRF/PRP switch, the security bounds of the XKX-based AE schemes with $$ become roughly $$, thus if $$ and $$, these achieve BBB security. By the xor construction, the security bounds of the XKX-based AE schemes with $$ become roughly $$, thus if $$, these achieve BBB security.

Note: Subsection 3.4 was modified.