# Tag Info

1

The authentication tag in GCM is generated by XORing a block cipher output with the Galois field hash (and truncating it for shorter lengths). It is thus assumed to look PRF. So it is effectively just a random nonce that should not collide until a birthday bound of $2^{t/2}$. With a tag length of 96 or more bits, it should be secure. Shorter random IV ...

13

Contrary to what Stephen says, you absolutely can compute the tag in parallel. Here's how it works; the tag computation is essentially "assemble the AAD, data, the length field and $Encr(Nonce)$ into a series of values $x_n, x_{n-1}, x_{n-2}, ..., x_0$", and then "compute the polynomial $x_nh^n + x_{n-1}h^{n-1} + x_{n-2}h^{n-2} + ... + x_0h^0$ This ...

5

The GCM flowchart on Wikipedia and my intuition support the notion that some of the GCM work can be done in parallel. At the very least you can do each $E_k(ctr)$ operation in parallel, but it doesn't look like you should be able to parallelize the authentication, as each $mult_H$ requires the output of a previous call as its input. Edit: poncho explains why ...

Top 50 recent answers are included