Communications in Cryptology IACR CiC

CCA Security with Short AEAD Tags


Mustafa Khairallah
Mustafa Khairallah ORCID
Seagate Research Group, Singapore, Singapore
Department of Electrical and Information Technology, Lund University, Lund, Sweden
mustafa dot khairallah dot 1608 at eit dot lth dot se


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.


Farzaneh Abed, Christian Forler, Eik List, Stefan Lucks, and Jakob Wenzel. RIV for robust authenticated encryption. In Fast Software Encryption: 23rd International Conference, FSE 2016, 23–42. Springer, 2016.
Mihir Bellare and Chanathip Namprempre. Authenticated encryption: relations among notions and analysis of the generic composition paradigm. In Tatsuaki Okamoto, editor, Advances in Cryptology — ASIACRYPT 2000, 531–545. Springer Berlin Heidelberg, 2000.
Colin Chaigneau and Henri Gilbert. Is AEZ v4. 1 sufficiently resilient against key-recovery attacks? IACR Transactions on Symmetric Cryptology, 1:654–682, 2016.
Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, and Mridul Nandi. Blockcipher-based Authenticated Encryption: How Small Can We Go? Journal of Cryptology, 33(3):703–741, 2020.
Jean Paul Degabriele and Vukašin Karadžić. Overloading the nonce: rugged PRPs, nonce-set AEAD, and order-resilient channels. In Advances in Cryptology–CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part IV, 264–295. Springer, 2022.
Akinori Hosoyamada, Akiko Inoue, Ryoma Ito, Tetsu Iwata, Kazuhiko Mimematsu, Ferdinand Sibleyras, and Yosuke Todo. Cryptanalysis of Rocca and Feasibility of Its Security Claim. IACR Transactions on Symmetric Cryptology, 2022(3):123–151, Sep. 2022.
Viet Tung Hoang, Ted Krovetz, and Phillip Rogaway. Robust Authenticated-Encryption AEZ and the Problem That It Solves. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015, 15–44. Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.
Tetsu Iwata, Mustafa Khairallah, Kazuhiko Minematsu, and Thomas Peyrin. Duel of the Titans: the Romulus and Remus Families of Lightweight AEAD Algorithms. IACR Transactions on Symmetric Cryptology, pages 43–120, 2020.
Mustafa Khairallah. Security of COFB against chosen ciphertext attacks. IACR Transactions on Symmetric Cryptology, pages 138–157, 2022.
National Institute of Standardization and Technology. Lightweight cryptography. 2019.
Thomas Peyrin and Yannick Seurin. Counter-in-Tweak: Authenticated Encryption Modes for Tweakable Block Ciphers. In Advances in Cryptology–CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I, 33–63. Springer, 2016.
Phillip Rogaway. Authenticated-Encryption with Associated Data. In Proceedings of the 9th ACM Conference on Computer and Communications Security, 98–107. 2002.
Phillip Rogaway and Thomas Shrimpton. A Provable-Security Treatment of the Key-Wrap Problem. In Serge Vaudenay, editor, Advances in Cryptology - EUROCRYPT 2006, 373–390. Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
Kosei Sakamoto, Fukang Liu, Yuto Nakano, Shinsaku Kiyomoto, and Takanori Isobe. Rocca: an efficient AES-based encryption scheme for beyond 5G. IACR Transactions on Symmetric Cryptology, pages 1–30, 2021.

PDFPDF Open access

Submitted: 2024-01-07
Accepted: 2024-03-05
Published: 2024-04-09
How to cite

Mustafa Khairallah, "CCA Security with Short AEAD Tags," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/aevua69p1.


Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.