Paper 2015/1016

One-Key Compression Function Based MAC with Security beyond Birthday Bound

Avijit Dutta, Mridul Nandi, and Goutam Paul

Abstract

Ga{\v z}i et al. [CRYPTO 2014] analyzed the NI-MAC construction proposed by An and Bellare [CRYPTO 1999] and gave a tight birthday-bound of $O(\ell q^{2}/2^{n})$, as an improvement over the previous bound of $O(\ell^{2}q^{2}/2^{n})$. In this paper, we design a simple extension of NI-MAC, called NI$^+$-MAC, and prove that it has security bound beyond birthday (BBB) of order $O(q^2\ell^2 / 2^{2n})$ provided $\ell \leq 2^{n/4}$. Our construction not only lifts the security of NI-MAC beyond birthday, it also reduces the number of keys from 2 (NI uses 2 independent keys) to 1. Before this work, Yasuda had proposed [FSE 2008] a single fixed-keyed compression function based BBB-secure MAC with security bound $O(\ell q^2/2^{2n})$ that uses an extra mask, requires a storage space to store the mask. However, our proposed construction NI$^+$ does not require any extra mask and thereby has reduced the state size compared to Yasuda's proposal [FSE 2008] with providing the same order of security bound for light-weight applications

Note: BBB in title expanded to full form. Some minor typos corrected. Publication info added.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. ACISP 2016
Keywords
Beyond BirthdayMACNIStructure-Graph.
Contact author(s)
avirocks dutta13 @ gmail com
goutam paul @ isical ac in
mridul nandi @ gmail com
History
2016-04-20: last of 5 revisions
2015-10-21: received
See all versions
Short URL
https://ia.cr/2015/1016
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1016,
      author = {Avijit Dutta and Mridul Nandi and Goutam Paul},
      title = {One-Key Compression Function Based MAC with Security beyond Birthday Bound},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1016},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1016}},
      url = {https://eprint.iacr.org/2015/1016}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.