Is GCM mode of authenticated encryption quantum secure?

Regarding post-quantum symmetric cryptography, it has been recommended to move to AES-256 or similar ciphers with 256-bit keys. How is authenticated encryption affected? Is AES-256-GCM considered quantum-safe? what are the other alternatives for post-quantum authenticated encryption?

• For the last question: HMAC is the typical, traditional, auth believed secure against quantum computing. Pair this with a symmetric cipher of your choice. – Thomas M. DuBuisson Jan 5 '18 at 17:28

Is AES-256-GCM considered quantum-safe?

For most common scenarios, yes.

Actually, it depends on your attack model. If your attack model is that the attacker is allowed to perform entangled queries on your GCM implementation, and return entangled responses, then, no, GCM is known not to be secure against this model; the attacker can use Grover's algorithm on the decryption Oracle to find a second valid ciphertext/tag with a previous seen nonce with $O(2^{64})$ work.

On the other hand, the attack model is rarely appropriate. Entanglement is quite delicate, and to make this attack model work, the decryption oracle would need to be implemented using quantum error correction. Typically, implementations don't help out the adversary to that extent, and hence it would need to be implemented as a part of the quantum computer (so that the adversary can implement quantum error correction within the oracle). About the only way this would be practical would be if you were attacking a white-box GCM implementation (so you couldn't trivially examine the implementation and extract the key).

In the standard scenario, where the attacker is allowed to make conventional queries to the oracle, and get the standard response, the standard proof of GCM applies; unless they can distinguish AES from a random permutation, they cannot generate a valid ciphertext/tag pair with nontrivial probability; using a 256 bit AES key means that Grover's algorithm would take $O(2^{128})$ time for this, which is generally considered infeasible.

• Actually, a Grover attack is only a polynomial speed-up. For entangled attack models, there are exponetially faxter attacks against GCM, using quantum period finding: see arxiv.org/abs/1602.05973 – Frédéric Grosshans Jan 8 '18 at 17:22
• @poncho What do you say about that paper? – Melab Jan 13 '18 at 13:26
• The paper is theoretically amusing, but completely irrelevant in the real world. Nobody with the tiniest shred of sanity would ever engineer a system that computes a quantum superposition of their secret function, e.g. AES-GCM under a secret key. The ‘standard scenario’ poncho mentions is the only relevant one—and the development of cheap quantum computers won't change that. – Squeamish Ossifrage Jun 8 '18 at 17:06