International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Improved Security Analysis of PMAC

Authors:
Mridul Nandi
Avradip Mandal
Download:
URL: http://eprint.iacr.org/2007/031
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2007-13313,
  title={Improved Security Analysis of PMAC},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Message Authentication Codes},
  url={http://eprint.iacr.org/2007/031},
  note={ mridul.nandi@gmail.com 13634 received 1 Feb 2007, last revised 1 May 2007},
  author={Mridul Nandi and Avradip Mandal},
  year=2007
}