Tight Security Analysis of EHtM MAC

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