Paper 2015/738

Authenticated Encryption with Small Stretch (or, How to Accelerate AERO)

Kazuhiko Minematsu


Standard form of authenticated encryption (AE) requires the ciphertext to be expanded by the nonce and the authentication tag. These expansions can be problematic when messages are relatively short and communication cost is high. To overcome the problem we propose a new form of AE scheme, MiniAE, which expands the ciphertext only by the single variable integrating nonce and tag. An important feature of MiniAE is that it requires the receiver to be stateful not only for detecting replays but also for detecting forgery of any type. McGrew and Foley already proposed a scheme having this feature, called AERO, however, there is no formal security guarantee based on the provable security framework. We provide a provable security analysis for MiniAE, and show several provably-secure schemes using standard symmetric crypto primitives. This covers a generalization of AERO, hence our results imply a provable security of AERO. Moreover, one of our schemes has a similar structure as OCB mode of operation and enables rate-1 operation, i.e. only one blockcipher call to process one input block. This implies that the computation cost of MiniAE can be as small as encryption-only schemes.

Note: This is a full version of a paper published at ACISP 2016.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. MAJOR revision.ACISP 2016
Authenticated EncryptionStateful DecryptionProvable SecurityAEROOCB
Contact author(s)
k-minematsu @ ah jp nec com
2016-07-19: revised
2015-07-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kazuhiko Minematsu},
      title = {Authenticated Encryption with Small Stretch (or, How to Accelerate AERO)},
      howpublished = {Cryptology ePrint Archive, Paper 2015/738},
      year = {2015},
      doi = {10.1007/978-3-319-40367-0},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.