Paper 2017/837

Tight Security Analysis of EHtM MAC

Avijit Dutta, 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.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in FSE 2018
Keywords
Probabilistic MACEHtMXMACRAlternating Cycle.
Contact author(s)
avirocks dutta13 @ gmail com
History
2017-08-31: received
Short URL
https://ia.cr/2017/837
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/837,
      author = {Avijit Dutta and Ashwin Jha and Mridul Nandi},
      title = {Tight Security Analysis of EHtM MAC},
      howpublished = {Cryptology ePrint Archive, Paper 2017/837},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/837}},
      url = {https://eprint.iacr.org/2017/837}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.