Can a zero nonce be safely used with AES-GCM if the key is random and never used again? I could generate a random nonce and prepend it to the ciphertext, but storage space is at a premium and the only constraint AES-GCM has on the nonce (if I'm reading correctly) is that the same nonce must never be paired with the same key for a second encryption.

The encryption key is randomly generated, used for a single encryption, split using Shamir's Secret Sharing Scheme, and discarded. When the key is reconstructed for decryption, there is no chance that it can be fed back through to encrypt again; a new random key is always generated for each encryption.

If that's the only constraint, then twelve zero bytes are as safe as twelve random bytes prepended to the ciphertext. I'm reading that the AES-GCM nonce is used as the IV for AES in CTR mode. It's okay to use a zero IV for AES-CTR as long as the key is never reused, but I don't want to assume without confirmation that AES-GCM does nothing relevant with the nonce besides passing it to AES CTR. Am I missing anything?
Usually. However, if you are using 128-bit AES in CTR mode (remember that GCM is essentially just CTR with authentication), then a kind of attack called a multi-target attack can become possible. This attack is realistic when an attacker has a huge amount of stored ciphertext, each with a random key. While breaking a specific key requires performing up to 2128 operations, breaking any key is significantly easier. This attack can be mitigated either by using a larger key size, or by using a random nonce.

From the above-linked blog post by DJB:


  What the attacker hopes to find inside the AES attack is a key collision. This means that a key guessed by the attack matches a key chosen by a user. Any particular guessed key has chance only 1/2128 of matching any particular user key, but the attack ends up merging costs across a batch of 240 user keys, amplifying the effectiveness of each guess by a factor 240.