[Resource Topic] 2017/837: Tight Security Analysis of EHtM MAC

Welcome to the resource topic for 2017/837

Tight Security Analysis of EHtM MAC

Authors: Avijit Dutta, Ashwin Jha, Mridul Nandi


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.

ePrint: https://eprint.iacr.org/2017/837

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .