Cryptology ePrint Archive: Report 2015/958

Building Single-Key Beyond Birthday Bound Message Authentication Code

Nilanjan Datta and Avijit Dutta and Mridul Nandi and Goutam Paul and Liting Zhang

Abstract: MACs (Message Authentication Codes) are widely adopted in communication systems to ensure data integrity and data origin authentication, e.g. CBC-MACs in the ISO standard 9797-1. However, all the current designs based on block cipher either suffer from birthday attacks or require long key sizes. In this paper, we focus on designing {\em single keyed block cipher based MAC achieving beyond-birthday-bound (BBB) security (in terms of number of queries) in the standard model}. Here, we develop several tools on sampling distributions which would be quite useful in the analysis of mode of operations. In this paper, we also show that the sum of two dependent pseudorandom permutation with some loss of randomness is still PRF with BBB security. Then, we demonstrate a generic composition (including the single keyed) achieving BBB security provided that the underlying internal construction satisfies some variants of cover-free (we call them {\em extended cover-free} and {\em pseudo-cover-free}) and block-wise universal properties. By applying this result, we finally provide two concrete single keyed constructions which achieve BBB security. These two constructions, called \tx{1kf9} and \tx{1k\_PMAC+}, are basically simple one key variants of \tx{3kf9} and \tx{PMAC\_Plus} respectively. Thus, we solve a long-standing open problem in designing single-keyed BBB-secure MAC.

Category / Keywords: \tx{1kf9}, \tx{1k\_PMAC+}, Beyond Birthday Bound, Cover-free, PRF, Sum of PRP.

Date: received 1 Oct 2015, last revised 11 Feb 2016, withdrawn 15 Feb 2017

Contact author: nilanjan_isi_jrf at yaho com; avirocks dutta13@gmail com; mridul nandi@gmail com; goutam paul@isical ac in; liting zhang@hotmail com

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

Note: We have found a flaw in the security proof of 1k_PMAC+ and therefore we have decided to withdraw the paper as we do not want our wrong results to be cited in other works.

Version: 20170215:094018 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]