**Improved Security Analysis of PMAC**

*Mridul Nandi and Avradip Mandal*

**Abstract: **In this paper we provide a simple, concrete and improved security
analysis of {\bf PMAC}, a Parallelizable Message Authentication
Code. We show that the advantage of any distinguisher for {\bf PMAC}
based on a random permutation is at most $\mathbf{\frac{5q\sigma -
3.5 q^2}{2^n}}$, where $\sigma$ is the total number of message
blocks in all $q$ queries made by the distinguisher. In the original
paper by Black and Rogaway in Eurocrypt-2002, the bound was
$\frac{(\sigma+1)^2}{2^{n-1}}$. Very recently, Minematsu and
Matsushima in FSE-2007, have provided a bound $\frac{10\ell
q^2}{2^n}$ where $\ell$ is the maximum block length of all messages
queried by the distinguisher. Our new bound is better than both
original and recently proposed bound and guarantees much more
security of PMAC. We also have provided a complete, independent and
simple combinatorial proof. This proof idea may help us to find a
similar result for other MAC algorithms.

**Category / Keywords: **secret-key cryptography / Message Authentication Codes

**Date: **received 1 Feb 2007, last revised 1 May 2007

**Contact author: **mridul nandi at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20070501:093211 (All versions of this report)

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

[ Cryptology ePrint archive ]