Paper 2020/1145
Improved Security Analysis for Noncebased Enhanced HashthenMask MACs
Wonseok Choi, Byeonghak Lee, Yeongmin Lee, and Jooyoung Lee
Abstract
In this paper, we prove that the noncebased enhanced hashthenmask 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 PRFbased $\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^{ns}$ and $\mu<\max\{2^{\frac{s}{2}},2^{ns}\}$, 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^{ns}\}$. 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)
 Category
 Secretkey cryptography
 Publication info
 A minor revision of an IACR publication in ASIACRYPT 2020
 Keywords
 message authentication codesbeyondbirthdaybound securitymirror theorygraceful degradationtruncation
 Contact author(s)

krwioh @ kaist ac kr
lbh0307 @ kaist ac kr
dudals4780 @ kaist ac kr
hicalf @ kaist ac kr  History
 20200921: received
 Short URL
 https://ia.cr/2020/1145
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1145, author = {Wonseok Choi and Byeonghak Lee and Yeongmin Lee and Jooyoung Lee}, title = {Improved Security Analysis for Noncebased Enhanced HashthenMask 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} }