# 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:

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.

• Thanks for your answer. Actually when writing my question, I was kinda worried whether the math that's behind some of these MACs can't be attacked by quantum computers, since many use primes in some way. GHASH in GCM already has some problems, so I thought that maybe these can lead to real problems with quantum computers. – Paya Jun 16 '15 at 14:10
• @Paya: no, symmetric crypto such as MACs generally don't need to worry about Shor's algorithm (and Grover's just does key-halving). As for GCM, well, unless AES is broken, the security proof still holds, even if the attacker has a QC. – poncho Jun 16 '15 at 14:31
• New paper claims to break GCM, CBC-MAC, OCB, etc. on quantum computer: arxiv.org/abs/1602.05973 – dchest Feb 22 '16 at 12:58
• @dchest: assuming, of course, this completely unrealistic attack model. – poncho Feb 24 '16 at 18:18
• Is this attack model somehow a sidestep? Do the authors agree this attack model is unrealistic? – Melab Jan 14 '18 at 23:08

Actually, a post-quantum security is truly achieveable in a cipher-combo only. So - take a look at AES-finalist-candidates, like Serpent, and use it too or just it, but in 512 bit keys. Here is the starting point for you : enter link description here

• -1 Combinations of ciphers have nothing to do with post-quantum crypto. AES-256 by itself is secure in a post-quantum world, because quantum computers only give a quadratic speedup and 128-bits is secure. OTOH, combining ciphers gives you nothing special, since the best attacks against symmetric crypto are general search algorithms that don't care how you're encrypting the message, just how long the key is. – cpast May 19 '15 at 2:16
• That's the point : 512 bit key will help for sure, but it's not H/W accelerated yet. That's why I've mentioned the cipher stack : it will not add the lengths of the keys, of course, but it is able to give you 256+ bit security WITH hardware acceleration. If you just need a security boost and don't care about the speed - use 512 bit variants from the AES finalists – Alexey Vesnin May 27 '15 at 15:53