Paper 2019/600

ZOCB and ZOTR: Tweakable Blockcipher Modes for Authenticated Encryption with Full Absorption

Zhenzhen Bao, Jian Guo, Tetsu Iwata, and Kazuhiko Minematsu

Abstract

We define ZOCB and ZOTR for nonce-based authenticated encryption with associated data, and analyze their provable security. These schemes use a tweakable blockcipher (TBC) as the underlying primitive, and fully utilize its input to process a plaintext and associated data (AD). This property is commonly referred to as full absorption, and this has been explored for schemes based on a permutation or a pseudorandom function (PRF). Our schemes improve the efficiency of TBC-based counterparts of OCB and OTR called $\Theta$CB3 (Krovetz and Rogaway, FSE 2011) and $\mathbb{OTR}$ (Minematsu, EUROCRYPT 2014). Specifically, $\Theta$CB3 and $\mathbb{OTR}$ have an independent part to process AD, and our schemes integrate this process into the encryption part of a plaintext by using the tweak input of the TBC. Up to a certain length of AD, ZOCB and ZOTR completely eliminate the independent process for it. Even for longer AD, our schemes process it efficiently by fully using the tweak input of the TBC. For this purpose, based on previous tweak extension schemes for TBCs, we introduce a scheme called $\mathsf{XTX}^{\ast}$. To our knowledge, ZOCB and ZOTR are the first efficiency improvement of $\Theta$CB3 and $\mathbb{OTR}$ in terms of the number of TBC calls. Compared to Sponge-based and PRF-based schemes, ZOCB and ZOTR allow fully parallel computation of the underlying primitive, and have a unique design feature that an authentication tag is independent of a part of AD. We present experimental results illustrating the practical efficiency gain and clarifying the efficiency cost for it with a concrete instantiation. The results show that for long input data, our schemes have gains, while we have efficiency loss for short input data.