International Association
for Cryptologic Research

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 either suffer from birthday attacks or require long key sizes. In this paper, we focus on designing beyond-birthday-bound MAC modes with a single key, and investigate their design

principles. First, we review the current proposals, e.g. 3kf9 and PMAC\\_Plus,

and identify that the security primarily comes from the construction of a cover-free function and the advantage of the sum of PRPs. The main challenge in

reducing their key size is to find a mechanism to carefully separate the block cipher inputs to the cover-free construction and the sum of PRPs that work in

cascade with such a construction. Secondly, we develop several tools on sampling distributions that are quite useful in analysis of the MAC mode of operations and by which we unify the proofs for three/two-key beyond-birthday-bound MACs. Thirdly, we establish our main theorem that upper-bounds the PRF security of the one-key constructions by extended-cover-free, pseudo-cover-free, block-wise universal and the normal PRP assumption on block ciphers. Finally, we apply our main theorem to 3kf9 and PMAC\\_Plus, and successfully reduce their key sizes to the minimum possible. Thus, we solve a long-standing open problem in designing beyond-birthday-bound MAC with a single key.