Is AES-128 quantum safe?

Question

I've been reading lately some contradicting messages with regards to the quantum-safe resistance of AES128. First, there are blog posts by Ericsson people like these ones:

Can quantum attackers break AES-128?

No. NIST estimates that a quantum computer breaking RSA-2048 in a matter of hours could be built by 2030 for about a billion dollars. This means that NIST estimates early quantum computers to have a clock rate of a few MHz. Such a quantum computer (a single 20 MHz quantum core) running Grover’s algorithm would need 10¹¹ years (a hundred billion years) to break AES-128. Even a cluster of 109 quantum cores (the world's largest public classical supercomputer has 10⁷ cores) with a clock rate of 2 THz would need 10⁶ years (a million years) to break AES-128.

Considering all this, Grover’s algorithm does not pose any apparent threat to symmetric cryptography. Some years ago, there was a common conception that Grover’s algorithm required symmetric key sizes to be doubled – requiring use of AES-256 instead of AES-128. This is today considered a misconception – NIST, for example, now states that AES-128 will likely remain secure for decades to come, despite Grover’s algorithm [5].

In fact, one of the security levels in the NIST PQC standardization is equivalent to that of AES-128. This means that NIST thinks it is relevant to standardize parameters for PQC that are as strong under quantum attacks as AES-128. There could, of course, be other reasons why a longer key is needed, such as compliance, and using a longer key only has a marginal effect on performance.

In summary, our most important symmetric cryptographic tools (AES, SNOW 3G, SHA2, SHA3 and so on) remain secure against quantum computers as they are. This also applies to the authentication, key generation, encryption and integrity in 3G, 4G and 5G that rely purely on symmetric cryptography.

Sources: here and here

Also, some folks in Cloudfare mention:

This all is a long-winded way of saying that security level 1 seems solid for the foreseeable future.

source here

And finally, NIST also mentions regarding the evaluation criteria for PQC:

NIST will base its classification on the range of security strengths offered by the existing NIST standards in symmetric cryptography, which NIST expects to offer significant resistance to quantum cryptanalysis. In particular, NIST will define a separate category for each of the > following security requirements (listed in order of increasing strength2):

• Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 128-bit key (e.g. AES128)

It is worth noting that the security categories based on these reference primitives provide substantially more quantum security than a naïve analysis might suggest. For example, categories 1, 3 and 5 are defined in terms of block ciphers, which can be broken using Grover’s algorithm, with a quadratic quantum speedup. But Grover’s algorithm requires a long-running serial computation, which is difficult to implement in practice. In a realistic attack, one has to run many smaller instances of the algorithm in parallel, which makes the quantum speedup less dramatic.

source: here

So, where is the truth? I had this impression for many years that we will definitely need to double the key sizes in symmetric crypto to remain quantum safe. Is this really a misconception?

Answer 1

All of the above sources are correct; there is not a realistic threat to AES from Grover's algorithm.

The headline statement of $2^{64}$ quantum operations is often misinterpreted because people think of $2^{64}$ operations as computationally feasible. What they do not realise is that whereas $2^{64}$ operations performed in parallel are feasible for modern classical computers, $2^{64}$ operations performed in serial are not feasible. The other thing to know is that Grover's algorithm is highly non-parallelisable. If we deploy $2^c$ computational units in parallel to search using Grover's algorithm, it will complete in time proportional to $2^{(128-c)/2}$ so that using 256-quantum computers will only reduce runtime by 1/16, 1024-quantum computer will only reduce runtime by 1/32 and so forth.

Now consider that quantum computers currently operate at the kHz clock rate in comparison to classical computers that might run at the GHz clock rate and we see there is a huge gulf to overcome. See the Ericsson numbers for examples (note that the Ericsson site has a typo: 106 years should read $10^6$ years).

One might ask whether an improved algorithm could outperform Grover's algorithm. However Christof Zalka has shown that Grover's algorithm (and in particular its non-parallel nature) is the best possible complexity for unstructured search.

Answer 2

I am NOT an expert on computer science or quantum computing.

@Fabian Röling

Regular computers are deterministic. You know you'll be able to bruteforce the key and get it right even if it takes gazillion years to achieve so.

In QC's, the situation is rather different. Thanks to the superposition of quantum particles, you will be able to generate all 256-bit keys at once along with the corresponding outputs.

HOWEVER!

You will NOT be able to select the right key/output combo as you wish, instead you will end up with a random one. The reason is that measuring the state of the quantum particle (up-down) will cause it to randomly collapse into one of those states.

Also check out the Shor's algorithm and the way it utilizes QC's to eliminate the wrong guesses in breaking RSA keys.

The absence of a similar algorithm for AES is what makes it secure for Post-Quantum Cryptography I think.

Edit: It seems my answer was somewhat not quite right. I have released a better version down there.

Implementation of the Grover's algorithm and possible alternatives to the algorithm is pretty much non parallelizible on the QC's.

Thus, with clock rates at the level of kHz the large scale implementation of it seems like a scenario which is rather very far into the future...

I believe that exploiting the algorithm itself seems more that of a possibility compared to breaking the keys.

TL;DR: AES-128 bits will hold its security for quite some time.