Is (AES-)GCM parallelizable? I recentely faced the issue of random access decryption while AES-GCM was being used. I said this person that the underlying CTR should allow parallelization but I have no idea how authentication comes into play.

Now I know that one of the cool features of CTR is that you can decrypt any block without needing to involve any other blocks. I also know that CTR is part of the basis for GCM.

Now my question(s) are:


Can one somehow parallelize encryption of data in GCM mode (only CTR part? Parts of the MAC as well?)
Is it possible to get random access to decrypted ciphertexts (+ fast verification?) or is at least somehow possible to parallelize decryption and authentication (do either of both in parallel or internally parallelize?)?
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 computation is evaluated within the field $GF(2^{128})$; since it is a field, all the standard ways of rearranging the polynomial work.

For example, if we wanted to convert this into a three-way parallelism, we could compute $j = h^3$, and then the three polynomials in parallel:

$$tag_2 = j^0x_2 + j^1x_5 + j^2x_8 + ...$$
$$tag_1 = j^0x_1 + j^1x_4 + j^2x_7 + ...$$
$$tag_0 = j^0x_0 + j^1x_3 + j^2x_6 + ...$$

and then combine them for the final result $tag = h^2tag_2 + h^1tag_1 + h^0tag_0$

Obviously, we can tune this to whatever degree of parallelism that suits us, and we haven't changed the tag result in any way.

Stephen also notes that the entire message needs to be scanned to compute the tag; this is trivally true of any method that has a tag that's a complex function of the entire message.