Post-quantum authenticated encryption It is well-known that the Grover's algorithm reduces cryptographic strength of symmetric ciphers to a square-root - e.g. AES-256 becomes only 2128 strong.

However, these statements are always made about the raw block ciphers. How about GCM-AES256, CCM-AES256 and the like? The MAC tag in GCM is at most 128 bits. Does this mean GCM is not post-quantum secure, even if I use AES-256? What mode of operation that gives me authenticated encryption also gives me post-quantum security?



UPDATE

So I have found some interesting papers, namely:  


Secure Signatures and Chosen Ciphertext Security
in a Quantum Computing World
Quantum-Secure Message Authentication Codes


GCM uses Carter-Wegman MAC, and per the second paper (p. 18): This MAC is not, in general, secure in the quantum setting. But the authors (Dan Boneh and Mark Zhandry) do give an example of a modified CW-MAC that is secure in quantum settings. So I guess that rules out the GCM mode, but what about CCM and others?

I am not sure whether the construction of MAC is the only issue in authenticated crypto, or the MAC tag space as well.
This [Carter-Wegman] MAC is not, in general, secure in the quantum setting


This is true; however we need to ask "what is this setting, and is it a realistic one?"

This setting is one where the adversary can ask queries that are composed of a superposition of quantum states, and the oracle returns the superposition of the answers.  In other words, the oracle (that is, the device with the MAC key that computes the MAC) must compute the answer without any decoherence in the quantum state, and the messages to and from the adversary must also not have any decoherence.  As far as we know, any significant amount of computation without decoherence must be done using Quantum Error Correction (to adjust for the decoherence that just occurs naturally), this effectively means that the device with the MAC key must be a part of the quantum computer (but, for some reason, the attacker doesn't look inside the device and just extract the MAC key).

I would argue that this is not an attack model that we need to worry about, if we're just creating devices that exchange messages, and are worried about someone building a Quantum Computer.

We do need to worry about Grover's algorithm, which given a function $F(x)$ with an unknown $n$-bit input, find an $x$ where $F(x)$ is a specific value in $O(2^{n/2})$ time.  However, the attacker can't take advantage to try to compute a 128-bit MAC tag; because, in addition to the tag that the attacker is searching for, the algorithm also has the key as the input, and the attacker doesn't know that.  Grover's algorithm could be used to attack the key itself; we can prevent that from being a possibility by using a 256 bit key.