Cryptology ePrint Archive: Report 2017/837

Tight Security Analysis of EHtM MAC

Avijit Dutta and Ashwin Jha and Mridul Nandi

Abstract: The security of a probabilistic Message Authentication Code (MAC) usually depends on the uniqueness of the random salt which restricts the security to birthday bound of the salt size due to the collision on random salts (e.g XMACR). To overcome the birthday bound limit, the natural approach to use (a) either a larger random salt (e.g $\mathrm{MACRX}_3$ uses $3n$ bits of random salt where $n$ is the input and output size of the underlying non-compressing pseudorandom function or PRF) or (b) a PRF with increased domain size (e.g RWMAC or Randomized WMAC). Enhanced Hash-then-Mask (\textsf{EHtM}), proposed by Minematsu in FSE 2010, is the first probabilistic MAC scheme that provides beyond birthday bound security without increasing the randomness of the salt and the domain size of the non-compressing PRF. The author proved the security of \textsf{EHtM} as long as the number of MAC query is smaller than $2^{2n/3}$ where $n$ is the input size of the underlying non-compressing PRF. In this paper, we provide the exact security bound of \textsf{EHtM} and prove that this construction offers security up to $2^{3n/4}$ MAC queries. The exactness is shown by demonstrating a matching attack.

Category / Keywords: Probabilistic MAC, EHtM, XMACR, Alternating Cycle.

Original Publication (in the same form): IACR-FSE-2018

Date: received 30 Aug 2017, last revised 31 Aug 2017

Contact author: avirocks dutta13 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170831:201656 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]