International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Improved Security Analysis for Nonce-based Enhanced Hash-then-Mask MACs

Authors:
Wonseok Choi
Byeonghak Lee
Yeongmin Lee
Jooyoung Lee
Download:
DOI: 10.1007/978-3-030-64837-4_23
Search ePrint
Search Google
Abstract: In this paper, we prove that the nonce-based enhanced hash-then-mask MAC (nEHtM) is secure up to 2^{3n/4} MAC queries and 2^n verification queries (ignoring logarithmic factors) as long as the number of faulty queries \mu is below 2^{3n/8}, significantly improving the previous bound by Dutta et al. Even when \mu goes beyond 2^{3n/8}, nEHtM enjoys graceful degradation of security. The second result is to prove the security of PRF-based nEHtM; when nEHtM is based on an n-to-s bit random function for a fixed size s such that 1 <= s <= n, it is proved to be secure up to any number of MAC queries and 2^s verification queries, if (1) s = n and \mu < 2^{n/2} or (2) n/2 < s < 2^{n-s} and \mu < max{2^{s/2}, 2^{n-s}}, or (3) s <= n/2 and \mu < 2^{n/2}. This result leads to the security proof of truncated nEHtM that returns only s bits of the original tag since a truncated permutation can be seen as a pseudorandom function. In particular, when s <= 2n/3, the truncated nEHtM is secure up to 2^{n - s/2} MAC queries and 2^s verification queries as long as \mu < min{2^{n/2}, 2^{n-s}}. For example, when s = n/2 (resp. s = n/4), the truncated nEHtM is secure up to 2^{3n/4} (resp. 2^{7n/8}) MAC queries. So truncation might provide better provable security than the original nEHtM with respect to the number of MAC queries.
Video from ASIACRYPT 2020
BibTeX
@article{asiacrypt-2020-30670,
  title={Improved Security Analysis for Nonce-based Enhanced Hash-then-Mask MACs},
  booktitle={Advances in Cryptology - ASIACRYPT 2020},
  publisher={Springer},
  doi={10.1007/978-3-030-64837-4_23},
  author={Wonseok Choi and Byeonghak Lee and Yeongmin Lee and Jooyoung Lee},
  year=2020
}