A Parallelizable PRF-Based MAC Algorithm: Well beyond the Birthday Bound


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E96-A   No.1   pp.237-241
Publication Date: 2013/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E96.A.237
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Cryptography and Information Security)
PMAC,  checksum,  tweakable PRF,  compression function,  finite field,  system of linear equations,  query length,  

Full Text: PDF>>
Buy this Article

In this note we suggest a new parallelizable mode of operation for message authentication codes (MACs). The new MAC algorithm iterates a pseudo-random function (PRF) FK:{0,1}m → {0,1}n, where K is a key and m,n are positive integers such that m ≥ 2n. The new construction is an improvement over a sequential MAC algorithm presented at FSE2008, solving positively an open problem posed in the paper – the new mode is capable of fully parallel execution while achieving rate-1 efficiency and “full n-bit” security. Interestingly enough, PMAC-like parallel structure, rather than CBC-like serial iteration, has beneficial side effects on security. That is, the new construction is provided with a more straightforward security proof and with an even better (“-free”) security bound than the FSE 2008 construction.