Paper 2020/1145

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

Wonseok Choi, Byeonghak Lee, Yeongmin Lee, and Jooyoung Lee

Abstract

In this paper, we prove that the nonce-based enhanced hash-then-mask MAC ($\mathsf{nEHtM}$) is secure up to $2^{\frac{3n}{4}}$ MAC queries and $2^n$ verification queries (ignoring logarithmic factors) as long as the number of faulty queries $\mu$ is below $2^\frac{3n}{8}$, significantly improving the previous bound by Dutta et al. Even when $\mu$ goes beyond $2^{\frac{3n}{8}}$, $\mathsf{nEHtM}$ enjoys graceful degradation of security. The second result is to prove the security of PRF-based $\mathsf{nEHtM}$; when $\mathsf{nEHtM}$ is based on an $n$-to-$s$ bit random function for a fixed size $s$ such that $1\leq s\leq 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^{\frac{n}{2}}$ or (2) $\frac{n}{2}<s<2^{n-s}$ and $\mu<\max\{2^{\frac{s}{2}},2^{n-s}\}$, or (3) $s\leq \frac{n}{2}$ and $\mu<2^{\frac{n}{2}}$. This result leads to the security proof of truncated $\mathsf{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\leq\frac{2n}{3}$, the truncated $\mathsf{nEHtM}$ is secure up to $2^{n-\frac{s}{2}}$ MAC queries and $2^s$ verification queries as long as $\mu<\min\{2^{\frac{n}{2}},2^{n-s}\}$. For example, when $s=\frac{n}{2}$ (resp. $s=\frac{n}{4}$), the truncated $\mathsf{nEHtM}$ is secure up to $2^{\frac{3n}{4}}$ (resp. $2^{\frac{7n}{8}}$) MAC queries. So truncation might provide better provable security than the original $\mathsf{nEHtM}$ with respect to the number of MAC queries.

Note: Correct a typo in the Abstract in this page (the submitted file is not changed)

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2020
Keywords
message authentication codesbeyond-birthday-bound securitymirror theorygraceful degradationtruncation
Contact author(s)
krwioh @ kaist ac kr
lbh0307 @ kaist ac kr
dudals4780 @ kaist ac kr
hicalf @ kaist ac kr
History
2020-09-21: received
Short URL
https://ia.cr/2020/1145
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1145,
      author = {Wonseok Choi and Byeonghak Lee and Yeongmin Lee and Jooyoung Lee},
      title = {Improved Security Analysis for Nonce-based Enhanced Hash-then-Mask MACs},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1145},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1145}},
      url = {https://eprint.iacr.org/2020/1145}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.