International Association
for Cryptologic Research

In CRYPTO 1999, J. An and M. Bellare proposed a Merkle-Damg\\r{a}rd iteration based MAC construction called NI-MAC in order to avoid constant re-keying on multiblock messages in NMAC and to ease the security proof. In CRYPTO 2014, Gazi et al. revisited the proof of

NI-MAC in the view of structure graph introduced by Bellare et al. in

CRYPTO 2005 and gave a tight bound of order $\\frac{lq^{2}}{2^{n}}$, which is an improvement over the trivial bound of order $\\frac{l^{2}q^{2}}{2^{n}}$, for $q$ queries, each of length at most $\\ell$ blocks. But this is again restricted to the birthday security. In order to prove the security of NI-MAC, Gazi et al. (CRYPTO 2014) introduced a variant of NI-MAC, called NI2-MAC and analyzed the advantage of NI2 MAC. Then he showed that the same proof technique will be applied to the security analysis of NI-MAC. In this paper, we lift the birthday bound of NI2-MAC construction to beyond birthday $O(q^2l^4/2^{2n})$ by a small change in the existing construction with one extra invocation of a independent keyed function. Finally, we argue how to lift the security of NI-MAC to beyond birthday using the security proof for NI2-MAC.