Partial decryption of large file in AES-GCM (or other modes)? Lets assume 


a 4gig file that is internally made of 1 million pages of 4k bytes each (page). 
the file was originally AES-GCM encrypted
these pages (or entire file) lives across the internet i.e. individual page reads are expensive/slow. (network IO operations are at page level by the way)


Is there any way to decrypt the 1,000,000th page without first fetching the 999,999 pages? I think not because the mac in GCM needs to 'digest' all the data that was encrypted, right.

The only other scheme I can think of is performing encryption/decryption at a page level but then we'd have to store 28 bytes extra (128 bits IV + 96 bits tag) for every page. One could argue 28MB overhead for a 4GB file isn't much but I'm trying to minimize overheads.

I would love to see if someone has a better design proposal for this situation.
Sure, basically GCM is counter mode encryption with an authentication tag added. You can encrypt any part of the stream without issue if you know the key and the counter for that part. Obviously, you cannot check the integrity though, because the tag is the integrity of the entire file.

Basically, you only have to perform the top part of the scheme: