Carter-Wegman MAC different notations

Question

While studying Carter-Wegman message authentication codes MAC, I got two different notations for the broader concept and have problems with understanding the difference, if any exist.

Let $K, K_1, K_2$ be randomly sampled keys, $k_i$ be a unique randomly sampled key (random nonce) for message $M_i$, and $h$ be a keyed strongly universal function (I assume making the strongly universal (hash) function keyed corresponds to random sampling the function).

I would define the concept of Carter-Wegman MAC as follows:

$$ Mac(K, M_i) = h(K, M_i) \oplus k_i $$

Now, I have seen multiple times that (e.g. here) that it can also be noted as follows:

$$ Mac(K_1 || K_2, M_i) = h(K_1, M_i) \oplus f(K_2, k_i) $$

(I introduce a second key because I already keyed $h$ to emphasize being a secret / randomly sampled hash function)

Can someone explain the difference in more detail? I see problems with the first definition because $k_i$ can be "Xored away", a problem the second notation does not have. But this way I read it from the original paper. Could my confusion arise from the concept of numbered messages?

Answer 1

Can someone explain the difference in more detail?

Actually, there is no real difference. When the first one says $k_i$, what it means is that there is a separate (and independent) $k_i$ for each message (hence, you can't 'xor' them out by xoring two different tags). One way of generating such a $k_i$ is to transform a nonce, that is $k_i = f(K_2, n_i)$, where $n_i$ is a public nonce. If we replace $n_i$ with $k_i$, we get the second equation.

That said, I would also note that the current usage of Carter-Wegman is somewhat different from the original paper. It assumed a 'strongly universal hash function set'; we know of constructions that can do that, but current practice is to go with a computationally cheaper option; one for which, for any two messages $M_1 \ne M_2$ and any $\delta$:

$$h(k, M_1) - h(k, M_2) = \delta$$

for only a tiny fraction of the possible key values $k$, and where the $-$ operation is some group subtraction operation.

We have such $h$ functions which provably meet this goal (and are efficient and take small keys); what this means is that the MAC actually becomes:

$$Mac( K_1, K_2, M, N ) = H( K_1, M ) + f( K_2, N )$$

where $+$ operation is addition in that same group.

Note that the $+$ operation need not be bit-wise xor. For Poly1305, it is actually modular addition (and Poly1305 does not meet the required property if we use the bitwise xor operation as its group operation).