This paper defines and analyzes a fully deterministic parallelizable block-cipher mode of operation for message authentication — DPMAC (deterministic parallelizable message authentication code). DPMAC is constructed based on a 128-bit block cipher, works for strings of any bit length, and employs a single block-cipher key. Its security is proved, using the Game-Playing technique to quantify an adversary’s forgery probability in terms of the quality of the block cipher as a pseudo-random permutation.