Improved security analysis of PMAC

In this paper we provide a simple, concrete and improved security analysis of Parallelizable Message Authentication Code or PMAC. In particular, we show that the advantage of any distinguisher at distinguishing PMAC from a random function is at most (5qσ – 3.5q2)/2n. Here, σ is the total number of message blocks in all q queries made by and PMAC is based on a random permutation over {0, 1}n. In the original paper of PMAC by Black and Rogaway in Eurocrypt-2002, the bound was shown to be (σ + 1)2/2n–1. In FSE-2007, Minematsu and Matsushima provided a bound 5ℓq2/(2n – 2ℓ), where ℓ is the number of blocks of the longest queried made by the distinguisher. Our proposed bound is sharper than these two previous bounds