Paper 2022/331

Parallelizable Authenticated Encryption with Small State Size

Akiko Inoue and Kazuhiko Minematsu


Authenticated encryption (AE) is a symmetric-key encryption function that provides confidentiality and authenticity of a message. One of the evaluation criteria for AE is state size, which is memory size needed for encryption. State size is especially important when cryptosystem is implemented in constrained devices, while trivial reduction by using a small primitive is not generally acceptable as it leads to a degraded security. In these days, the state size of AE has been very actively studied and a number of small-state AE schemes have been proposed, but they are inherently serial. It would be a natural question if we come up with a parallelizable AE with a smaller state size than the state-of-the-art. In this paper, we study the seminal OCB mode for parallelizable AE and propose a method to reduce its state size without losing the bit security of it. More precisely, while (the most small-state variant of) OCB has $3n$-bit state, by carefully treating the checksum that is halved, we can achieve $2.5n$-bit state, while keeping the $n/2$-bit security as original. We also propose an inverse-free variant of it based on OTR. While the original OTR has $4n$-bit state, ours has $3.5n$-bit state. To our knowledge these numbers are the smallest ones achieved by the blockcipher modes for parallel AE and inverse-free parallel AE.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Selected Areas in Cryptography (SAC) 2019
Authenticated encryptionState sizeOCBOTRand Phash
Contact author(s)
a_inoue @ nec com
2022-03-14: received
Short URL
Creative Commons Attribution


      author = {Akiko Inoue and Kazuhiko Minematsu},
      title = {Parallelizable Authenticated Encryption with Small State Size},
      howpublished = {Cryptology ePrint Archive, Paper 2022/331},
      year = {2022},
      doi = {10.1007/978-3-030-38471-5_25},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.