International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Highly Secure Nonce-based MACs from the Sum of Tweakable Block Ciphers

Authors:
Wonseok Choi , Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Korea
Akiko Inoue , NEC Corporation, Kawasaki, Japan
Byeonghak Lee , Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Korea
Jooyoung Lee , Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Korea
Eik List , Bauhaus-Universität Weimar, Weimar, Germany
Kazuhiko Minematsu , NEC Corporation, Kawasaki, Japan
Yusuke Naito , Mitsubishi Electric Corporation, Kamakura, Kanagawa, Japan
Download:
DOI: 10.46586/tosc.v2020.i4.39-70
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8747
Search ePrint
Search Google
Abstract: Tweakable block ciphers (TBCs) have proven highly useful to boost the security guarantees of authentication schemes. In 2017, Cogliati et al. proposed two MACs combining TBC and universal hash functions: a nonce-based MAC called NaT and a deterministic MAC called HaT. While both constructions provide high security, their properties are complementary: NaT is almost fully secure when nonces are respected (i.e., n-bit security, where n is the block size of the TBC, and no security degradation in terms of the number of MAC queries when nonces are unique), while its security degrades gracefully to the birthday bound (n/2 bits) when nonces are misused. HaT has n-bit security and can be used naturally as a nonce-based MAC when a message contains a nonce. However, it does not have full security even if nonces are unique.This work proposes two highly secure and efficient MACs to fill the gap: NaT2 and eHaT. Both provide (almost) full security if nonces are unique and more than n/2-bit security when nonces can repeat. Based on NaT and HaT, we aim at achieving these properties in a modular approach. Our first proposal, Nonce-as-Tweak2 (NaT2), is the sum of two NaT instances. Our second proposal, enhanced Hash-as-Tweak (eHaT), extends HaT by adding the output of an additional nonce-depending call to the TBC and prepending nonce to the message. Despite the conceptual simplicity, the security proofs are involved. For NaT2 in particular, we rely on the recent proof framework for Double-block Hash-then-Sum by Kim et al. from Eurocrypt 2020.
Video from TOSC 2020
BibTeX
@article{tosc-2020-30776,
  title={Highly Secure Nonce-based MACs from the Sum of Tweakable Block Ciphers},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2020, Issue 4},
  pages={39-70},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8747},
  doi={10.46586/tosc.v2020.i4.39-70},
  author={Wonseok Choi and Akiko Inoue and Byeonghak Lee and Jooyoung Lee and Eik List and Kazuhiko Minematsu and Yusuke Naito},
  year=2020
}