Parallel variant of Carter-Wegman MAC with incremental property Is there any variant of the Carter-Wegman MAC algorithm that is fast, parallel and has the property of incremental crypto?
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.