International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: A Block-Cipher Mode of Operation for Parallelizable Message Authentication

Authors:
John Black
Phillip Rogaway
Download:
URL: http://eprint.iacr.org/2001/027
Search ePrint
Search Google
Abstract: 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.
BibTeX
@misc{eprint-2001-11439,
  title={A Block-Cipher Mode of Operation for Parallelizable Message Authentication},
  booktitle={IACR Eprint archive},
  keywords={block-cipher modes, message authentication codes, modes of operation, provable security},
  url={http://eprint.iacr.org/2001/027},
  note={An extended abstract to appear at Eurocrypt 2002.  This is the full version. jrblack@cs.colorado.edu 11934 received 1 Apr 2001, last revised 4 Sep 2002},
  author={John Black and Phillip Rogaway},
  year=2001
}