A New Variant of PMAC: Beyond the Birthday Bound

Abstract. We propose a PMAC-type mode of operation that can be used as a highly secure MAC (Message Authentication Code) or PRF (Pseudo-Random Function). Our scheme is based on the assumption that the underlying n-bit blockcipher is a pseudo-random permutation. Our construction, which we call PMAC Plus, involves extensive modification to PMAC, requiring three blockcipher keys. The PMAC Plus algorithm is a first rate-1 (i.e., one blockcipher call per n-bit message block) blockcipher-based MAC secure against O(2^2n/3) queries, increasing the O(2^n/2) security of PMAC at a low additional cost. Our analysis uses some of the security-proof techniques developed with the sum construction (Eurocrypt 2000) and with the encrypted-CBC sum construction (CT-RSA 2010).

Keywords: 64-bit blockcipher, PRP, sum construction, CBC vs. PMAC, game-playing technique.