Is there any variant of the Carter-Wegman MAC algorithm that is fast, parallel and has the property of incremental crypto?

  • $\begingroup$ You can always interleave several MACs $\endgroup$ Aug 19, 2014 at 8:46
  • 2
    $\begingroup$ Sorry, I don't understand $\endgroup$
    – BlaX
    Aug 19, 2014 at 9:41

1 Answer 1


How about GMAC? It's a Carter-Wegman MAC that meets the requirements of being fast to compute, and parallelizable.

In addition, it can be securely updated, that is, given a long message, you can compute the MAC of a modified version of that message faster than recomputing the entire MAC. For example, suppose you have a message/nonce/tag triple of $(N, M, T)$, and you want to change block $i$ of the message $M$ from the value $a$ to the value $b$ (where $i$ counts backwards; $i=0$ is the last block, $i=1$ is the next to last block). To do that, you create a fresh (never used before) nonce $N'$, and compute:

$T' = T \oplus (H^{i+2} \times (a \oplus b)) \oplus AES_k(Pad(N)) \oplus AES_k(Pad(N'))$

With the result being the triple $(N', M', T')$, where:

  • $k$ and $H$ are the key and secret values within GMAC
  • $\times$ and $H^{i+2}$ are computed within $GF(2^{128})$
  • $\oplus$ is exclusive or (which is addition within $GF(2^{128})$)
  • $i+2$ is computed with normal addition (not $GF(2^{128})$ addition).
  • $AES_k(X)$ is the AES block encryption (ECB mode) of the 128 bit block $X$
  • $Pad$ converts the nonce into a 128 bit value (for 96 bit nonces, this is just postpending 4 0x00 bytes; for other sizes, it's more complicated).

This takes $O(\log(i))$ time (and can be done faster if you precompute $H^x$ of various values of $x$), which I believe meets the incremental requirement.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.