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?
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.