**Revisiting Sum of CBC-MACs and Extending NI2-MAC to Achieve Beyond-Birthday Security**

*Avijit Dutta and Goutam Paul*

**Abstract: **In CT-RSA 2010, Kan Yasuda has shown that the sum of two independent Encrypted CBC (ECBC) MACs is a secure PRF with security beyond birthday bound. It was mentioned in the abstract of the paper that ``no proof of security above the birthday bound $(2^{n/2})$ has been known for the sum of CBC MACs" (where $n$ is the tag size in bits). Kan Yasuda's paper did not consider the sum of actual CBC outputs and hence the PRF-security of the same has been left open. In this paper, we solve this problem by proving the beyond birthday security of sum of two CBC MACs. As a tool to prove this result, we develope a generalization of the result of S. Lucks from EUROCRYPT 2000 that the sum of two secure PRPs is a secure PRF. We extend this to the case when the domain and the range of the permutations may have some restrictions. Finally, we also lift the birthday bound of NI2 MAC construction (the bound was proven in CRYPTO 2014 by Gazi et al.) to beyond birthday by a small change in the existing construction.

**Category / Keywords: **Beyond Birthday, CBC, ECBC, MAC, NI, NI2, Sum of PRP

**Date: **received 11 Sep 2015, last revised 13 Sep 2015, withdrawn 14 Sep 2015

**Contact author: **goutam paul at isical ac in

**Available format(s): **(-- withdrawn --)

**Note: **A few typos corrected.

**Version: **20150914:125710 (All versions of this report)

**Short URL: **ia.cr/2015/883

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]