Paper 2001/027

A Block-Cipher Mode of Operation for Parallelizable Message Authentication

John Black and Phillip Rogaway


We define and analyze a simple and fully parallelizable block-cipher mode of operation for message authentication. Parallelizability does not come at the expense of serial efficiency: in a conventional, serial environment, the algorithm's speed is within a few percent of the (inherently sequential) CBC~MAC. The new mode, PMAC, is deterministic, resembles a standard mode of operation (and not a Carter-Wegman MAC), works for strings of any bit length, employs a single block-cipher key, and uses just max{1, ceiling(|M|/n)} block-cipher calls to MAC any string M using an n-bit block cipher. We prove PMAC secure, quantifying an adversary's forgery probability in terms of the quality of the block cipher as a pseudorandom permutation.

Available format(s)
Publication info
Published elsewhere. An extended abstract to appear at Eurocrypt 2002. This is the full version.
block-cipher modesmessage authentication codesmodes of operationprovable security
Contact author(s)
jrblack @ cs colorado edu
2002-09-04: last of 6 revisions
2001-04-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {John Black and Phillip Rogaway},
      title = {A Block-Cipher Mode of Operation for Parallelizable Message Authentication},
      howpublished = {Cryptology ePrint Archive, Paper 2001/027},
      year = {2001},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.