Cryptology ePrint Archive: Report 2015/1016

Lifting the Security of NI-MAC Beyond Birthday Bound

Avijit Dutta and Goutam Paul

Abstract: 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.

Category / Keywords: secret-key cryptography /

Date: received 20 Oct 2015, last revised 20 Oct 2015

Contact author: avirocks dutta13 at gmail com, goutam paul@isical ac in

Available format(s): PDF | BibTeX Citation

Version: 20151021:054243 (All versions of this report)

Short URL: ia.cr/2015/1016

Discussion forum: Show discussion | Start new discussion