International Association for Cryptologic Research

International Association
for Cryptologic Research


CCA Security with Short AEAD Tags

Mustafa Khairallah , Seagate Research Group, Department of Electrical and Information Technology, Lund University
DOI: 10.62056/aevua69p1
Search ePrint
Search Google

The size of the authentication tag represents a significant overhead for applications that are limited by bandwidth or memory. Hence, some authenticated encryption designs have a smaller tag than the required privacy level, which was also suggested by the NIST lightweight cryptography standardization project. In the ToSC 2022, two papers have raised questions about the IND-CCA security of AEAD schemes in this situation. These papers show that (a) online AE cannot provide IND-CCA security beyond the tag length, and (b) it is possible to have IND-CCA security beyond the tag length in a restricted Encode-then-Encipher framework. In this paper, we address some of the remaining gaps in this area. Our main result is to show that, for a fixed stretch, Pseudo-Random Injection security implies IND-CCA security as long as the minimum ciphertext size is at least as large as the required IND-CCA security level. We also show that this bound is tight and that any AEAD scheme that allows empty plaintexts with a fixed stretch cannot achieve IND-CCA security beyond the tag length. Next, we look at the weaker notion of MRAE security, and show that two-pass schemes that achieve MRAE security do not achieve IND-CCA security beyond the tag size. This includes SIV and rugged PRPs.

  title={CCA Security with Short AEAD Tags},
  publisher={International Association for Cryptologic Research},
  volume={1, Issue 1},
  author={Mustafa Khairallah},