Cryptology ePrint Archive: Report 2015/738

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

Kazuhiko Minematsu

Abstract: 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.

Category / Keywords: secret-key cryptography / Authenticated Encryption, Stateful Decryption, Provable Security, AERO, OCB

Original Publication (with major differences): ACISP 2016

Date: received 23 Jul 2015, last revised 19 Jul 2016

Contact author: k-minematsu at ah jp nec com

Available format(s): PDF | BibTeX Citation

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

Version: 20160719:094428 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]