International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Duel of the Titans: The Romulus and Remus Families of Lightweight AEAD Algorithms

Authors:
Tetsu Iwata , Nagoya University, Nagoya, Japan
Mustafa Khairallah , Nanyang Technological University, Singapore, Singapore
Kazuhiko Minematsu , NEC, Kawasaki, Japan
Thomas Peyrin , Nanyang Technological University, Singapore, Singapore; Temasek Laboratories, Nanyang Technological University (NTU), Singapore, Singapore
Download:
DOI: 10.13154/tosc.v2020.i1.43-120
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8560
Search ePrint
Search Google
Abstract: In this article, we propose two new families of very lightweight and efficient authenticated encryption with associated data (AEAD) modes, Romulus and Remus, that provide security beyond the birthday bound with respect to the block-length n. The former uses a tweakable block cipher (TBC) as internal primitive and can be proven secure in the standard model. The later uses a block cipher (BC) as internal primitive and can be proven secure in the ideal cipher model. Both our modes allow to switch very easily from the nonce-respecting to the nonce-misuse scenario.Previous constructions, such as ΘCB3, are quite computationally efficient, yet needing a large memory for implementation, which makes them unsuitable for platforms where lightweight cryptography should play a key role. Romulus and Remus break this barrier by introducing a new architecture evolved from a BC mode COFB. They achieve the best of what can be possible with TBC – the optimal computational efficiency (rate-1 operation) and the minimum state size of a TBC mode (i.e., (n + t)-bit for n-bit block, t-bit tweak TBC), with almost equivalent provable security as ΘCB3. Actually, our comparisons show that both our designs present superior performances when compared to all other recent lightweight AEAD modes, being BC-based, TBC-based or sponge-based, in the nonce-respecting or nonce-misuse scenario. We eventually describe how to instantiate Romulus and Remus modes using the Skinny lightweight tweakable block cipher proposed at CRYPTO 2016, including the hardware implementation results
Video from TOSC 2020
BibTeX
@article{tosc-2020-30269,
  title={Duel of the Titans: The Romulus and Remus Families of Lightweight AEAD Algorithms},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2020, Issue 1},
  pages={43-120},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8560},
  doi={10.13154/tosc.v2020.i1.43-120},
  author={Tetsu Iwata and Mustafa Khairallah and Kazuhiko Minematsu and Thomas Peyrin},
  year=2020
}