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 $\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.

Note: Subsection 3.4 was modified.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in TOSC 2017 ISSUE 2
Keywords
Blockciphertweakable blockcipherefficient authenticated encryptionbeyond-birthday-bound security
Contact author(s)
Naito Yusuke @ ce mitsubishielectric co jp
History
2017-07-01: last of 4 revisions
2017-05-28: received
See all versions
Short URL
https://ia.cr/2017/466
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/466,
      author = {Yusuke Naito},
      title = {Tweakable Blockciphers for Efficient Authenticated Encryptions with Beyond the Birthday-Bound Security},
      howpublished = {Cryptology ePrint Archive, Paper 2017/466},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/466}},
      url = {https://eprint.iacr.org/2017/466}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.